A quasi-stability result for dictatorships in \(S_n\) (Q519995)

The authors prove that Boolean functions on \(S_n\), whose Fourier transform are highly concentrated on the first two irreducible representations of \(S_n\), are close to being unions of cosets of point-stabilizers. Two main applications are given. The first is a new and natural proof of a conjecture of \textit{P. J. Cameron} and \textit{C. Y. Ku} [Eur. J. Comb. 24, No. 7, 881--890 (2003; Zbl 1026.05001)] that was originally proved by the first author [J. Lond. Math. Soc., II. Ser. 85, No. 1, 165--190 (2012; Zbl 1235.05003)]. The result states as follows. There exists \(\delta > 0\) such that, for all \(n \in \mathbb N\), if \(\mathcal A\subset S_n\) is an intersecting family of permutations, i.e., any two permutations in \(\mathcal A\) agree at some point, with \(\mathcal A \geq (1-\delta)(n-1)!\), then A is contained within a point-stabilizer of \(S_n\). The second is a result stating that subsets of \(S_n\) with small edge-boundary in the transposition graph are close to being unions of cosets of point-stabilizers. The paper ends with two conjectures strengthening the main theorem and the second application.