2011/10/21 by Matt DeVos, DeVos, Matt, Bojan Mohar +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #math.CO #math.GR
paper · pdf · doi:10.48550/arxiv.1110.4885
28 pages
arxiv created 2011/10/21 · arxiv updated 2011/10/24
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 ⊆ V be a finite vertex-set with |A| ≤ |V|/2 and |\v ∈ V ∖ A : u ∼ v for some u ∈ A \|≤ k. We show that whenever the diameter of G is at least 31(k+1)2, either |A| ≤ 2k3+k2, 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.