DeVos–Mohar depth expansion conjecture for vertex-transitive graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.