Lower-bound conjecture for the Cheeger constant of random Cayley graphs

About 8 years old · traced to

There is a random Cayley graph on a finite group GG generated by kk generators. For every ε∈(0,1)\varepsilon\in(0,1), consider groups with sufficiently large size and take sufficiently many generators.

Cheeger lower-bound conjecture. There exists an absolute constant cc such that, for all ε∈(0,1)\varepsilon\in(0,1), there are constants N(ε)N(\varepsilon) and M(ε)M(\varepsilon) such that, for every finite group GG with ∣G∣≥N(ε)|G|\geq N(\varepsilon) and every k≥M(ε)k\geq M(\varepsilon), the probability that the Cheeger constant is less than c∣G∣−1/kc|G|^{-1/k} is at most ε\varepsilon.

This is a probabilistic lower-bound formulation of the claimed order ∣G∣−1/k|G|^{-1/k} for the Cheeger constant. The supplied text does not provide evidence that this stronger formulation has been resolved.

References

Primary source

Jonathan Hermon and Sam Olesker-Taylor, “Supplementary Material for Random Cayley Graphs Project”, arXiv:1810.05130 (2021).

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.