pith. sign in

arxiv: 1210.3989 · v4 · pith:HKRRMO5Dnew · submitted 2012-10-15 · 🧮 math.CO

A stability result for balanced dictatorships in S_(n)

classification 🧮 math.CO
keywords closedictatorshipsfunctionresultbalancedbooleanconcentratedexpectation
0
0 comments X
read the original abstract

We prove that a balanced Boolean function on $S_{n}$ whose Fourier transform is highly concentrated on the first two irreducible representations of $S_{n}$, is close in structure to a dictatorship, a function which is determined by the image or pre-image of a single element. As a corollary, we obtain a stability result concerning extremal isoperimetric sets in the Cayley graph on $S_{n}$ generated by the transpositions. Our proof works in the case where the expectation of the function is bounded away from $0$ and $1$. In contrast, [Ellis, D., Filmus, Y., Friedgut, E., A quasi-stability result for dictatorships in $S_{n}$, Combinatorica 35 (2015), pp. 573-618] deals with Boolean functions of expectation O(1/n) whose Fourier transform is highly concentrated on the first two irreducible representations of $S_{n}$. These need not be close to dictatorships; rather, they must be close to a union of a constant number of cosets of point-stabilizers.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.