A stability result for balanced dictatorships in Sn1. Issue 3 (7th August 2013) - Ellis, David; Filmus, Yuval; Friedgut, Ehud
<x xml:space="preserve">Abstract</x> We prove that a balanced Boolean function on Sn whose Fourier transform is highly concentrated on the first two irreducible representations of Sn, 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 Sn 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, [6] deals with Boolean functions of expectation O(1/ n) whose Fourier transform is highly concentrated on the first two irreducible representations of Sn. These need not be close to dictatorships; rather, they must be close to a union of a constant number of cosets of point‐stabilizers. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 494–530, 2015