The Erdos-Ko-Rado theorem for perfect matchings

MaRDI QIDQ6216387zbMATH OpenFDO

Authors K. Meagher

Publication date 18 November 2009

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 $kgeq3t/2+1$, then the largest system of $t$-intersecting $2k$-matchings has size $(2(k-t)-1)!!=pro{d}_{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 $tgeq6$. The method used is this paper is similar to the proof of the complete ErdH{o}s-Ko-Rado theorem given by Ahlswede and Khachatrian.

This page was built for publication: The Erdos-Ko-Rado theorem for perfect matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6216387)