Combinatorics Seminar

When: Sunday, May 4, 10am Where: Schreiber 309 Speaker: Haran Pilpel, Hebrew University, Title: Intersecting families of permutations

Abstract:

Two permutations in S_n are 1-intersecting if they agree on some point. A subset A of S_n is 1-intersecting if every two elements are 1-intersecting. The maximal measure of a 1-intersecting family is 1/n (Deza-Frankl) and all such families are known (Cameron-Ku, Larose-Malvenuto.)

We study families which are almost maximal, i.e. have measure almost 1/n. To get stability results, the natural instrument is Fourier analysis. Since S_n is nonabelian, we need to understand its irreducible representations. We characterize all 1-intersecting families of measure > 1/n - 1/n^6.

Joint work with Ehud Friedgut.