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

About 1 year old · traced to

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(1−1ω).\sqrt{s^+} \leq n\left(1-\frac{1}{\omega}\right).

Equivalently,

nn−s+≤ω.\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.

References

Primary source

Hareshkumar Jadav, Sreekara Madyastha, Rahul Raut and Ranveer Singh, “Strengthening Wilf's lower bound on clique number”, arXiv:2504.04836 (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.