Counting Deranged Matchings

MaRDI QIDQ6416060zbMATH OpenFDO

Authors Sam Spiro

Publication date 3 November 2022

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $mathrmpm(G)$ denote the number of perfect matchings of a graph $G$, and let $K_{rimes2n/r}$ denote the complete $r$-partite graph where each part has size $2n/r$. Johnson, Kayll, and Palmer conjectured that for any perfect matching $M$ of $K_{rimes2n/r}$, we have for $2n$ divisible by $r$ [frac{mathrm{pm}(K_{r imes 2n/r}-M)}{mathrm{pm}(K_{r imes 2n/r})}sim e^{-r/(2r-2)}.] This conjecture can be viewed as a common generalization of counting the number of derangements on $n$ letters, and of counting the number of deranged matchings of $K_{2n}$. We prove this conjecture. In fact, we prove the stronger result that if $R$ is a uniformly random perfect matching of $K_{rimes2n/r}$, then the number of edges that $R$ has in common with $M$ converges to a Poisson distribution with parameter $fracr2r-2$.

This page was built for publication: Counting Deranged Matchings

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