Intersecting families of permutations. (English) Zbl 1285.05171
Summary: 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.
MSC:
| 05D10 | Ramsey theory |
| 05A05 | Permutations, words, matrices |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05E10 | Combinatorial aspects of representation theory |
| 20C30 | Representations of finite symmetric groups |
References:
| [1] | Rudolf Ahlswede and Levon H. Khachatrian, The complete intersection theorem for systems of finite sets, European J. Combin. 18 (1997), no. 2, 125 – 136. · Zbl 0869.05066 · doi:10.1006/eujc.1995.0092 |
| [2] | 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. · Zbl 0973.68610 · doi:10.1007/3-540-45022-X_49 |
| [3] | László Babai, Spectra of Cayley graphs, J. Combin. Theory Ser. B 27 (1979), no. 2, 180 – 189. · Zbl 0338.05110 · doi:10.1016/0095-8956(79)90079-0 |
| [4] | Garrett Birkhoff, Three observations on linear algebra, Univ. Nac. Tucumán. Revista A. 5 (1946), 147 – 151 (Spanish). · Zbl 0060.07906 |
| [5] | J. Bourgain, On the distributions of the Fourier spectrum of Boolean functions, Israel J. Math. 131 (2002), 269 – 276. · Zbl 1021.43004 · doi:10.1007/BF02785861 |
| [6] | Peter J. Cameron and C. Y. Ku, Intersecting families of permutations, European J. Combin. 24 (2003), no. 7, 881 – 890. · Zbl 1026.05001 · doi:10.1016/S0195-6698(03)00078-7 |
| [7] | Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159 – 179. · Zbl 0485.60006 · doi:10.1007/BF00535487 |
| [8] | David Ellis. Stability for t-intersecting families of permutations. To appear in Journal of Combinatorial Theory, Series A. · Zbl 1234.05229 |
| [9] | J. S. Frame, G. de B. Robinson, and R. M. Thrall, The hook graphs of the symmetric groups, Canadian J. Math. 6 (1954), 316 – 324. · Zbl 0055.25404 |
| [10] | 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. · Zbl 0352.05003 |
| [11] | Ehud Friedgut, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica 18 (1998), no. 1, 27 – 35. · Zbl 0909.06008 · doi:10.1007/PL00009809 |
| [12] | 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. · Zbl 1039.91014 · doi:10.1016/S0196-8858(02)00024-6 |
| [13] | Ehud Friedgut and Haran Pilpel. Intersecting families of permutations: An algebraic approach. Talk given at the Oberwolfach Conference in Combinatorics, January 2008. · Zbl 1285.05171 |
| [14] | 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. · Zbl 1177.05010 · doi:10.1016/j.ejc.2008.05.006 |
| [15] | G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988. Reprint of the 1952 edition. · Zbl 0634.26008 |
| [16] | 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. · Zbl 0168.26205 · doi:10.1093/qmath/18.1.369 |
| [17] | 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. |
| [18] | I. Martin Isaacs, Character theory of finite groups, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1976. Pure and Applied Mathematics, No. 69. · Zbl 0337.20005 |
| [19] | C. Jordan. Traité des Substitutions et des Equations Algébriques. Gauthier-Villars, Paris, 1870. · Zbl 0828.01011 |
| [20] | Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on Boolean functions (extended abstract). In FOCS, pages 68-80. IEEE, 1988. |
| [21] | Benoit Larose and Claudia Malvenuto, Stable sets of maximal size in Kneser-type graphs, European J. Combin. 25 (2004), no. 5, 657 – 673. · Zbl 1048.05078 · doi:10.1016/j.ejc.2003.10.006 |
| [22] | Imre Leader. Open Problems Session, British Combinatorial Conference, 2005. |
| [23] | Jiří Matoušek and Bernd Gärtner. Understanding and Using Linear Programming. Springer-Verlag, Berlin, 2007. · Zbl 1133.90001 |
| [24] | 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. · Zbl 0873.17007 · doi:10.1070/SM1996v187n01ABEH000101 |
| [25] | Paul Renteln, On the spectrum of the derangement graph, Electron. J. Combin. 14 (2007), no. 1, Research Paper 82, 17. · Zbl 1183.05047 |
| [26] | Yuval Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), no. 3, 451 – 485. · Zbl 0854.20015 · doi:10.1007/s002220050083 |
| [27] | 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. · Zbl 0964.05070 |
| [28] | Jean-Pierre Serre, Linear representations of finite groups, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott; Graduate Texts in Mathematics, Vol. 42. · Zbl 0355.20006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
