Chung's singular-value discrepancy conjecture for regular graphs

For a graph GG on nn vertices, write e(G)e(G) for its number of edges and set

ρ(G)=e(G)(n2)1.\rho(G)=e(G)\binom{n}{2}^{-1}.

For nonempty vertex subsets X,YV(G)X,Y\subseteq V(G), let

disc2(G)=maxX,YV(G),X,Ye(X,Y)ρ(G)XYXY.disc_{2}(G)=\max_{X,Y\subseteq V(G),\,X\neq\varnothing,\,Y\neq\varnothing}\frac{\left|e(X,Y)-\rho(G)|X||Y|\right|}{\sqrt{|X||Y|}}.

Let σ2(G)\sigma_{2}(G) denote the second-largest singular value of the adjacency matrix of GG. Chung's conjecture. There is an absolute constant CC such that for every regular graph GG,

σ2(G)<Cdisc2(G).\sigma_{2}(G)<C\,disc_{2}(G).

The conjecture asks for a direct comparison between spectral expansion and edge-distribution discrepancy in regular graphs. The source attributes it to Fan Chung; its resolution is not specified in the supplied text.

Sources & referencesView supporting material

Primary source

Bela Bollobas and Vladimir Nikiforov, “Graphs and Hermitian matrices: discrepancy and singular values”, arXiv:math/0404559 (2004).

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.