The far-from-Turán second-eigenvalue conjecture
Statement
For a graph on vertices, call -far from if at least edge changes are required to obtain a graph isomorphic to . A Turán graph is a complete multipartite graph whose parts are as equal in size as possible. Let denote the second largest eigenvalue of the adjacency matrix of a regular graph.
Far-from-Turán eigenvalue conjecture. For every , there exists such that, if is a regular -vertex graph that is -far from every Turán graph, including the empty graph, then
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 .
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.