The far-from-Turán second-eigenvalue conjecture

For a graph HH on nn vertices, call GG ε\varepsilon-far from HH if at least εn2\varepsilon n^2 edge changes are required to obtain a graph isomorphic to HH. A Turán graph is a complete multipartite graph whose parts are as equal in size as possible. Let λ2\lambda_2 denote the second largest eigenvalue of the adjacency matrix of a regular graph.

Far-from-Turán eigenvalue conjecture. For every ε>0\varepsilon>0, there exists c>0c>0 such that, if GG is a regular nn-vertex graph that is ε\varepsilon-far from every Turán graph, including the empty graph, then

λ2cn1/4.\lambda_2\geq cn^{1/4}.

This is the analogous spectral problem to the preceding discrepancy conjecture. The source presents it as an open question motivated by constructions far from Turán graphs with second eigenvalue of order n1/4n^{1/4}.

Sources & referencesView supporting material

Primary source

Eero Räty, Benny Sudakov and István Tomon, “Positive discrepancy, MaxCut, and eigenvalues of graphs”, arXiv:2311.02070 (2023).

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.