DeVos–Mohar depth expansion conjecture for vertex-transitive graphs

Let X=(V,E)X=(V,E) be a connected vertex-transitive graph and let AVA\subset V be finite, with 0<AV/20<|A|\leqslant |V|/2. Define

depth(A)=sup{d(u,VA)uA}.depth(A)=\sup\{d(u,V\smallsetminus A)\mid u\in A\}.

DeVos–Mohar conjecture. There exists a fixed constant c>0c>0 such that

AAcdepth(A).\frac{|\partial A|}{|A|}\geqslant \frac{c}{depth(A)}.

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 Z2\mathbb{Z}^2, 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

No solutions have been posted yet.