Isoperimetric conjecture for finite vertex-transitive graphs

About 24 years old · traced to

Let GG be a finite, connected, vertex-transitive graph. Write diam⁡(G)\operatorname{diam}(G) for its diameter and, for a vertex set SS, let ∂S\partial S denote its edge boundary. Isoperimetric conjecture. If

diam⁡(G)<∣G∣α,\operatorname{diam}(G)<|G|^{\alpha},

then

∣∂S∣>cα∣S∣1−α|\partial S|>c_{\alpha}|S|^{1-\alpha}

for every SS with 1≤∣S∣≤∣G∣/21\leq |S|\leq |G|/2. This would strengthen the known lower bound for the Cheeger constant of a finite transitive graph in terms of the reciprocal of its diameter; the source gives no resolution of the conjecture.

References

Primary source

Itai Benjamini and Gady Kozma, “A Resistance Bound via an Isoperimetric Inequality”, arXiv:math/0212322 (2012).

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.