← All problems

Elphick–Wocjan clique-number conjecture

For every finite simple graph GG with nn vertices, adjacency eigenvalues λ1,…,λn\lambda_1,\ldots,\lambda_n, clique number ω(G)\omega(G), and s+(G)=∑λi>0λi2s^+(G)=\sum_{\lambda_i>0}\lambda_i^2, prove that nn−s+(G)≤ω(G)\frac{n}{n-\sqrt{s^+(G)}}\leq \omega(G).

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A 2026 paper checks the conjecture for more infinite families and obtains a stronger bound there, but the conjecture for all graphs remains open.

Elphick and Wocjan proposed in 2018 that every graph satisfies nn−s+≤ω\frac{n}{n-\sqrt{s^+}}\leq\omega, where nn is the number of vertices, ω\omega the clique number, and s+s^+ the sum of squared positive adjacency eigenvalues.

Known results

  • Triangle-free, weakly perfect, Kneser, and almost all random graphs (Elphick–Wocjan, 2018 and 2021).
  • Conference graphs; specified strongly regular graphs; line graphs of complete graphs; Cartesian products; and dd-regular Ramanujan graphs with n≥11dn\geq 11d (2025).
  • The general conjecture is explicitly reported as open (2025).

October 15, 2026 verification classes

Jadav, Mallik, Panchangam, and Singh report a stronger spectral bound that verifies the conjecture for a new infinite graph family. This is a partial advance, not a general proof, and the preprint’s claim has not been independently verified here.

Current status (as of October 2026): The conjecture is verified for many graph classes, including infinite families, but remains open for general graphs; the latest strengthened-family result is unverified.

Sources

Solutions 0

No solutions have been posted yet.