A stability result for balanced dictatorships in S_{n}

Authors David Ellis, Yuval Filmus, Ehud Friedgut

Publication date 15 October 2012

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 page was built for publication: A stability result for balanced dictatorships in $S_{n}$

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