Depth-bound conjecture for vertex-transitive graphs

At least 14 years old · documented by

Let GG be a connected vertex-transitive graph, let A⊆V(G)A\subseteq V(G) be finite with 0<∣A∣≤12∣V(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

∣∂A∣∣A∣≥cdepth⁡(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.

References

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.