Chung's singular-value discrepancy conjecture for regular graphs
Chung's singular-value discrepancy conjecture for regular graphs
For a graph on vertices, write for its number of edges and set
For nonempty vertex subsets , let
Let denote the second-largest singular value of the adjacency matrix of . Chung's conjecture. There is an absolute constant such that for every regular graph ,
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.