Deranged Matchings: Proofs and Conjectures

DOI10.1080/00029890.2023.2274239MaRDI QIDQ6189652zbMATH OpenFDO

Authors

Publication date 8 February 2024

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

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

principle of inclusion-exclusion Tannery's theorem

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)

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_{2 n}

minus a perfect matching

M^{'}

. With

m a t h r m p m (c d o t)

counting perfect matchings, the elder phenomenon takes the form

m a t h r m p m (K_{n, n} - M) / m a t h r m p m (K_{n, n}) o 1 / e

as

n o i n f t y

while its youthful analogue is

m a t h r m p m (K_{2 n} - M^{'}) / m a t h r m p m (K_{2 n}) o 1 / s q r t e

. These starting graphs are both

2 n

-vertex `balanced complete

r

-partite' graphs

K_{r i m e s 2 n / r}

, respectively with

r = 2

and

r = 2 n

. We conjecture that

m a t h r m p m (K_{r i m e s 2 n / r} - M) / m a t h r m p m (K_{r i m e s 2 n / r}) s i m e^{- r / (2 r - 2)}

as

n o i n f t y

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.

Recommendations

Cites work

Cited in

(1)

Deranged perfect matchings on complete graph and balanced complete r-partite graph

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)