Aldous–Fill and Guiduli–Mohar conjectures on minimum algebraic connectivity

Let $\tau(G)$ denote the relaxation time of the simple random walk on a connected regular graph $G$ with $n$ vertices. Aldous and Fill conjectured that, as $n\to\infty$ ,

\max_{\substack{G\text{ connected and regular\\ |V(G)|=n}}}\tau(G)\le (1+o(1))\frac{3n^2}{2\pi^2},

and that asymptotic equality holds for even $n$ . Equivalently, for a $d$ -regular graph, since $\tau(G)=d/\mu(G)$ where $\mu(G)$ is the algebraic connectivity, this predicts the corresponding extremal behavior for the minimum algebraic connectivity among connected regular graphs.

References

Primary source

arXiv

Additional references

Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures — arXiv — Maryam Abdi, Ebrahim Ghorbani
Graphs with Minimum Algebraic Connectivity II: Regular Graphs of Even Degree — arXiv — Maryam Abdi, Ebrahim Ghorbani

Posted 2 weeks ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed solved

Two new preprints claim to settle the linked conjectures, but no independent confirmation has appeared.

The Aldous–Fill and Guiduli–Mohar conjectures predict path-like structures for regular graphs with the smallest algebraic connectivity and related extremal relaxation-time behavior. The conjectures also connect minimum algebraic connectivity with graph diameter.

Known results

Cubic graphs: the minimum-gap graph was characterized, confirming the Aldous–Fill prediction for degree $3$ .
Quartic graphs: minimum-gap graphs were characterized up to the reported near-complete structural result, confirming the degree- $4$ case.
For larger degrees, maximum diameter does not generally imply minimum algebraic connectivity.
Asymptotic formulas were known for graphs with diameter $\frac{3n}{d+1}+O(1)$ , including distinct odd- and even-degree regular cases.

September 22, 2026 claimed resolution

Two preprints by Maryam Abdi and Ebrahim Ghorbani claim proofs for the odd- and even-degree cases and derive asymptotic formulas for the relevant extremal graphs. A separate preprint claims a uniform proof of the Aldous–Fill spectral-gap conjecture, with uniqueness of the cubic extremizer for sufficiently large even orders. These claims are unverified.

Current status (as of September 2026): the linked conjectures are claimed solved by new preprints, but their proofs and the full structural conclusions remain unverified.

Sources

No solutions have been posted yet.