On Local Expansion of Vertex-Transitive Graphs
András Lukács · Combinatorics Probability Computing · 1998
Let X be a vertex-transitive graph and let S be an arbitrary finite subset of its vertices. Denote by @∂S the set of vertices adjacent to S but not in S. Babai and Szegedy proved that for an infinite, connected, locally finite X with subexponential growth we haveformula herewhere d(S) is the diameter of S. The aim of this note is to provide a slightly better, tight lower bound on this quantity. We prove thatformula hereunder the same conditions.