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

preprint2014arXivOpen access

Abstract

We prove an isoperimetric inequality for conjugation-invariant sets of size kk in SnS_n, showing that these necessarily have edge-boundary considerably larger than some other sets of size kk (provided kk is small). Specifically, let TnT_n denote the Cayley graph on SnS_n generated by the set of all transpositions. We show that if A⊂SnA \subset S_n is a conjugation-invariant set with ∣A∣=pn!≤n!/2|A| = pn! \leq n!/2, then the edge-boundary of AA in TnT_n has size at least c⋅log⁡2(1p)log⁡2log⁡2(2p)⋅n⋅∣A∣,c \cdot \frac {\log_2 (\tfrac 1{p})}{\log_2 \log_2 (\tfrac 2{p})}\cdot n \cdot |A|, where cc is an absolute constant. (This is sharp up to an absolute constant factor, when p=Θ(1/s!)p = Θ(1/s!) for any s∈{1,2,...,n}s \in \{1,2,...,n\}.) It follows that if p=n−Θ(1)p = n^{-Θ(1)}, then the edge-boundary of a conjugation-invariant set of measure pp is necessarily a factor of Ω(log⁡n/log⁡log⁡n)Ω(\log n / \log \log n) larger than the minimum edge-boundary over all sets of measure pp.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.