Deranged Matchings: Proofs and Conjectures

DOI10.1080/00029890.2023.2274239arXiv2209.11319MaRDI QIDQ6189652FDOQ6189652

Authors:

Publication date: 8 February 2024

Published in: The American Mathematical Monthly (Search for Journal in Brave)

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 $mathrmpm(cdot)$ counting perfect matchings, the elder phenomenon takes the form $mathrmpm(K_{n,n}-M)/mathrmpm(K_{n,n})o1/e$ as $noinfty$ while its youthful analogue is $mathrmpm(K_{2n}-M^{\prime })/mathrmpm(K_{2n})o1/sqrte$. These starting graphs are both $2n$-vertex `balanced complete $r$-partite' graphs $K_{rimes2n/r}$, respectively with $r=2$ and $r=2n$. We conjecture that $mathrmpm(K_{rimes2n/r}-M)/mathrmpm(K_{rimes2n/r})sim{e}^{-r/(2r-2)}$ as $noinfty$ 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.

Full work available at URL: https://arxiv.org/abs/2209.11319

Recommendations

• Counting deranged matchings
• On the combinatorics of derangements and related permutations
• Derangements, Permanents, and Christmas Presents
• A conjecture of Stanley on alternating permutations
• Perfect matchings and derangements on graphs

zbMATH Keywords

Tannery's theoremprinciple of inclusion-exclusion

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Convergence and divergence of series and sequences (40A05)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hermite polynomials and a duality relation for matchings polynomials
• Title not available (Why is that?)
• Perfect matchings and derangements on graphs
• A vector space analog of permutations with restricted position
• Complementary matching vectors and the uniform matching extension property
• Amazing and aesthetic aspects of analysis
• Matchings, Derangements, Rencontres
• Title not available (Why is that?)
• The set of ratios of derangements to permutations in digraphs is dense in \([0,1/2]\)
• Roots of polynomials and the derangement problem
• Asymptotic enumeration of \(k\)-edge-colored \(k\)-regular graphs
• Dinner, Dancing, and Tennis, Anyone?
• Avoiding Your Spouse at a Bridge Party
• Deranged Matchings: Enumeration by Integration!!
• A new proof of an integral formula for counting perfect matchings in graphs
• Integrals don't have anything to do with discrete math, do they?
• Recontres Reencountered
• Derangements, Permanents, and Christmas Presents
• Another short proof of the Joni-Rota-Godsil integral formula for counting bipartite matchings
• Title not available (Why is that?)

This page was built for publication: Deranged Matchings: Proofs and Conjectures

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