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:

Keywords: Erdős–Ko–Rado Theorem, Perfect matchings, Association scheme, Ratio bound, Clique, Coclique, Quotient graphs, Character table.

Fallat, Shaun ^{1};
Meagher, Karen ^{1};
Shirazi, Mahsa N. ^{1}

@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 SP - 575 EP - 598 VL - 4 IS - 4 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.169/ DO - 10.5802/alco.169 LA - en ID - ALCO_2021__4_4_575_0 ER -

%0 Journal Article %A Fallat, Shaun %A Meagher, Karen %A Shirazi, Mahsa N. %T The Erdős–Ko–Rado theorem for 2-intersecting families of perfect matchings %J Algebraic Combinatorics %D 2021 %P 575-598 %V 4 %N 4 %I MathOA foundation %U https://alco.centre-mersenne.org/articles/10.5802/alco.169/ %R 10.5802/alco.169 %G en %F ALCO_2021__4_4_575_0

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 | DOI | MR | Zbl

[2] Intersecting families of permutations, European J. Combin., Volume 24 (2003) no. 7, pp. 881-890 | DOI | MR | Zbl

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

[4] Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), Volume 12 (1961), pp. 313-320 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[7] Erdős–Ko–Rado theorems: algebraic approaches, Cambridge Studies in Advanced Mathematics, 149, Cambridge University Press, Cambridge, 2016, xvi+335 pages | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[9] Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | Zbl

[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 | Zbl

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

[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 | DOI | MR | Zbl

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

[19] Introduction to combinatorial designs, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007, xvi+311 pages | DOI | MR | Zbl

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

*Cited by Sources: *