Local Expansion of Symmetrical Graphs
László Babai, Márió Szegedy · Combinatorics Probability Computing · 1992
A graph is vertex-transitive (edge-transitive) if its automorphism group acts transitively on the vertices (edges, resp.). The expansion rate of a subset S of the vertex set is the quotient e(S):= |∂(S)|/| S |, where ∂( S ) denotes the set of vertices not in S but adjacent to some vertex in S . Improving and extending previous results of Aldous and Babai, we give very simple proofs of the following results. Let X be a (finite or infinite) vertex-transitive graph and let S be a finite subset of the vertices. If X is finite, we also assume | S | ≤| V ( X )/2. Let d be the diameter of S in the metric induced by X . Then e(S) ≥1/( d + 1); and e(S) ≥ 2/( d +2) if X is finite and d is less than the diameter of X . If X is edge-transitive then |δ( S )|/| S | ≥ r /(2 d ), where ∂( S ) denotes the set of edges joining S to its complement and r is the harmonic mean of the minimum and maximum degrees of X . – Diverse applications of the results are mentioned.