Local Expansion of Symmetrical Graphs

Publisher Website
Google Scholar
Abstract
A graph is vertex-transitive (edge-transitive) if its automorphism group acts transitively on the vertices (edges, resp.). Theexpansion rateof a subsetSof the vertex set is the quotient e(S):= |∂(S)|/|S|, where ∂(S) denotes the set of vertices not inSbut adjacent to some vertex inS. Improving and extending previous results of Aldous and Babai, we give very simple proofs of the following results. LetXbe a (finite or infinite) vertex-transitive graph and letSbe a finite subset of the vertices. IfXis finite, we also assume |S| ≤|V(X)/2. Letdbe the diameter ofSin the metric induced byX. Then e(S) ≥1/(d+ 1); ande(S)≥ 2/(d+2) ifXis finite anddis less than the diameter ofX. IfXis edge-transitive then |δ(S)|/|S| ≥r/(2d), where ∂(S) denotes the set of edges joiningSto its complement andris the harmonic mean of the minimum and maximum degrees ofX. – Diverse applications of the results are mentioned.

This publication has 16 references indexed in Scilit: