Low-degree Boolean functions on S_n, with an application to isoperimetry
Forum of Mathematics, Sigma
MetadataShow full item record
We prove that Boolean functions on Sn, 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 Sn which is asymptotically sharp for subsets of Sn of size n!/poly(n), using eigenvalue techniques. We then combine these two results to obtain a sharp edge-isoperimetric inequality for subsets of Sn of size (n − t)!, where n is large compared to t, confirming a conjecture of Ben Efraim in these cases.
AuthorsELLIS, DC; Filmus, Y; Friedgut, E
- College Publications