In this talk we describe two seemingly unrelated results on the symmetric group S_n.
A family F of permutations is called t-intersecting if any two permutations in F agree on at least t values. In 1977, Deza and Frankl conjectured that for all n>n_0(t), the maximal size of a t-intersecting subfamily of S_n is (n-t)!. Ellis, Friedgut and Pilpel (JAMS, 2011) proved the conjecture for all n>exp(exp(t)) and conjectured that it holds for all n>2t. We prove that the conjecture holds for all n>ct for some constant c.
A well-known problem asks for characterizing conjugacy classes A of S_n whose square A^2 contains (=""covers"") the alternating group A_n. We show that if A is of density at least exp(-n^{2/5-\epsilon}) then A^2 covers A_n. This extends a seminal result of Larsen and Shalev (Inventiones Math., 2008) who obtained the same with 1/4 in the double exponent.
The two results boil down to the understanding of independent sets in certain Cayley graphs, and turn out to be related. We shall discuss the main new tool we use in the proof of both results - hypercontractive inequalities for global functions, developed by Keevash, Lifshitz, Long and Minzer (JAMS, 2024).
Based on joint works with Noam Lifshitz, Dor Minzer, and Ohad Sheinfeld.
