pith. sign in

arxiv: 1110.4885 · v1 · pith:JJXCYAPWnew · submitted 2011-10-21 · 🧮 math.CO · math.GR

Small separations in vertex transitive graphs

classification 🧮 math.CO math.GR
keywords transitivevertexfinitegraphsroughseparationsstructuretheorem
0
0 comments X
read the original abstract

Let $k$ be an integer. We prove a rough structure theorem for separations of order at most $k$ in finite and infinite vertex transitive graphs. Let $G = (V,E)$ be a vertex transitive graph, let $A \subseteq V$ be a finite vertex-set with $|A| \le |V|/2$ and $|\{v \in V \setminus A : {$u \sim v$ for some $u \in A$} \}|\le k$. We show that whenever the diameter of $G$ is at least $31(k+1)^2$, either $|A| \le 2k^3+k^2$, or $G$ has a ring-like structure (with bounded parameters), and $A$ is efficiently contained in an interval. This theorem may be viewed as a rough characterization, generalizing an earlier result of Tindell, and has applications to the study of product sets and expansion in groups.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.