---
OA_place: publisher
OA_type: hybrid
_id: '22154'
abstract:
- lang: eng
  text: 'The inertia bound and ratio bound (also known as the Cvetković bound and
    Hoffman bound) are two fundamental inequalities in spectral graph theory, giving
    upper bounds on the independence number a(G) of a graph G in terms of spectral
    information about a weighted adjacency matrix of G. For both inequalities, given
    a graph G, one needs to make a judicious choice of weighted adjacency matrix to
    obtain as strong a bound as possible. While there is a well‐established theory
    surrounding the ratio bound, the inertia bound is much more mysterious, and its
    limits are rather unclear. In fact, only recently did Sinkovic find the first
    example of a graph for which the inertia bound is not tight (for any weighted
    adjacency matrix), answering a longstanding question of Godsil. We show that the
    inertia bound can be extremely far from tight, and in fact can significantly underperform
    the ratio bound: for example, one of our results is that for infinitely many n,
    there is an n‐vertex graph for which even the unweighted ratio bound can prove
    a(G)<4n^3/4, but the inertia bound is always at least n/4. In particular, these
    results address questions of Rooney, Sinkovic, and Wocjan–Elphick–Abiad.'
acknowledgement: Open access funding provided by Eidgenossische Technische Hochschule
  Zurich.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Matthew
  full_name: Kwan, Matthew
  last_name: Kwan
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Kwan M, Wigderson Y. The inertia bound is far from tight. <i>Bulletin of the
    London Mathematical Society</i>. 2024;56(10):3196-3208. doi:<a href="https://doi.org/10.1112/blms.13127">10.1112/blms.13127</a>
  apa: Kwan, M., &#38; Wigderson, Y. (2024). The inertia bound is far from tight.
    <i>Bulletin of the London Mathematical Society</i>. Wiley. <a href="https://doi.org/10.1112/blms.13127">https://doi.org/10.1112/blms.13127</a>
  chicago: Kwan, Matthew, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.”
    <i>Bulletin of the London Mathematical Society</i>. Wiley, 2024. <a href="https://doi.org/10.1112/blms.13127">https://doi.org/10.1112/blms.13127</a>.
  ieee: M. Kwan and Y. Wigderson, “The inertia bound is far from tight,” <i>Bulletin
    of the London Mathematical Society</i>, vol. 56, no. 10. Wiley, pp. 3196–3208,
    2024.
  ista: Kwan M, Wigderson Y. 2024. The inertia bound is far from tight. Bulletin of
    the London Mathematical Society. 56(10), 3196–3208.
  mla: Kwan, Matthew, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.”
    <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 10, Wiley, 2024,
    pp. 3196–208, doi:<a href="https://doi.org/10.1112/blms.13127">10.1112/blms.13127</a>.
  short: M. Kwan, Y. Wigderson, Bulletin of the London Mathematical Society 56 (2024)
    3196–3208.
date_created: 2026-06-29T10:49:18Z
date_published: 2024-10-01T00:00:00Z
date_updated: 2026-07-08T07:34:36Z
day: '01'
ddc:
- '500'
doi: 10.1112/blms.13127
extern: '1'
external_id:
  arxiv:
  - '2312.04925'
intvolume: '        56'
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1112/blms.13127
month: '10'
oa: 1
oa_version: Published Version
page: 3196-3208
publication: Bulletin of the London Mathematical Society
publication_identifier:
  eissn:
  - 1469-2120
  issn:
  - 0024-6093
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: The inertia bound is far from tight
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 56
year: '2024'
...