# ALGEBRAIC COMBINATORICS

The Erdős–Ko–Rado theorem for 2-intersecting families of perfect matchings
Algebraic Combinatorics, Volume 4 (2021) no. 4, pp. 575-598.

A perfect matching in the complete graph on $2k$ vertices is a set of edges such that no two edges have a vertex in common and every vertex is covered exactly once. Two perfect matchings are said to be $t$-intersecting if they have at least $t$ edges in common. The main result in this paper is an extension of the famous Erdős–Ko–Rado (EKR) theorem [4] to 2-intersecting families of perfect matchings for all values of $k$. Specifically, for $k\ge 3$ a set of 2-intersecting perfect matchings in ${K}_{2k}$ of maximum size has $\left(2k-5\right)\left(2k-7\right)\cdots \left(1\right)$ perfect matchings.

Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/alco.169
Classification: 05E30,  05C50,  05C25
Keywords: Erdős–Ko–Rado Theorem, Perfect matchings, Association scheme, Ratio bound, Clique, Coclique, Quotient graphs, Character table.
@article{ALCO_2021__4_4_575_0,
author = {Fallat, Shaun and Meagher, Karen and Shirazi, Mahsa N.},
title = {The {Erd\H{o}s{\textendash}Ko{\textendash}Rado} theorem for 2-intersecting families of perfect matchings},
journal = {Algebraic Combinatorics},
pages = {575--598},
publisher = {MathOA foundation},
volume = {4},
number = {4},
year = {2021},
doi = {10.5802/alco.169},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.169/}
}
TY  - JOUR
AU  - Fallat, Shaun
AU  - Meagher, Karen
AU  - Shirazi, Mahsa N.
TI  - The Erdős–Ko–Rado theorem for 2-intersecting families of perfect matchings
JO  - Algebraic Combinatorics
PY  - 2021
DA  - 2021///
SP  - 575
EP  - 598
VL  - 4
IS  - 4
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.169/
UR  - https://doi.org/10.5802/alco.169
DO  - 10.5802/alco.169
LA  - en
ID  - ALCO_2021__4_4_575_0
ER  - 
Fallat, Shaun; Meagher, Karen; Shirazi, Mahsa N. The Erdős–Ko–Rado theorem for 2-intersecting families of perfect matchings. Algebraic Combinatorics, Volume 4 (2021) no. 4, pp. 575-598. doi : 10.5802/alco.169. https://alco.centre-mersenne.org/articles/10.5802/alco.169/

[1] Ahlswede, Rudolf; Khachatrian, Levon H. The complete intersection theorem for systems of finite sets, European J. Combin., Volume 18 (1997) no. 2, pp. 125-136 | Article | MR 1429238 | Zbl 0869.05066

[2] Cameron, Peter J.; Ku, Cheng Yeaw Intersecting families of permutations, European J. Combin., Volume 24 (2003) no. 7, pp. 881-890 | Article | MR 2009400 | Zbl 1026.05001

[3] Ellis, David; Friedgut, Ehud; Pilpel, Haran Intersecting families of permutations, J. Amer. Math. Soc., Volume 24 (2011) no. 3, pp. 649-682 | Article | MR 2784326 | Zbl 1285.05171

[4] Erdős, Pál; Ko, Chao; Rado, Richard Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), Volume 12 (1961), pp. 313-320 | Article | MR 140419 | Zbl 0100.01902

[5] GAP – Groups, Algorithms, and Programming, Version 4.11.0 (2020) (https://www.gap-system.org)

[6] Godsil, Chris; Guo, Krystal Using the existence of $t$-designs to prove Erdős–Ko–Rado, Discrete Math., Volume 342 (2019) no. 10, pp. 2846-2849 | Article | MR 3990672 | Zbl 1417.05237

[7] Godsil, Chris; Meagher, Karen Erdős–Ko–Rado theorems: algebraic approaches, Cambridge Studies in Advanced Mathematics, 149, Cambridge University Press, Cambridge, 2016, xvi+335 pages | Article | MR 3497070 | Zbl 1343.05002

[8] Godsil, Chris; Meagher, Karen An algebraic proof of the Erdős–Ko–Rado theorem for intersecting families of perfect matchings, Ars Math. Contemp., Volume 12 (2017) no. 2, pp. 205-217 | Article | MR 3646689 | Zbl 1370.05102

[9] Godsil, Chris; Royle, Gordon Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | Article | MR 1829620 | Zbl 0968.05002

[10] Gurobi Optimization, LLC Gurobi Optimizer Reference Manual (2021) (http://www.gurobi.com)

[11] Ku, Cheng Yeaw; Wales, David B. Eigenvalues of the derangement graph, J. Combin. Theory Ser. A, Volume 117 (2010) no. 3, pp. 289-312 | Article | MR 2592902 | Zbl 1209.05145

[12] Lindzey, Nathan Erdős–Ko–Rado for perfect matchings, European J. Combin., Volume 65 (2017), pp. 130-142 | Article | MR 3679841 | Zbl 1369.05173

[13] Meagher, Karen; Moura, Lucia Erdős–Ko–Rado theorems for uniform set-partition systems, Electron. J. Combin., Volume 12 (2005), Paper no. Research Paper 40, 12 pages | MR 2156694 | Zbl 1075.05086

[14] Muzychuk, Mikhail On association schemes of the symmetric group ${S}_{2n}$acting on partitions of type ${2}^{n}$, Bayreuth. Math. Schr. (1994) no. 47, pp. 151-164 | MR 1285207 | Zbl 0817.05080

[15] Rasala, Richard On the minimal degrees of characters of ${S}_{n}$, J. Algebra, Volume 45 (1977) no. 1, pp. 132-181 | Article | MR 427445 | Zbl 0348.20009

[16] Srinivasan, Murali K. A Maple program for computing ${\stackrel{^}{\theta }}_{2\mu }^{2\lambda }$ (2018) (http://www.math.iitb.ac.in/~mks/papers/EigenMatch.pdf)

[17] Srinivasan, Murali K. The perfect matching association scheme, Algebr. Comb., Volume 3 (2020) no. 3, pp. 559-591 | Article | MR 4113598 | Zbl 1441.05240

[18] Tanaka, Hajime The Erdős–Ko–Rado theorem for twisted Grassmann graphs, Combinatorica, Volume 32 (2012) no. 6, pp. 735-740 | Article | MR 3063159 | Zbl 1299.05313

[19] Wallis, Walter D. Introduction to combinatorial designs, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007, xvi+311 pages | Article | MR 2323153 | Zbl 1126.05001

[20] Wilson, Richard M. The exact bound in the Erdős–Ko–Rado theorem, Combinatorica, Volume 4 (1984) no. 2-3, pp. 247-257 | Article | MR 771733 | Zbl 0556.05039

Cited by Sources: