Kwan–Wigderson's unbounded inertia conjecture for graphs with independence number two

From papers

Let G=(V,E)G=(V,E) be a simple graph, and let α(G)\alpha(G) denote its independence number. A weighted adjacency matrix of GG is a Hermitian matrix AA indexed by VV such that Aij0A_{ij}\neq 0 only when ijEij\in E. For a Hermitian matrix AA, let n0(A)n_{\geq 0}(A) be the number of nonnegative eigenvalues, and define n0(G)n_{\geq 0}(G) as the minimum of n0(A)n_{\geq 0}(A) over all weighted adjacency matrices AA of GG.

Kwan–Wigderson's conjecture. For every integer kk, there exists a graph GG with α(G)=2\alpha(G)=2 and

n0(A)kn_{\geq 0}(A)\geq k

for every weighted adjacency matrix AA of GG.

This conjecture concerns whether the inertia bound α(G)n0(G)\alpha(G)\leq n_{\geq 0}(G) can be arbitrarily far from tight, even among graphs with independence number two. It arose from work on Godsil's question about whether the inertia bound can always be attained by a suitable weighted adjacency matrix; the source provides no resolution of the conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Quanyu Tang, Shengtong Zhang and Clive Elphick, “Inertia, Independence and Expanders”, arXiv:2505.07305 (2025).

Solutions 0

No solutions have been posted yet.