Juntas, stability and isoperimetric inequalities in the symmetric group

Juntas, stability and isoperimetric inequalities in the symmetric group

Tue, 05/02
14:30 		David Ellis (Queen Mary) Combinatorial Theory Seminar Add to calendar L3
Juntas, stability and isoperimetric inequalities in the symmetric group
Results of Bourgain and Kindler-Safra state that if $ f $ is a Boolean function on $ \{0,1\}^n $, and the Fourier transform of $ f $ is highly concentrated on low frequencies, then $ f $ must be close to a ‘junta’ (a function depending upon a small number of coordinates). This phenomenon is known as ‘Fourier stability’, and has several interesting consequences in combinatorics, theoretical computer science and social choice theory. We will describe some of these, before turning to the analogous question for Boolean functions on the symmetric group. Here, genuine stability does not occur; it is replaced by a weaker phenomenon, which we call ‘quasi-stability’. We use our 'quasi-stability' result to prove an isoperimetric inequality for $ S_n $ which is sharp for sets of size $ (n-t)! $, when $ n $ is large. Several open questions remain. Joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Weizmann Institute).