ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a connected kk-regular graph on nn vertices. Its spectral gap, or algebraic connectivity, is the second smallest eigenvalue of its Laplacian matrix. Equivalently, for regular graphs it is kk times the second smallest eigenvalue of the normalized Laplacian.

Aldous–Fill spectral-gap conjecture. The spectral gap of a connected kk-regular graph on nn vertices is at least

(1+o(1))2kπ23n2,(1+o(1))\frac{2k\pi^2}{3n^2},

and the bound is attained for at least one value of kk.

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 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.