Deranged matchings: proofs and conjectures

Abstract

We introduce, and partially resolve, a conjecture that brings a three-centuries-old derangements phenomenon and its much younger two-decades-old analogue under the same umbrella. Through a graph-theoretic lens, a derangement is a perfect matching in the complete bipartite graph $K_{n,n}$ with a disjoint perfect matching $M$ removed. Likewise, a deranged matching is a perfect matching in the complete graph $K_{2n}$ minus a perfect matching $M^{\prime }$. With $\mathrm{pm}(\cdot )$ counting perfect matchings, the elder phenomenon takes the form $\mathrm{pm}(K_{n,n}-M)/\mathrm{pm}(K_{n,n})\to 1/e$ as $n\to \infty$ while its youthful analogue is $\mathrm{pm}(K_{2n}-M^{\prime })/\mathrm{pm}(K_{2n})\to 1/\sqrt{e}$. These starting graphs are both $2n$-vertex `balanced complete $r$-partite' graphs $K_{r\times 2n/r}$, respectively with $r=2$ and $r=2n$. We conjecture that $\mathrm{pm}(K_{r\times 2n/r}-M)/\mathrm{pm}(K_{r\times 2n/r})\sim e^{-r/(2r-2)}$ as $n\to \infty$ and establish several substantive special cases thereof. For just two examples, $r=3$ yields the limit $e^{-3/4}$ while $r=n$ results again in $e^{-1/2}$. Our tools blend combinatorics and analysis in a medley incorporating Inclusion-Exclusion and Tannery's Theorem.

19 pages, 3 figures