An isoperimetric inequality for conjugation-invariant sets in the symmetric group

Original · EN

We prove an isoperimetric inequality for conjugation-invariant sets of size k in Sₙ, showing that these necessarily have edge-boundary considerably larger than some other sets of size k (provided k is small). Specifically, let Tₙ denote the Cayley graph on Sₙ generated by the set of all transpositions. We show that if A ⊂ Sₙ is a conjugation-invariant set with |A| = pn! ≤ n!/2, then the edge-boundary of A in Tₙ has size at least c · ₂ (1p)₂ ₂ (2p)· n · |A|, where c is an absolute constant. (This is sharp up to an absolute constant factor, when p = Θ(1/s!) for any s ∈ {1,2,...,n}.) It follows that if p = n⁻Θ⁽¹⁾, then the edge-boundary of a conjugation-invariant set of measure p is necessarily a factor of Ω(n / n) larger than the minimum edge-boundary over all sets of measure p.