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

About 1 year old · traced to

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 Aij≠0A_{ij}\neq 0 only when ij∈Eij\in E. For a Hermitian matrix AA, let n≥0(A)n_{\geq 0}(A) be the number of nonnegative eigenvalues, and define n≥0(G)n_{\geq 0}(G) as the minimum of n≥0(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

n≥0(A)≥kn_{\geq 0}(A)\geq k

for every weighted adjacency matrix AA of GG.

This conjecture concerns whether the inertia bound α(G)≤n≥0(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.