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 $(2k-5)(2k-7)\cdots \left(1\right)$ perfect matchings.

Revised:

Accepted:

Published online:

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/} }

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] 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] Intersecting families of permutations, European J. Combin., Volume 24 (2003) no. 7, pp. 881-890 | Article | MR 2009400 | Zbl 1026.05001

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

[4] 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] 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] 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] 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] Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | Article | MR 1829620 | Zbl 0968.05002

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

[11] 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] Erdős–Ko–Rado for perfect matchings, European J. Combin., Volume 65 (2017), pp. 130-142 | Article | MR 3679841 | Zbl 1369.05173

[13] 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] 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] 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] A Maple program for computing ${\widehat{\theta}}_{2\mu}^{2\lambda}$ (2018) (http://www.math.iitb.ac.in/~mks/papers/EigenMatch.pdf)

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

[18] 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] 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] 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