Rough-isometry invariance of mixing time for bounded-degree graphs
Let and be graphs with , equipped with their path metrics. Let be a rough isometry with constant , meaning that for all vertices ,
and every vertex of lies within distance of some vertex in the image of . Write and for the mixing times of the simple random walks on the two graphs.
Rough-isometry invariance conjecture. There is a constant such that
The claim asks whether mixing time is a geometric property in the setting of unweighted graphs of uniformly bounded degree, where the path metric provides the natural geometry. The supplied text presents it as a formal question and gives no resolution, so its status remains open.
References
Primary source
Gady Kozma, “On the precision of the spectral profile”, arXiv:0709.0112 (2008).
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.