Elphick–Wocjan conjecture on the spectral lower bound for clique number
Elphick–Wocjan conjecture on the spectral lower bound for clique number
Let be a graph with vertices, let be the eigenvalues of its adjacency matrix, and let be the sum of the squares of its positive eigenvalues:
Let denote the clique number of . Elphick–Wocjan conjecture. The positive-eigenvalue spectral quantity satisfies
Equivalently,
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
Sign in to submit a solution.
No solutions have been posted yet.