betaFeedback

WorksMathematics

The limits of inertia bounds on graph powers

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.

Introduction

The independence number of a graph GG, denoted by α(G)\alpha(G), is one of the most studied parameters in graph theory. Since it is NP-hard to compute [36] and to approximate [55], a lot of effort has been put into finding good bounds on the independence number. The spectral approach has yielded many such bounds. The spectrum Spec⁡(G)\operatorname{Spec}(G) of a graph GG is the multiset of the eigenvalues of its adjacency matrix, which can be ordered as

λ1≥λ2≥⋯≥λn\lambda_1 \ge\lambda_2 \ge\cdots\ge\lambda_n

Two of the most well-known types of spectral bounds are ratio bounds (that use the ratio between the largest and smallest eigenvalues), and inertia bounds (that count the signs of the eigenvalues). While the ratio bounds are relatively well understood [28, 33, 54], the inertia bounds are much less well understood.

The first inertia bound was introduced in its unweighted form by Cvetković [23] in 1971. This bound was strong enough to give an algebraic proof of the Erdős-Ko-Rado theorem, which can also be obtained using the ratio bound, see e.g. [32]. However, the full power of the bound lies in the freedom to choose weights. Calderbank and Frankl [20] studied the weighted version of the inertia bound in 1992 in order to derive multiple results in extremal set theory. For a Hermitian matrix MM, we let n≥0(M)n_{\ge0}(M) be the number of non-negative eigenvalues of MM (counted with multiplicity). For a graph GG a weighted adjacency matrix of GG is a Hermitian matrix BB with zero diagonal where Bij=0B_{ij}=0 when there is no edge i∼ji\sim j in GG.

Theorem 1 (Weighted inertia bound, cf. [20]). For a graph GG and a weighted adjacency matrix BB,

α(G)≤n≥0(B).\alpha(G) \le n_{\ge0}(B).

We let n≥0(G)n_{\ge0}(G) denote the optimal bound on α(G)\alpha(G) obtained using Theorem 1. The strength of this bound is such that it is tight for every graph on at most 10 vertices [25]. The search space of weights is infinite and there is no practical program known to find optimal weights. There are some heuristics known, such as for Cayley graphs in [46], but no method that guarantees optimality. This also makes it hard to lower bound n≥0(G)n_{\ge0}(G) by anything larger than α(G)\alpha(G).

In 2018 Sinković published the first example where using real weights cannot give a matrix such that n≥0(B)n_{\ge0}(B) is equal to the independence number [47]. Only in the last two years has the separation between α(G)\alpha(G) and n≥0(G)n_{\ge0}(G) been stretched to arbitrarily large gaps. Kwan and Wigderson used ideas from probability theory to show that C4C_4-free graphs have a weighted inertia bound that grows linearly in the order nn [41]. Such graphs can have ratio bound and hence independence number bounded by O(n3/4)O(n^{3/4}). Elphick, Tang and Zhang [49] showed that there is no way to upper bound n≥0(G)n_{\ge0}(G) in terms of α(G)\alpha(G) by demonstrating a family of graphs with fixed independence number, α(G)=2\alpha(G)=2, where the weighted inertia bound grows at a rate Ω(n1/9)\Omega(n^{1/9}). In this paper we continue their line of work and show similar separation results for the more general kk-independence number of a graph.

The kk-independence number of a graph GG, denoted αk(G)\alpha_k(G), is a natural generalization of the independence number that considers sets where all vertices are at distance greater than kk from each other. This more general independence parameter is also NP-hard to compute, see [40]. Equivalently, it can be defined as the independence number of GkG^k, the kk-th graph power of GG, the graph on the same vertex set as GG where two vertices are adjacent if they are at distance at most kk in GG.

Graph powers help design efficient algorithms for specific combinatorial optimization problems, see [13, 17]. In distributed computing, the kk-th power of graph GG represents the possible flow of information during kk rounds of communication in a distributed network of processors organized according to a graph GG, see [44]. The investigation of the behavior of the independence number of graph powers is motivated by questions in (quantum) information theory and coding theory. Indeed, αk(G)\alpha_k(G) and hence inertia bounds can be used to estimate the possible size of minimum distance k+1k+1 codes, see e.g. [5, 6]. The inertia can also be used to upper bound the quantum kk-independence number [52] and the quantum distance-kk chromatic number [4, 8], which is particularly helpful because these parameters are not known to be computable.

Good inertia bounds typically require a good choice of weights. For graphs of interest this is much more difficult to find for GkG^k, than for GG, because the graph is denser and thus has more freedom in its choice of weights. This led Abiad, Coutinho and Fiol [2] to introduce a more restricted weight optimization version of the inertia bound, which bounds αk(G)\alpha_k(G) directly in terms of the spectrum of GG. Note that the relation between GG and GkG^k is not particularly algebraic, so their spectra are in general not related, see e.g. [3, 24, 53]. Therefore bounds on αk\alpha_k which use the spectrum of GG directly (such as the following bound) carry different information than those using the spectrum of GkG^k.

Theorem 2 (Inertia-type bound [2]). Let Pk\mathcal{P}_k denote the vector space of real polynomials in xx with degree at most kk. Let p∈Pkp \in\mathcal{P}_k and λ1≥λ2≥⋯≥λn\lambda_1 \ge\lambda_2 \ge\cdots\ge\lambda_n be the eigenvalues of the adjacency matrix AA of GG. Let w(p)=min⁡i(p(A))iiw(p) = \min_i(p(A))_{ii} and W(p)=max⁡i(p(A))iiW(p) = \max_i(p(A))_{ii} denote the minimum and maximum of the diagonal of p(A)p(A) and

In⁡k(p,G):=min⁡{∣{i:p(λi)≥w(p)}∣,∣{i:p(λi)≤W(p)}∣}.\operatorname{In}_k(p,G) := \min\left\{\left|\{i : p(\lambda_i) \ge w(p)\}\right|,\left|\{i : p(\lambda_i) \le W(p)\}\right|\right\}.

Then αk(G)≤In⁡k(p,G)\alpha_k(G) \le\operatorname{In}_k(p,G).

We write In⁡k(G)\operatorname{In}_k(G) for the optimal inertia-type bound, i.e., using the optimal polynomial. Even less is known about the performance of this inertia-type bound. Finding In⁡k(G)\operatorname{In}_k(G) can be formulated as a mixed-integer linear program [3], which can be solved in polynomial time for fixed kk [7]. Nevertheless, relatively little is known about the graphs for which the optimum equals αk(G)\alpha_k(G). Indeed, we do not know when the inertia-type bound is tight, except for one class of graphs attaining equality for p=xkp=x^k [1] and for specific Odd graphs [3].

In this paper we show that large separation exists between the kk-independence number and inertia bounds. We show this for both the weighted inertia bound on GkG^k and for the inertia-type bound on GG. During the preparation of this paper, it was shown that the weighted inertia bound is at least as strong as the inertia-type bound [31]. Indeed, the separation we show for the inertia-type bound is larger. In § 2 we use the approach from [49] to deduce separation results for the weighted inertia bound. In particular, we prove separation for random graphs (Corollary 5) and show that certain non-explicit Cayley graphs have αk(G)=2\alpha_k(G)=2, but have n≥0(Gk)=Ω~(n1/(6k))n_{\ge0}(G^k)=\tilde{\Omega}(n^{1/(6k)}).

Theorem 14. For fixed k≥3k \ge3 there is a sequence of graphs GnG_n of order NN such that αk(Gn)=2\alpha_k(G_n)=2 and n≥0(Gnk)≥Ω~(N1/(6k))n_{\ge0}(G_n^k) \ge\tilde{\Omega}(N^{1/(6k)}).

Separation also holds for k=2k=2, but our proof does not give the same 16k\frac{1}{6k} exponent. We cannot extend Kwan and Wigderson’s result [41] to get a linearly growing weighted inertia bound, because graph powers are not C4C_4-free and are generally locally dense. Instead, the proof of our separation result relies on the observation that all large enough subsets of certain Abelian groups can be written as a sumset A+AA+A. This follows from an extension of Alon’s result on this topic in [10] to symmetric sets and larger sums kAkA, see Theorem 6, which may be a result of independent interest. A month before the appearance of this preprint, Chae and Lee posted an article that also obtained the extension of Alon’s result to larger kk but without symmetry [21]. In § 3 we show that the inertia-type bound can grow linearly with the order while the diameter is at most kk (implying αk(G)=1\alpha_k(G)=1). We show this for random graphs of the right density (Corollary 17) and inspired by the recent construction of pseudorandom graphs by Forey, Fresán, Kowalski and Wigderson in [29] we also give explicit vertex-transitive graphs for which this holds.

Theorem 18. Fix an integer k≥5k \ge5 and prime p>kp > k. Define s=⌊k2⌋+1s=\left\lfloor\frac{k}{2}\right\rfloor+1. There exists an integer a≥1a \ge1 such that s∣p2a−1s \mid p^{2a}-1. For any large enough prime power q=(p2a)hq=(p^{2a})^h the graph

Gqs:=Cay⁡(Fqs,Ss),where Ss={±(t,t2,…,ts):t∈Fq×}G_q^s:=\operatorname{Cay}(\mathbb{F}_q^s,S_s),\qquad\text{where }S_s=\{\pm(t,t^2,\ldots,t^s):t\in\mathbb{F}_q^\times\}

has

αk(Gqs)=1,andIn⁡k(Gqs)=Ω(∣V(Gqs)∣) as q→∞.\alpha_k(G_q^s)=1,\qquad\text{and}\qquad\operatorname{In}_k(G_q^s)=\Omega(|V(G_q^s)|)\text{ as }q\to\infty.

The same separation result also holds for 2≤k≤42 \le k \le4, but requires different graphs and a different proof, which we only remark upon.

Notation

The following two sections can be read independently. Therefore each of them will contain its own necessary preliminaries. In both sections we prove results for the Erdős-Rényi random graph. We let G(n,p)G(n,p) denote this random graph on nn vertices where each edge is included independently with probability pp. The results we prove will be asymptotic. We use the following notation. For two positive functions f,g:N→R>0f,g:\mathbb{N}\to\mathbb{R}_{>0} we write f=o(g)f=o(g), ω(g)\omega(g), O(g)O(g) or Ω(g)\Omega(g) if the fraction f(n)g(n)\frac{f(n)}{g(n)} as n→∞n\to\infty goes to zero or infinity, is bounded from above or bounded from below by a constant C>0C>0 respectively. If f=O(g)f=O(g) and f=Ω(g)f=\Omega(g) we write f=Θ(g)f=\Theta(g). We also use f=O~(g)f=\widetilde{O}(g) if f(n)=O(gh)f(n)=O(gh) where hh is a polylogarithmic function. The notation Ω~\widetilde{\Omega} is used analogously. We use log⁡\log to denote logarithms with base 22 and ln⁡\ln for natural logarithms. Lastly, we say that a sequence of events EnE_n occurs with high probability if P(En)=1−o(1)\mathbb{P}(E_n)=1-o(1) as n→∞n\to\infty.

Separation of the weighted inertia bound

Recall that n≥0(G)n_{\ge0}(G) denotes the optimal weighted inertia bound for a graph GG. In [49] the authors lower bounded n≥0(G)n_{\ge0}(G) for complements of pseudorandom graphs. We use this lower bound to find separation results for the weighted inertia bound of random graphs and graph powers. Let λ(G)\lambda(G) denote max⁡{∣λ2(G)∣,∣λn(G)∣}\max\{|\lambda_2(G)|,|\lambda_n(G)|\}, the second largest absolute value of an eigenvalue. A graph is an (n,d,λ)(n,d,\lambda)-graph if it has order nn, is dd-regular and has λ(G)≤λ\lambda(G)\le\lambda.

References

  1. [1]A. Abiad, S. M. Cioabă, and M. Tait. Spectral bounds for the k-independence number of a graph. Linear Algebra Appl. 510 (2016), 160–170.arxiv.org/abs/1510.07186
  2. [2]A. Abiad, G. Coutinho, and M. A. Fiol. On the k-independence number of graphs. Discrete Math. 342.10 (2019), 2875–2885.
  3. [3]A. Abiad, G. Coutinho, M. Fiol, B. Nogueira, and S. Zeijlemaker. Optimization of eigenvalue bounds for the independence and chromatic number of graph powers. Discrete Math. 345.3 (2022), 112706.arxiv.org/abs/2010.12649
  4. [4]A. Abiad and B. Jany. Eigenvalue bounds for the quantum distance chromatic number of graph powers. Electron. J. Linear Algebra 41 (2025).arxiv.org/abs/2503.02367
  5. [5]A. Abiad, A. Neri, and H. Reijnders. Eigenvalue bounds for the distance-t chromatic number of a graph and their application to Lee codes. J. Algebra Appl. (2025), 2541024.arxiv.org/abs/2404.14839
  6. [6]A. Abiad, L. Peters, and A. Ravagnani. The Eigenvalue Method in coding theory. Can. J. Math. (2025), 1–41.DOI
  7. [7]A. Abiad, S. van Hoesel, and V. Michaux. Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers. arXiv:2605.00524 (2026).arxiv.org/abs/2605.00524
  8. [8]A. Abiad and J. Meeus. Tales of Hoffman: from a distance. arXiv:2512.13187 (2025).arxiv.org/abs/2512.13187
  9. [9]N. Alon. Explicit Ramsey graphs and orthonormal labelings. Electron. J. Combin. 1.1 (1994), #R12.DOI
  10. [10]N. Alon. Large sets in finite fields are sumsets. J. Number Theory 126 (2007), 110–118.DOI
  11. [11]N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Struct. Algorithms 5.2 (1994), 271–284.DOI
  12. [12]G. W. Anderson, A. Guionnet, and O. Zeitouni. An Introduction to Random Matrices. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2009.DOI
  13. [13]T. Andreae and H.-J. Bandelt. Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities. SIAM Journal on Discrete Mathematics 8.1 (1995), 1–16.DOI
  14. [14]G. Atkinson and A. Frieze. On the b-Independence Number of Sparse Random Graphs. Comb. Probab. Comput. 13.3 (2004), 295–309.
  15. [15]M. Beis, W. Duckworth, and M. Zito. Large k-independent sets of regular graphs. en. Electron. Notes Discrete Math. 19 (2005), 321–327.DOI
  16. [16]F. Benaych-Georges and A. Knowles. Lectures on the local semicircle law for Wigner matrices. arXiv:1601.04055 (2018).
  17. [17]M. A. Bender and C. Chekuri. Performance guarantees for the TSP with a parameterized triangle inequality. Inf. Process. Lett 73.1 (2000), 17–21.
  18. [18]B. Bollobás. Random Graphs. 2nd edition. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2001.
  19. [19]C. Brittenham and J. Pakianathan. Random walks and the “Euclidean” association scheme in finite vector spaces. Can. J. Math. 77.5 (Oct. 2025), 1664–1685.arxiv.org/abs/2401.04814
  20. [20]A. R. Calderbank and P. Frankl. Improved Upper Bounds Concerning the Erdős-Ko-Rado Theorem. Comb. Probab. and Comput. 1.2 (1992), 115–122.DOI
  21. [21]J. Chae and H. Lee. Random Cayley sum hypergraphs and k-fold sumsets. arXiv:2610.08629 (2026).arxiv.org/abs/2610.08629
  22. [22]S. D. Cohen. Uniform Distribution of Polynomials Over Finite Fields. J. Lond. Math. Soc. s2-6.1 (Dec. 1972), 93–102.DOI
  23. [23]D. M. Cvetković. GRAPHS AND THEIR SPECTRA. Publikacije Elektrotehničkog fakulteta. Serija Matematika i fizika 354/356 (1971), 1–50.
  24. [24]K. C. Das and J. Guo. Laplacian eigenvalues of the second power of a graph. Discrete Math. 313.5 (2013), 626–634.DOI
  25. [25]R. Elzinga and D. Gregory. Weighted matrix eigenvalue bounds on the independence number of a graph. Electron. J. Linear Algebra 20 (2010).DOI
  26. [26]A. Entin. Artin–Schreier L-functions and random unitary matrices. J. Number Theory 145 (Dec. 2014), 340–351.arxiv.org/abs/1308.3163
  27. [27]A. Erdős L.and Knowles, H.-T. Yau, and J. Yin. Spectral statistics of Erdős–Rényi graphs I: Local semicircle law. Ann. Probab. 41 (May 2013), 2279–2375.
  28. [28]Y. Filmus and N. Lindzey. Simple Algebraic Proofs of Uniqueness for Erdős–Ko-Rado Theorems. arXiv:2201.02887 (2022).arxiv.org/abs/2201.02887
  29. [29]A. Forey, J. Fresán, E. Kowalski, and Y. Wigderson. Spectrally indistinguishable pseudorandom graphs. arXiv:2511.21351 (2025).arxiv.org/abs/2511.21351
  30. [30]Z. Füredi and J. Komlós. The eigenvalues of random symmetric matrices. Combinatorica 1.3 (1981), 233–241.DOI
  31. [31]J. Gao, J. Ma, and O. Pikurhko. A note on the Ratio and Inertia Bounds for the k-Independence Number. arXiv:2606.01761 (2026).arxiv.org/abs/2606.01761
  32. [32]C. Godsil and K. Meagher. Erdős–Ko–Rado Theorems: Algebraic Approaches. Cambridge Studies in Advanced Mathematics. Cambridge: Cambridge University Press, 2015.DOI
  33. [33]W. H. Haemers. Hoffman’s ratio bound. Linear Algebra Appl. 617 (2021), 215–219.arxiv.org/abs/2102.05529
  34. [34]H. Hasse and H. Davenport. Die Nullstellen der Kongruenzzetafunktionen in gewissen zyklischen Fällen. Journal für die reine und angewandte Mathematik 172 (1935), 151–182.DOI
  35. [35]K. Ireland and M. Rosen. “Gauss and Jacobi Sums”. A Classical Introduction to Modern Number Theory. New York, NY: Springer New York, 1982, 88–107. ISBN: 978-1-4757-1779-2.
  36. [36]R. Karp. Reducibility among combinatorial problems (1972). Ideas that created the future—classic papers of computer science. MIT Press, Cambridge, MA, 2021, 349–356.DOI
  37. [37]N. M. Katz. Moments, Monodromy, and Perversity: A Diophantine Perspective. Volume 159. Annals of Mathematics Studies. Princeton, NJ: Princeton University Press, 2005.
  38. [38]N. M. Katz and P. Sarnak. Random Matrices, Frobenius Eigenvalues, and Monodromy. Volume 45. American Mathematical Society Colloquium Publications. Providence, RI: American Mathematical Society, 1999. ISBN: 0-8218-1017-0.DOI
  39. [39]F. Knox, D. Kühn, and D. Osthus. Edge-disjoint Hamilton cycles in random graphs. Random Struct. Alg. 46.3 (2015), 397–445.
  40. [40]M. C. Kong and Y. Zhao. On computing maximum k-independent sets. Congressus Numerantium 95 (1993), 47–47.
  41. [41]M. Kwan and Y. Wigderson. The inertia bound is far from tight. Bull. Lond. Math. Soc 56.10 (2024), 3196–3208.arxiv.org/abs/2312.04925
  42. [42]H. W. Lenstra. Galois Theory for Schemes. Electronic third edition. 2008.
  43. [43]R. Lidl and H. Niederreiter. Finite Fields. 2nd edition. Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press, 1996. ISBN: 978-0-521-39231-0.
  44. [44]N. Linial. Locality in Distributed Graph Algorithms. SIAM J. Comput. 21.1 (1992), 193–201.DOI
  45. [45]N. Lorenz and M. C. Zimmermann. Diameter and Girth of Representation Graphs of Quadratic Forms. arXiv:2503.01721 (2025).arxiv.org/abs/2503.01721
  46. [46]B. Rooney. Spectral aspects of cliques in graphs. PhD thesis. University of Waterloo, 2014.
  47. [47]J. Sinkovic. A graph for which the inertia bound is not tight. J. Algebr. Comb 47.1 (2018), 39–50.arxiv.org/abs/1609.02826
  48. [48]T. Stacks Project Authors. Stacks Project. https://stacks.math.columbia.edu/tag/03VD. 2018.
  49. [49]Q. Tang, S. Zhang, and C. Elphick. Inertia, independence and expanders. Bull. Lond. Math. Soc. 57.12 (2025), 4076–4095.DOI
  50. [50]K. S. Tikhanovtseva. The rate of the smallest value of the weighted measure of the nonnegativity set for polynomials with zero mean value on a closed interval. Proc. Steklov Inst. Math. 288.1 (2015), 195–201.DOI
  51. [51]L. V. Tran, V. H. Vu, and K. Wang. Sparse random graphs: Eigenvalues and eigenvectors. Random Struct Algorithms 42.1 (2013), 110–134.arxiv.org/abs/1011.6646
  52. [52]P. Wocjan, C. Elphick, and A. Abiad. Spectral upper bound on the quantum k-independence number of a graph. Electron. J. Linear Algebra 38 (2022), 331–338.arxiv.org/abs/1910.07339
  53. [53]R. Xing and B. Zhou. On the two largest distance eigenvalues of graph powers. Inf. Process. Lett. 119 (2017), 39–43.DOI
  54. [54]J. Zhou. Unified bounds for the independence number of graphs. Can. J. Math. 77.1 (2025), 97–117.DOI
  55. [55]D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM, New York, 2006, 681–690.

Paper details

vlnc:W_645837qb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents