Aldous–Fill conjecture on maximum relaxation time
Let be a connected regular graph on vertices, and let denote the relaxation time of its random walk, defined by
where is the second-largest eigenvalue of the transition matrix. Aldous–Fill conjecture. Over all connected regular graphs on vertices,
The conjecture concerns the slowest-mixing random walk among connected regular graphs and is equivalent, within each degree, to minimizing the spectral gap. The paper proves the corresponding asymptotic result for quartic graphs, so the conjecture follows for degree , while the general statement is not resolved here.
References
3 papers in this index state this conjecture (2018–2020). The statement above is taken from the most recent of them; the others are arXiv:1907.03733, arXiv:1804.05500.
Source: Maryam Abdi and Ebrahim Ghorbani, “Quartic Graphs with Minimum Spectral Gap”, arXiv:2008.03144 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.