The covering radius problem for sets of perfect matchings

Abstract

Consider the family of all perfect matchings of the complete graph $K_{2n}$ with $2n$ vertices. Given any collection $\mathcal{M}$ of perfect matchings of size $s$, there exists a maximum number $f(n,x)$ such that if $s\le f(n,x)$, then there exists a perfect matching that agrees with each perfect matching in $\mathcal{M}$ in at most $x-1$ edges. We use probabilistic arguments to give several lower bounds for $f(n,x)$. We also apply the Lovász local lemma to find a function $g(n,x)$ such that if each edge appears at most $g(n,x)$ times then there exists a perfect matching that agrees with each perfect matching in $\mathcal{M}$ in at most $x-1$ edges. This is an analogue of an extremal result vis-á-vis the covering radius of sets of permutations, which was studied by Cameron and Wanless (cf. \cite{cameron}), and Keevash and Ku (cf. \cite{ku}). We also conclude with a conjecture of a more general problem in hypergraph matchings.

10 pages