Rough-isometry invariance of mixing time for bounded-degree graphs

At least 18 years old · documented by

Let GG and HH be graphs with deg⁡G,deg⁡H≤d\deg G,\deg H\leq d, equipped with their path metrics. Let f:G→Hf:G\to H be a rough isometry with constant KK, meaning that for all vertices a,b∈Ga,b\in G,

1Kd(a,b)−K≤d(f(a),f(b))≤Kd(a,b)+K,\frac{1}{K}d(a,b)-K\leq d(f(a),f(b))\leq Kd(a,b)+K,

and every vertex of HH lies within distance KK of some vertex in the image of ff. Write τ(G)\tau(G) and τ(H)\tau(H) for the mixing times of the simple random walks on the two graphs.

Rough-isometry invariance conjecture. There is a constant C(K,d)C(K,d) such that

τ(G)≤C(K,d)τ(H).\tau(G)\leq C(K,d)\tau(H).

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

Never refreshed

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.