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

##### View/Open

##### Volume

212

##### Pagination

139 - 162

##### DOI

10.1007/s11856-016-1296-7

##### Journal

Israel Journal of Mathematics

##### Issue

##### ISSN

1565-8511

##### Metadata

Show full item record##### Abstract

We prove an isoperimetric inequality for conjugation-invariant sets of size k in Sn, showing that these necessarily have edge-boundary considerably larger than some other sets of size k (provided k is small). Specifically, let Tn denote the Cayley graph on Sn generated by the set of all transpositions. We show that if A ⊂ Sn is a conjugation-invariant set with |A| = pn! ≤ n!/2, then the edge-boundary of A in Tn has size at least
c⋅log2(1p)log2log2(2p)⋅n⋅|A|
c⋅log2(1p)log2log2(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-Θ(1), then the edge-boundary of a conjugation-invariant set of measure p is necessarily a factor of Ω(log n/ log log n) larger than the minimum edge-boundary over all sets of measure p.

##### Authors

Atzmon, N; Ellis, D; Kogan, D##### Collections

- Applied Mathematics [140]