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

DOI10.1007/S11856-016-1296-7MaRDI QIDQ2630863zbMATH OpenOpenAlexFDO

Authors Neta Atzmon, David Ellis, Dmitry Kogan

Publication date 22 July 2016

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4542

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: We prove an isoperimetric inequality for conjugation-invariant sets of size $k$ in $S_n$, showing that these necessarily have edge-boundary considerably larger than some other sets of size $k$ (provided $k$ is small). Specifically, let $T_n$ denote the Cayley graph on $S_n$ generated by the set of all transpositions. We show that if $Asubset{S}_n$ is a conjugation-invariant set with $|A|=pn!leqn!/2$, then the edge-boundary of $A$ in $T_n$ has size at least ${\displaystyle }$c cdot frac {log_2 ( frac 1{p})}{log_2 log_2 ( frac 2{p})}cdot n cdot |A|,${\displaystyle }$ where $c$ is an absolute constant. (This is sharp up to an absolute constant factor, when $p=Theta(1/s!)$ for any $sin1,2,\mathrm{...},n$.) It follows that if $p=n^{-Theta(1)}$, then the edge-boundary of a conjugation-invariant set of measure $p$ is necessarily a factor of $Omega(logn/loglogn)$ larger than the minimum edge-boundary over all sets of measure $p$.

Recommendations

• LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY
• Bounds on the diameter of Cayley graphs of the symmetric group
• Aldous's spectral gap conjecture for normal sets
• A curved Brunn-Minkowski inequality for the symmetric group
• Conjugation diameter of the symmetric groups

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A note on the edges of the n-cube
• A quasi-stability result for dictatorships in S_n
• Assignment of Numbers to Vertices
• Generating a random permutation with random transpositions
• scientific article; zbMATH DE number 3771876 (Why is no real title available?)
• scientific article; zbMATH DE number 18980 (Why is no real title available?)
• Logarithmic combinatorial structures: A probabilistic approach
• Maximally Connected Arrays on the n-Cube
• Optimal Assignments of Numbers to Vertices

Cited in

(3)

• A curved Brunn-Minkowski inequality for the symmetric group
• Broué's perfect isometry conjecture holds for the double covers of the symmetric and alternating groups
• Isoperimetric profile and resistance diameters of Cayley graphs on symmetric groups with Coxeter generating sets

This page was built for publication: An isoperimetric inequality for conjugation-invariant sets in the symmetric group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2630863)