Article contents
LOW-DEGREE BOOLEAN FUNCTIONS ON
$S_{n}$, WITH AN APPLICATION TO ISOPERIMETRY
Published online by Cambridge University Press: 03 October 2017
Abstract
We prove that Boolean functions on $S_{n}$, whose Fourier transform is highly concentrated on irreducible representations indexed by partitions of
$n$ whose largest part has size at least
$n-t$, are close to being unions of cosets of stabilizers of
$t$-tuples. We also obtain an edge-isoperimetric inequality for the transposition graph on
$S_{n}$ which is asymptotically sharp for subsets of
$S_{n}$ of size
$n!/\text{poly}(n)$, using eigenvalue techniques. We then combine these two results to obtain a sharp edge-isoperimetric inequality for subsets of
$S_{n}$ of size
$(n-t)!$, where
$n$ is large compared to
$t$, confirming a conjecture of Ben Efraim in these cases.
MSC classification
- Type
- Research Article
- Information
- Creative Commons
- This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
- Copyright
- © The Author(s) 2017
References
- 4
- Cited by