The limits of inertia bounds on graph powers

We investigate the tightness of inertia and inertia-type bounds related to graph powers. This class of graphs appears in several contexts, such as the theory of distance-regular graphs, quantum information theory and coding theory. They are a priori not covered by previous separation constructions involving locally sparse graphs, see Kwan and Wigderson (2024), or Alon's pseudorandom graphs, see Elphick, Tang and Zhang (2025). Instead, we apply the latter's lower bound for complements of pseudorandom graphs to random graphs and random Cayley graph constructions, whose graph-power structure is ensured by additive combinatorial arguments. From this we are able to conclude that also for graph powers there can be a large gap between inertia bounds and the actual independence number. For the inertia-type bound, which is based on polynomials, we achieve even larger separation by considering sequences of graphs whose spectrum converges to a continuous distribution. Our methods draw from several areas of mathematics, ranging from additive combinatorics and probabilistic methods, to character sums over finite fields and arithmetic geometry.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-18
DOI
https://doi.org/10.48550/arxiv.2611.24865
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The limits of inertia bounds on graph powers

Sam Mattheus, Aida Abiad, Nils van de Berg
arXiv (Cornell University)
Limits and Structures in Graph Theory
preprint

The limits of inertia bounds on graph powers

Sam Mattheus, Aida Abiad, Nils van de Berg
preprint en

Abstract

We investigate the tightness of inertia and inertia-type bounds related to graph powers. This class of graphs appears in several contexts, such as the theory of distance-regular graphs, quantum information theory and coding theory. They are a priori not covered by previous separation constructions involving locally sparse graphs, see Kwan and Wigderson (2024), or Alon's pseudorandom graphs, see Elphick, Tang and Zhang (2025). Instead, we apply the latter's lower bound for complements of pseudorandom graphs to random graphs and random Cayley graph constructions, whose graph-power structure is ensured by additive combinatorial arguments. From this we are able to conclude that also for graph powers there can be a large gap between inertia bounds and the actual independence number. For the inertia-type bound, which is based on polynomials, we achieve even larger separation by considering sequences of graphs whose spectrum converges to a continuous distribution. Our methods draw from several areas of mathematics, ranging from additive combinatorics and probabilistic methods, to character sums over finite fields and arithmetic geometry.

arXiv (Cornell University)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon