DeVos–Mohar depth expansion conjecture for vertex-transitive graphs
Let be a connected vertex-transitive graph and let be finite, with . Define
DeVos–Mohar conjecture. There exists a fixed constant such that
The conjecture proposes replacing the diameter in the Babai–Szegedy isoperimetric inequality by the depth of the set. It is refuted by examples in the Cayley graph of , and consequently in suitable finite vertex-transitive graphs.
References
Primary source
Martha Giannoudovardi, “On Small Separations in Cayley Graphs”, arXiv:1112.1970 (2011).
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.