Intersecting families of permutations

Ellis, David^1, 2 ; Friedgut, Ehud³ ; Pilpel, Haran^4, 5

¹ Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB England
² St John’s College, Cambridge, CB2 1TP, United Kingdom
³ Department of Mathematics, Hebrew University, 91904 Jerusalem, Israel, and Department of Mathematics, University of Toronto, 40 St. George Street, Toronto, Ontario M5S 2E4, Canada
⁴ Department of Mathematics, Hebrew University, 91904 Jerusalem, Israel
⁵ Google, Inc., Levinstein Tower 26th Floor, 23 Manachem Begin St, 66183 Tel Aviv, Israel

Journal of the American Mathematical Society, Tome 24 (2011) no. 3, pp. 649-682

Résumé

A set of permutations $I \subset S_n$ is said to be $k$-intersecting if any two permutations in $I$ agree on at least $k$ points. We show that for any $k \in \mathbb {N}$, if $n$ is sufficiently large depending on $k$, then the largest $k$-intersecting subsets of $S_n$ are cosets of stabilizers of $k$ points, proving a conjecture of Deza and Frankl. We also prove a similar result concerning $k$-cross-intersecting subsets. Our proofs are based on eigenvalue techniques and the representation theory of the symmetric group.

Détail

DOI : 10.1090/S0894-0347-2011-00690-5

Bibliographie

[1] Ahlswede, Rudolf, Khachatrian, Levon H. The complete intersection theorem for systems of finite sets European J. Combin. 1997 125 136

[2] Alon, Noga, Kaplan, Haim, Krivelevich, Michael, Malkhi, Dahlia, Stern, Julien Scalable secure storage when half the system is faulty 2000 576 587

[3] Babai, Lã¡Szlã³ Spectra of Cayley graphs J. Combin. Theory Ser. B 1979 180 189

[4] Birkhoff, Garrett Three observations on linear algebra Univ. Nac. Tucumán. Revista A. 1946 147 151

[5] Bourgain, J. On the distributions of the Fourier spectrum of Boolean functions Israel J. Math. 2002 269 276

[6] Cameron, Peter J., Ku, C. Y. Intersecting families of permutations European J. Combin. 2003 881 890

[7] Diaconis, Persi, Shahshahani, Mehrdad Generating a random permutation with random transpositions Z. Wahrsch. Verw. Gebiete 1981 159 179

[8] Frame, J. S., Robinson, G. De B., Thrall, R. M. The hook graphs of the symmetric groups Canad. J. Math. 1954 316 324

[9] Frankl, Pã©Ter, Deza, Mikhail On the maximum number of permutations with given maximal or minimal distance J. Combinatorial Theory Ser. A 1977 352 360

[10] Friedgut, Ehud Boolean functions with low average sensitivity depend on few coordinates Combinatorica 1998 27 35

[11] Friedgut, Ehud, Kalai, Gil, Naor, Assaf Boolean functions whose Fourier transform is concentrated on the first two levels Adv. in Appl. Math. 2002 427 437

[12] Godsil, Chris, Meagher, Karen A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations European J. Combin. 2009 404 414

[13] Hardy, G. H., Littlewood, J. E., Pã³Lya, G. Inequalities 1988

[14] Hilton, A. J. W., Milner, E. C. Some intersection theorems for systems of finite sets Quart. J. Math. Oxford Ser. (2) 1967 369 384

[15] Hoffman, Alan J. On eigenvalues and colorings of graphs 1970 79 91

[16] Isaacs, I. Martin Character theory of finite groups 1976

[17] Larose, Benoit, Malvenuto, Claudia Stable sets of maximal size in Kneser-type graphs European J. Combin. 2004 657 673

[18] Mishchenko, S. P. Lower bounds on the dimensions of irreducible representations of symmetric groups and of the exponents of the exponential of varieties of Lie algebras Mat. Sb. 1996 83 94

[19] Renteln, Paul On the spectrum of the derangement graph Electron. J. Combin. 2007

[20] Roichman, Yuval Upper bound on the characters of the symmetric groups Invent. Math. 1996 451 485

[21] Sagan, Bruce E. The symmetric group 2001

[22] Serre, Jean-Pierre Linear representations of finite groups 1977