×

zbMATH — the first resource for mathematics

Erdős-Ko-Rado for perfect matchings. (English) Zbl 1369.05173
Summary: A perfect matching of a complete graph \(K_{2 n}\) is a 1-regular subgraph that contains all the vertices. Two perfect matchings intersect if they share an edge. It is known that if \(\mathcal{F}\) is family of intersecting perfect matchings of \(K_{2 n}\), then \(|\mathcal{F}| \leq(2(n-1)-1)!!\) and if equality holds, then \(\mathcal{F} = \mathcal{F}_{ij}\) where \(\mathcal{F}_{ij}\) is the family of all perfect matchings of \(K_{2 n}\) that contain some fixed edge \(ij\). We give a short algebraic proof of this result, resolving a question of C. D. Godsil and K. Meagher [ibid. 30, No. 2, 404–414 (2009; Zbl 1177.05010)]. Along the way, we show that if a family \(\mathcal{F}\) is non-Hamiltonian, that is, \(m\cup m^\prime \ncong C_{2 n}\) for any \(m\), \(m^\prime \in \mathcal{F}\), then \(|\mathcal{F}| \leq(2(n-1)-1)!!\). Our results make ample use of a symmetric commutative association scheme arising from the Gelfand pair \((S_{2 n}, S_2 \wr S_n)\). We give an exposition of a few new interesting objects that live in this scheme as they pertain to our results.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
Software:
GAP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmadi, Bahman, Maximum Intersecting Families of Permutations (Ph.D. thesis), (2013), University of Regina
[2] Bannai, E.; Ito, T., (Algebraic Combinatorics I: Association Schemes, Mathematics Lecture Note Series, (1984), Benjamin/Cummings Pub. Co.) · Zbl 0555.05019
[3] Berge, Claude, Two theorems in graph theory, Proc. Natl. Acad. Sci., 43, 9, 842-844, (1957) · Zbl 0086.16202
[4] Diaconis, Persi, (Group Representations in Probability and Statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, (1988), Institute of Mathematical Statistics Hayward, CA), vi+198 · Zbl 0695.60012
[5] Edmonds, Jack, Paths, trees, and flowers, Canad. J. Math., 17, 449-467, (1965) · Zbl 0132.20903
[6] Edmonds, J.; Pulleyblank, W. R.; Lovász, L., Brick decompositions and the matching rank of graphs, Combinatorica, 2, 3, 247-274, (1982) · Zbl 0521.05035
[7] Ellis, D.; Friedgut, E.; Pilpel, H., Intersecting families of permutations, J. Amer. Math. Soc., 24, 649-682, (2011) · Zbl 1285.05171
[8] Frankl, Peter; Deza, Mikhail, On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory Ser. A, 22, 3, 352-360, (1977) · Zbl 0352.05003
[9] The GAP Group, GAP -Groups,Algorithms, and Programming, Version 4.7.5, 2014. http://www.gap-system.org
[10] Godsil, Chris; Meagher, Karen, Multiplicity-free permutation representations of the symmetric group, Ann. Comb., 13, 4, 463-490, (2010) · Zbl 1234.20015
[11] Godsil, Chris; Royle, Gordon, Algebraic graph theory, Graduate Texts in Mathematics, xx+439, (2001), Springer-Verlag New York · Zbl 0968.05002
[12] Godsil, Chris D.; Meagher, Karen, A new proof of the Erdös-ko-Rado theorem for intersecting families of permutations, European J. Combin., 30, 2, 404-414, (2009) · Zbl 1177.05010
[13] Královič, Rastislav; Královič, Richard, On semi-perfect 1-factorizations, (Proceedings of the 12th International Conference on Structural Information and Communication Complexity, SIROCCO’05, (2005), Springer-Verlag Berlin, Heidelberg), 216-230 · Zbl 1086.05061
[14] Ku, Cheng Yeaw; Wales, David B., Eigenvalues of the derangement graph, J. Combin. Theory Ser. A, 117, 3, 289-312, (2010) · Zbl 1209.05145
[15] Ku, Cheng Yeaw; Wong, Kok Bin, Solving the ku-wales conjecture on the eigenvalues of the derangement graph, European J. Combin., 34, 6, 941-956, (2013) · Zbl 1285.05116
[16] Lucas, E., Récréations mathématiques, Récréations mathématiques, (1892), A. Blanchard · JFM 15.0158.01
[17] Macdonald, I. G., Symmetric functions and Hall polynomials, Oxford mathematical monographs, (1995), Clarendon Press · Zbl 0487.20007
[18] Meagher, Karen; Moura, Lucia, Erdös-ko-Rado theorems for uniform set-partition systems, Electron. J. Combin., 12, 1, (2005), Research Paper 40, 12 pp. (electronic) · Zbl 1075.05086
[19] Newman, Michael, Independent Sets and Eigenspaces (Ph.D. thesis), (2004), University of Waterloo
[20] Pak, I., Four questions on the Birkhoff polytope, Ann. Comb., 4, 1, 83-90, (2000) · Zbl 0974.52010
[21] Polster, Burkard, Abstract hyperovals and Hadamard designs, Australas. J. Combin., 16, 29-33, (1997) · Zbl 0889.51010
[22] Renteln, Paul, On the spectrum of the derangement graph, Electron. J. Combin., 14, 1, (2007), Research Paper 82, 17 pp. (electronic) · Zbl 1183.05047
[23] Rooney, Brendan, Spectral Aspects of Cocliques in Graphs (Ph.D. thesis), (2014), University of Waterloo
[24] Rothvoß, Thomas, The matching polytope has exponential extension complexity, (STOC, (2014)), 263-272 · Zbl 1315.90038
[25] Thrall, R. M., On symmetrized Kronecker powers and the structure of the free Lie ring, Amer. J. Math., 64, 1, 371-388, (1942) · Zbl 0061.04201
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.