Elphick–Wocjan conjecture on the spectral lower bound for clique number

From papers

Let GG be a graph with nn vertices, let λ1,,λn \lambda_1,\dots,\lambda_n be the eigenvalues of its adjacency matrix, and let s+ s^+ be the sum of the squares of its positive eigenvalues:

s+=λi>0λi2.s^+ = \sum_{\lambda_i>0}\lambda_i^2.

Let ω\omega denote the clique number of GG. Elphick–Wocjan conjecture. The positive-eigenvalue spectral quantity satisfies

s+n(11ω).\sqrt{s^+} \leq n\left(1-\frac{1}{\omega}\right).

Equivalently,

nns+ω.\frac{n}{n-\sqrt{s^+}}\leq\omega.

This conjecture strengthens Wilf's spectral lower bound on the clique number by replacing the largest adjacency eigenvalue with the square root of the sum of the squares of all positive eigenvalues. It is also stated as the second problem in a survey of open problems in spectral graph theory.

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

Hareshkumar Jadav, Sreekara Madyastha, Rahul Raut and Ranveer Singh, “Strengthening Wilf's lower bound on clique number”, arXiv:2504.04836 (2025).

Solutions 0

No solutions have been posted yet.