Aldous–Fill spectral-gap conjecture for regular graphs
Statement
Let be a connected -regular graph on vertices. Its spectral gap, or algebraic connectivity, is the second smallest eigenvalue of its Laplacian matrix. Equivalently, for regular graphs it is times the second smallest eigenvalue of the normalized Laplacian.
Aldous–Fill spectral-gap conjecture. The spectral gap of a connected -regular graph on vertices is at least
and the bound is attained for at least one value of .
This is an equivalent spectral-gap formulation of the conjecture on maximum relaxation time. The paper proves it for cubic graphs, while the general assertion remains open in the supplied text.
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.