## Intersecting families of permutations

HTML articles powered by AMS MathViewer

- by David Ellis, Ehud Friedgut and Haran Pilpel PDF
- J. Amer. Math. Soc.
**24**(2011), 649-682 Request permission

## Abstract:

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.

## References

- Rudolf Ahlswede and Levon H. Khachatrian,
*The complete intersection theorem for systems of finite sets*, European J. Combin.**18**(1997), no. 2, 125–136. MR**1429238**, DOI 10.1006/eujc.1995.0092 - Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, and Julien Stern,
*Scalable secure storage when half the system is faulty*, Automata, languages and programming (Geneva, 2000) Lecture Notes in Comput. Sci., vol. 1853, Springer, Berlin, 2000, pp. 576–587. MR**1795918**, DOI 10.1007/3-540-45022-X_{4}9 - László Babai,
*Spectra of Cayley graphs*, J. Combin. Theory Ser. B**27**(1979), no. 2, 180–189. MR**546860**, DOI 10.1016/0095-8956(79)90079-0 - Garrett Birkhoff,
*Three observations on linear algebra*, Univ. Nac. Tucumán. Revista A.**5**(1946), 147–151 (Spanish). MR**0020547** - J. Bourgain,
*On the distributions of the Fourier spectrum of Boolean functions*, Israel J. Math.**131**(2002), 269–276. MR**1942312**, DOI 10.1007/BF02785861 - Peter J. Cameron and C. Y. Ku,
*Intersecting families of permutations*, European J. Combin.**24**(2003), no. 7, 881–890. MR**2009400**, DOI 10.1016/S0195-6698(03)00078-7 - Persi Diaconis and Mehrdad Shahshahani,
*Generating a random permutation with random transpositions*, Z. Wahrsch. Verw. Gebiete**57**(1981), no. 2, 159–179. MR**626813**, DOI 10.1007/BF00535487 - David Ellis. Stability for
*t*-intersecting families of permutations. To appear in*Journal of Combinatorial Theory, Series A*. - J. S. Frame, G. de B. Robinson, and R. M. Thrall,
*The hook graphs of the symmetric groups*, Canad. J. Math.**6**(1954), 316–324. MR**62127**, DOI 10.4153/cjm-1954-030-1 - Péter Frankl and Mikhail Deza,
*On the maximum number of permutations with given maximal or minimal distance*, J. Combinatorial Theory Ser. A**22**(1977), no. 3, 352–360. MR**439648**, DOI 10.1016/0097-3165(77)90009-7 - Ehud Friedgut,
*Boolean functions with low average sensitivity depend on few coordinates*, Combinatorica**18**(1998), no. 1, 27–35. MR**1645642**, DOI 10.1007/PL00009809 - Ehud Friedgut, Gil Kalai, and Assaf Naor,
*Boolean functions whose Fourier transform is concentrated on the first two levels*, Adv. in Appl. Math.**29**(2002), no. 3, 427–437. MR**1942632**, DOI 10.1016/S0196-8858(02)00024-6 - Ehud Friedgut and Haran Pilpel. Intersecting families of permutations: An algebraic approach. Talk given at the Oberwolfach Conference in Combinatorics, January 2008.
- Chris Godsil and Karen Meagher,
*A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations*, European J. Combin.**30**(2009), no. 2, 404–414. MR**2489272**, DOI 10.1016/j.ejc.2008.05.006 - G. H. Hardy, J. E. Littlewood, and G. Pólya,
*Inequalities*, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988. Reprint of the 1952 edition. MR**944909** - A. J. W. Hilton and E. C. Milner,
*Some intersection theorems for systems of finite sets*, Quart. J. Math. Oxford Ser. (2)**18**(1967), 369–384. MR**219428**, DOI 10.1093/qmath/18.1.369 - Alan J. Hoffman,
*On eigenvalues and colorings of graphs*, Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969) Academic Press, New York, 1970, pp. 79–91. MR**0284373** - I. Martin Isaacs,
*Character theory of finite groups*, Pure and Applied Mathematics, No. 69, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1976. MR**0460423** - C. Jordan.
*Traité des Substitutions et des Equations Algébriques*. Gauthier-Villars, Paris, 1870. - Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on Boolean functions (extended abstract). In
*FOCS*, pages 68–80. IEEE, 1988. - Benoit Larose and Claudia Malvenuto,
*Stable sets of maximal size in Kneser-type graphs*, European J. Combin.**25**(2004), no. 5, 657–673. MR**2061391**, DOI 10.1016/j.ejc.2003.10.006 - Imre Leader. Open Problems Session, British Combinatorial Conference, 2005.
- Jiří Matoušek and Bernd Gärtner.
*Understanding and Using Linear Programming*. Springer-Verlag, Berlin, 2007. - S. P. Mishchenko,
*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.**187**(1996), no. 1, 83–94 (Russian, with Russian summary); English transl., Sb. Math.**187**(1996), no. 1, 81–92. MR**1380205**, DOI 10.1070/SM1996v187n01ABEH000101 - Paul Renteln,
*On the spectrum of the derangement graph*, Electron. J. Combin.**14**(2007), no. 1, Research Paper 82, 17. MR**2365981** - Yuval Roichman,
*Upper bound on the characters of the symmetric groups*, Invent. Math.**125**(1996), no. 3, 451–485. MR**1400314**, DOI 10.1007/s002220050083 - Bruce E. Sagan,
*The symmetric group*, 2nd ed., Graduate Texts in Mathematics, vol. 203, Springer-Verlag, New York, 2001. Representations, combinatorial algorithms, and symmetric functions. MR**1824028**, DOI 10.1007/978-1-4757-6804-6 - Jean-Pierre Serre,
*Linear representations of finite groups*, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott. MR**0450380**, DOI 10.1007/978-1-4684-9458-7

## Additional Information

**David Ellis**- Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB England
- Address at time of publication: St John’s College, Cambridge, CB2 1TP, United Kingdom
**Ehud Friedgut**- Affiliation: Department of Mathematics, Hebrew University, 91904 Jerusalem, Israel, and Department of Mathematics, University of Toronto, 40 St. George Street, Toronto, Ontario M5S 2E4, Canada
**Haran Pilpel**- Affiliation: Department of Mathematics, Hebrew University, 91904 Jerusalem, Israel
- Address at time of publication: Google, Inc., Levinstein Tower 26th Floor, 23 Manachem Begin St, 66183 Tel Aviv, Israel
- Received by editor(s): March 9, 2009
- Received by editor(s) in revised form: November 15, 2010, and December 8, 2010
- Published electronically: January 31, 2011
- Additional Notes: Research of the second author was supported in part by the Israel Science Foundation, grant no. 0397684, and NSERC grant 341527.

Research of the third author was supported in part by the Giora Yoel Yashinsky Memorial Grant. - © Copyright 2011
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc.
**24**(2011), 649-682 - MSC (2010): Primary 05E10, 20C30, 05D99
- DOI: https://doi.org/10.1090/S0894-0347-2011-00690-5
- MathSciNet review: 2784326