Depth-bound conjecture for vertex-transitive graphs

Let GG be a connected vertex-transitive graph, let AV(G)A\subseteq V(G) be finite with 0<A12V(G)0<|A|\leq \tfrac12|V(G)|, let A\partial A denote the vertex boundary of AA, and let depth(A)\operatorname{depth}(A) denote the depth of AA. Depth-bound conjecture. There exists a fixed constant c>0c>0 such that

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

This conjecture would replace the diameter in the Babai–Szegedy boundary estimate by a constant multiple of the depth, and would yield the expected quadratic bound in the paper's main theorem. Its status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Matt DeVos and Bojan Mohar, “Small separations in vertex transitive graphs”, arXiv:1110.4885 (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.