Browse issues
no. 4
The Erdős–Ko–Rado theorem for 2-intersecting families of perfect matchings
Fallat, Shaun1; Meagher, Karen1; Shirazi, Mahsa N.1
1 University of Regina Department of Mathematics and Statistics Regina, SK S4S 0A2, Canada
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≥3 a set of 2-intersecting perfect matchings in K 2k of maximum size has (2k-5)(2k-7)⋯(1) perfect matchings.

Received:
Revised:
Accepted:
Published online:
DOI: 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.

Fallat, Shaun 1; Meagher, Karen 1; Shirazi, Mahsa N. 1

1 University of Regina Department of Mathematics and Statistics Regina, SK S4S 0A2, Canada
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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] 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 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

[16] Srinivasan, Murali K. A Maple program for computing θ ^ 2μ 2λ (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 | DOI | MR | Zbl

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

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

[20] Wilson, Richard M. 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: