Intersecting families of permutations

Ellis, David; Friedgut, Ehud; Pilpel, Haran

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

Intersecting families of permutations
HTML articles powered by AMS MathViewer

by David Ellis, Ehud Friedgut and Haran Pilpel

J. Amer. Math. Soc. 24 (2011), 649-682

DOI: https://doi.org/10.1090/S0894-0347-2011-00690-5

Published electronically: January 31, 2011

PDF | 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, DOI 10.37236/1000
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