Small separations in vertex transitive graphs

Details Small separations in vertex transitive graphs Small separations in vertex transitive graphs

2011-10-21

arxiv.org/abs/1110.4885v1

Mathematics

Combinatorics

28 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Small separations in vertex transitive graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Small separations in vertex transitive graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small separations in vertex transitive graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-85991