Recognition: unknown
An exponentially small gap of the Perron vector on independent sets
Pith reviewed 2026-05-08 03:03 UTC · model grok-4.3
The pith
A construction of graphs with arbitrarily large chromatic number yields independent sets whose Perron-vector sum of squares approaches 1/2 with an exponentially small gap.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors show that for any independent set S there holds 1/2 - sum x_v^2 = q/(4λ - 2q) where λ is the spectral radius and q the Rayleigh quotient of the Perron vector restricted to V(G) minus S. They construct graphs with chromatic number tending to infinity and an independent set S making this gap exponentially small in the graph parameters, proving there is no universal polynomial-type lower bound on the gap.
What carries the argument
The gap identity 1/2 - sum_{v in S} x_v^2 = q / (4λ - 2q), which allows explicit control of the gap via choice of graph and set S to make q small relative to λ.
If this is right
- Odd cycles of length at least 7 provide simple counterexamples to Gregory's conjecture.
- The gap admits no lower bound of the form Omega(k^alpha / n^beta) for any alpha, beta > 0.
- The construction achieves tightness up to constants in some local sense.
- Local weighted lower bounds on the gap can be established.
Where Pith is reading between the lines
- The result implies that spectral properties of independent sets do not force polynomial separation from the bipartite maximum in high-chromatic graphs.
- Similar constructions might apply to other graph invariants like the independence number or eigenvalue gaps.
- Computationally, verifying the gap for large constructed graphs would require efficient Perron vector approximation methods.
Load-bearing premise
The specific graph family constructed has both the claimed high chromatic number and produces the exponentially small gap value when the formula is applied.
What would settle it
Compute the chromatic number and the exact gap value using the formula for the smallest instances of the constructed graph family and check if the gap is exponentially small while chromatic number exceeds any fixed bound.
Figures
read the original abstract
A classical result of Cioab\u{a} states that if $G$ is a connected graph with the unit Perron vector $\mathbf{x}$, then any independent set $S$ of $G$ satisfies $\sum_{v\in S} x_v^2 \le \frac{1}{2}$, with equality if and only if $G$ is a bipartite graph and $S$ is one of the partite sets. Let $\chi(G)= k $ be the chromatic number of $G$. A well-known conjecture of Gregory asserts that any independent set $S$ of $G$ satisfies $\frac{1}{2} - \sum_{v\in S}x_v^2 = \Omega ((k/n)^{1/2})$. Recently, Liu and Ning [J. Combin. Theory Ser. B 176 (2026)] disproved Gregory's conjecture by constructing a graph $G$ and an independent set $S$ such that $\frac{1}{2}- \sum_{v\in S}x_v^2 = O(k^5/n^3)$. Furthermore, they conjectured that this bound is tight up to a constant factor. In this paper, we first show that any cycle $C_n$ with odd integer $n\ge 7$ provides a simple counterexample to Gregory's conjecture. Second, we establish that for any independent set $S$, we have $\frac{1}{2} - \sum_{v\in S}x_v^2 = \frac{q}{4\lambda -2q}$, where $\lambda$ is the spectral radius of $G$, and $q$ is the Rayleigh quotient of $\mathbf{x}$ restricted to $\bar{S} :=V(G)\setminus S$. Third, we construct a graph with arbitrarily large chromatic number and find an independent set $S$ such that $\sum_{v\in S}x_v^2$ can be arbitrarily close to $\frac{1}{2}$, with an exponentially small gap. Our construction shows that there is no universal lower bound of the form $\Omega (k^{\alpha}/n^{\beta})$ for any $\alpha, \beta >0$. This settles both Gregory's original conjecture and the modified conjecture of Liu and Ning in the negative. Finally, we show the tightness of our construction and provide some local weighted lower bounds.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript disproves Gregory's conjecture by exhibiting odd cycles C_n (n≥7) as counterexamples where the gap 1/2 − ∑_{v∈S} x_v² equals 1/(2n), which is o((k/n)^{1/2}). It derives the exact identity 1/2 − ∑_{v∈S} x_v² = q/(4λ − 2q) from the eigenvalue equation Ax=λx by decomposing x^T A x into induced edges on the complement and cross terms, with q the Rayleigh quotient of x restricted to the complement of S. It then gives an explicit graph family with arbitrarily large chromatic number for which the gap is exponentially small, refuting also the modified conjecture of Liu and Ning that the gap is Ω(k^5/n^3) up to constants, and establishes tightness of the construction together with some local weighted lower bounds.
Significance. If the construction is verified, the work provides a definitive negative resolution to both conjectures by exhibiting graphs where the Perron mass on an independent set approaches 1/2 arbitrarily closely despite unbounded chromatic number, with the gap decaying exponentially rather than polynomially. The exact identity is parameter-free and obtained by direct algebraic manipulation of the Rayleigh quotient, offering a reusable tool for spectral analysis of independent sets. The cycle examples are immediately verifiable and parameter-free; the construction supplies an explicit, falsifiable family achieving the exponential decay while χ(G)→∞.
minor comments (2)
- In the abstract and introduction, the citation to Cioabă's result would benefit from an explicit reference (author, year, journal) for readers unfamiliar with the classical bound.
- The definition of the graph family in the construction section could include a small explicit example (e.g., for the smallest parameter yielding χ=4) to illustrate how the independent set S is chosen and how q is computed, improving readability without altering the proof.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript, for the accurate summary of our results, and for recommending acceptance. We are pleased that the referee recognized the significance of the exact identity, the simple cycle counterexamples, and the explicit construction achieving exponentially small gaps with unbounded chromatic number.
Circularity Check
No significant circularity; derivations are algebraic and construction-based
full rationale
The paper's key identity ½ − ∑_{v∈S} x_v² = q/(4λ − 2q) follows directly from algebraic manipulation of the eigenvalue equation Ax = λx, the decomposition of xᵀAx into induced and cross terms, and the definition of q as the Rayleigh quotient on the complement subgraph; this holds identically without fitting or external assumptions. Odd-cycle counterexamples are explicit, parameter-free, and immediately verifiable by direct computation of the Perron vector. The main construction is an explicit graph family whose chromatic number and gap are proved to satisfy the stated bounds via combinatorial arguments, independent of any self-citation chain. The citation to the authors' prior work merely contextualizes the modified conjecture being disproved and does not serve as a load-bearing premise for the new results or formula.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Perron-Frobenius theorem guarantees a unique positive unit eigenvector for the spectral radius of a connected graph
- standard math Rayleigh quotient equals the quadratic form x^T A x / x^T x
Reference graph
Works this paper leans on
-
[1]
Bhattacharya, S
A. Bhattacharya, S. Friedland, U.N. Peled, On the first eigenvalue of bipartite graphs, Elec- tron. J. Combin. 15 (2008), Paper No. R144
2008
-
[2]
Bilu, Tales of Hoffman: Three extensions of Hoffman’s bound on the graph chromatic number, J
Y. Bilu, Tales of Hoffman: Three extensions of Hoffman’s bound on the graph chromatic number, J. Combin. Theory Ser. B 96 (2006) 608–613
2006
-
[3]
Cioab˘ a, A necessary and sufficient eigenvector condition for a connected graph to be bipartite, Electron
S.M. Cioab˘ a, A necessary and sufficient eigenvector condition for a connected graph to be bipartite, Electron. J. Linear Algebra 20 (2010) 351–353
2010
-
[4]
Cioab˘ a, The principal eigenvector of a connected graph, in: Spectral Graph Theory Online Conference, (2021),http://spectralgraphtheory.org/sgt-online-program
S.M. Cioab˘ a, The principal eigenvector of a connected graph, in: Spectral Graph Theory Online Conference, (2021),http://spectralgraphtheory.org/sgt-online-program
2021
-
[5]
Cioab˘ a, D.N
S.M. Cioab˘ a, D.N. Desai, M. Tait, The spectral even cycle problem, Combin. Theory 4 (1) (2024), Paper No. 10. 14
2024
-
[6]
Csikv´ ari, V
P. Csikv´ ari, V. Harangi, The least balanced graphs and trees, J. Combin. Theory Ser. B 179 (2026) 147–204
2026
-
[7]
Godsil and M.W
C.D. Godsil and M.W. Newman, Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B 98 (2008) 721–734
2008
-
[8]
Haemers, Hoffman’s ratio bound, Linear Algebra Appl
W.H. Haemers, Hoffman’s ratio bound, Linear Algebra Appl. 617 (2021) 215–219
2021
-
[9]
Huang, Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, Ann
H. Huang, Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, Ann. of Math. (2) 190 (3) (2019) 949–955
2019
-
[10]
Jiang, J
Z. Jiang, J. Tidor, Y. Yao, S. Zhang, Y. Zhao, Equiangular lines with a fixed angle, Ann. of Math. (2) 194 (3) (2021) 729–743
2021
-
[11]
M. Kwan, Y. Wigderson, The inertia bound is far from tight, Bull. Lond. Math. Soc. 56 (10) (2024) 3196–3208
2024
-
[12]
S. Li, S. Zhao, L. Zou, Spectral extrema of graphs with fixed size: forbidden a fan graph, a friendship graph, or a theta graph, J. Graph Theory 110 (4) (2025) 483–495
2025
-
[13]
X. Li, M. Zhai, J. Shu, A Brualdi–Hoffman–Tur´ an problem on cycles, European J. Combin. 120 (2024), Paper No. 103966
2024
- [14]
- [15]
-
[16]
L. Liu, B. Ning, Unsolved problems in spectral graph theory, Oper. Res. Trans., 27 (2023) 33–60
2023
-
[17]
L. Liu, B. Ning, Local properties of the spectral radius and Perron vector in graphs, J. Combin. Theory Ser. B 176 (2026) 241–253
2026
-
[18]
Tait, The Colin de Verdi´ ere parameter, excluded minors, and the spectral radius, J
M. Tait, The Colin de Verdi´ ere parameter, excluded minors, and the spectral radius, J. Com- bin. Theory Ser. A 166 (2019) 42–58
2019
-
[19]
Q. Tang, S. Zhang, C. Elphick, Inertia, independence and expanders, Bull. Lond. Math. Soc. 57 (12) (2025) 4076–4095
2025
-
[20]
Wilf, The eigenvalues of a graph and its chromatic number, J
H.S. Wilf, The eigenvalues of a graph and its chromatic number, J. London Math. Soc. 42 (1967) 330–332
1967
-
[21]
Wocjan, C
P. Wocjan, C. Elphick, New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, Electronic J. Combin. 20(3) (2013), # P39. 15
2013
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.