27th Conference of the International Linear Algebra Society (ILAS 2026)

Spectral bounds for the clique number of a graph

May 19, 2026, 5:00 PM

25m

Goodwin Hall 135 (Virginia Tech)

Minisymposium Talk Combinatorial Matrix Theory Combinatorial Matrix Theory

Speaker

Sudipta Mallik (Marshall University)

Description

Given an integer k, deciding whether a graph has a clique of size k is an NP-complete problem. Wilf's inequality provides a spectral lower bound for the clique number (i.e., the order of a largest clique) in terms of the largest adjacency eigenvalue. In 2018, Elphick and Wocjan conjectured a stronger spectral bound using positive adjacency eigenvalues. We introduce a spectral bound using Laplacian eigenvalues. We show that this is an improvement for almost all graphs.