2022/09/22 by Daniel Johnston, Johnston, Daniel, P. Mark Kayll +3 · 1 citation
Mathematics · Social Sciences · #05C70 05C30 (Primary) 05A16 #40A05 (Secondary) #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Names, Identity, and Discrimination Research
paper · pdf · doi:10.48550/arxiv.2209.11319
openalex publication_date 2022/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Kn,n with a disjoint perfect matching M removed. Likewise, a deranged matching is a perfect matching in the complete graph K2n minus a perfect matching M'. With pm(⋅) counting perfect matchings, the elder phenomenon takes the form pm(Kn,n-M)/pm(Kn,n)→ 1/e as n→∞ while its youthful analogue is pm(K2n-M')/pm(K2n)→ 1/√(e). These starting graphs are both 2n-vertex `balanced complete r-partite' graphs K_r × 2n/r, respectively with r=2 and r=2n. We conjecture that pm(K_r×2n/r-M)/pm(K_r×2n/r)∼ e-r/(2r-2) as n→∞ 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.