A stability result for balanced dictatorships in Sn1. Issue 3 (7th August 2013)

• Record Type: Journal Article
• Authors: Ellis, David; Filmus, Yuval; Friedgut, Ehud
• Is Part Of: Random structures & algorithms. Volume 46:Issue 3(2015)
• Page Start: 494
• Page End: 530
• Publication Date: 2013-08-07
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20515
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>We prove that a balanced Boolean function on <italic>S</italic>_{<italic>n</italic>} whose Fourier transform is highly concentrated on the first two irreducible representations of <italic>S</italic>_{<italic>n</italic>}, 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 <italic>S</italic>_{<italic>n</italic>} generated by the transpositions.</p> <p>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 <italic>O</italic>(1/ <italic>n</italic>) whose Fourier transform is highly concentrated on the first two irreducible representations of <italic>S</italic>_{<italic>n</italic>}. 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</p> </abstract>