Kwan–Wigderson's unbounded inertia conjecture for graphs with independence number two
Kwan–Wigderson's unbounded inertia conjecture for graphs with independence number two
Let be a simple graph, and let denote its independence number. A weighted adjacency matrix of is a Hermitian matrix indexed by such that only when . For a Hermitian matrix , let be the number of nonnegative eigenvalues, and define as the minimum of over all weighted adjacency matrices of .
Kwan–Wigderson's conjecture. For every integer , there exists a graph with and
for every weighted adjacency matrix of .
This conjecture concerns whether the inertia bound 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
Sign in to submit a solution.
No solutions have been posted yet.