2022/11/03 by Sam Spiro, Spiro, Sam, Erlang Surya +1 · 1 citation
Computer Science · Mathematics · #05A16 #05C70 #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2211.01872
openalex publication_date 2022/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let pm(G) denote the number of perfect matchings of a graph G, and let Kr× 2n/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 Kr× 2n/r, we have for 2n divisible by r \fracpm(Kr× 2n/r-M)pm(Kr× 2n/r)∼ 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 K2n. We prove this conjecture. In fact, we prove the stronger result that if R is a uniformly random perfect matching of Kr× 2n/r, then the number of edges that R has in common with M converges to a Poisson distribution with parameter (r)/(2r-2).