A perfect matching in the complete graph on 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 -intersecting if they have at least 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 . Specifically, for a set of 2-intersecting perfect matchings in of maximum size has perfect matchings.
Revised:
Accepted:
Published online:
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 = {http://www.numdam.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 - http://www.numdam.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 http://www.numdam.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. http://www.numdam.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 -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), Research Paper 40, 12 pages | MR | Zbl
[14] On association schemes of the symmetric group acting on partitions of type , Bayreuth. Math. Schr. (1994) no. 47, pp. 151-164 | MR | Zbl
[15] On the minimal degrees of characters of , J. Algebra, Volume 45 (1977) no. 1, pp. 132-181 | DOI | MR | Zbl
[16] A Maple program for computing (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: