The Erdos-Ko-Rado theorem for perfect matchings

2009/11/18 by Meagher, Karen
#05C35 #05C70 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0911.3669

Abstract

A 2k-matching is a perfect matching of the complete graph on 2k vertices. Two 2k-matchings are defined to be t-intersecting if they have at least t edges in common. The main result in this paper is that if k ≥ 3t/2+1, then the largest system of t-intersecting 2k-matchings has size (2(k-t)-1)!! = ∏_i=0^k-t-1(2k-2t-2i-1) and the only systems that meet this bound consist of all 2k-matchings that contain a set of t disjoint edges. Further, this bound on k is sharp for t≥ 6. The method used is this paper is similar to the proof of the complete Erdős-Ko-Rado theorem given by Ahlswede and Khachatrian.

Related

• The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings
• An extension of the Erdős-Ko-Rado theorem to set-wise 2-intersecting families of perfect matchings
• An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings
• An Erdős-Ko-Rado type theorem for subgraphs of perfect matchings
• Erdős-Ko-Rado for Perfect Matchings