ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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

λ2≥cn1/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}.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.