Low-degree Boolean functions on S_n, with an application to isoperimetry

2015/11/27 by David Ellis, Ellis, David, Filmus, Yuval +2
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Combinatorial Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1511.08694

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!/\textrmpoly(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.

Related

• A quasi-stability result for dictatorships in S_n
• A stability result for balanced dictatorships in S_n
• Edge-isoperimetric inequalities and influences
• Isoperimetric inequalities in high-dimensional convex sets
• Bourgain's slicing problem and KLS isoperimetry up to polylog