A Stability Result for Balanced Dictatorships in S-n

作者：Ellis David^*; Filmus Yuval; Friedgut Ehud

来源：Random Structures and Algorithms, 2015, 46(3): 494-530.

DOI：10.1002/rsa.20515

• Fourier transform
• stability
• symmetric group

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, [6] 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.

• 出版日期2015-5