Article in press
Authors:
Title:
Deranged Perfect Matchings on complete graph and balanced complete r-partite graph
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-05-18 , Revised: 2025-10-15 , Accepted: 2025-10-15 , Available online: 2025-11-11 , https://doi.org/10.7151/dmgt.2610
Abstract:
We proved that for any finite collection of sparse subgraphs $(D _m)_{m=1}^\ell$ of the
complete graph $K_{2n}$, and a uniformly chosen perfect matching $R$ in $K_{2n}$,
the random vector $(|E(R \cap D_m)|)_{m=1}^\ell$ jointly converges to a vector
of independent Poisson random variables with mean $|E(D_m)|/(2n)$. We also
showed a similar result when $K_{2n}$ is replaced by the balanced complete
$r$-partite graph $K_{r × 2n/r}$ for fixed $r$ and determined the
asymptotic joint distribution. The proofs rely on elementary tools of the
Principle of Inclusion-Exclusion and generating functions. These results extend
recent works of Johnston, Kayll and Palmer, Spiro and Surya, and Granet and
Joos from the univariate to the multivariate setting.
Keywords:
perfect matching, Poisson distribution, principle of Inclusion-Exclusion, generating function
References:
- J.N. Brawner, Dinner, dancing, and tennis, anyone$?$, Math. Mag. 73 (2000) 29–36.
https://doi.org/10.1080/0025570X.2000.11996795 - C.D. Godsil, Hermite polynomials and a duality relation for matchings polynomials, Combinatorica 1 (1981) 257-262.
https://doi.org/10.1007/BF02579331 - B. Granet and F. Joos, Random perfect matchings in regular graphs, Random Structures Algorithms 64 (2024) 3–14.
https://doi.org/10.1002/rsa.21172 - V. Gruslys and S. Letzter, Cycle partitions of regular graphs, Combin. Probab. Comput. 30 (2021) 526–549.
https://doi.org/10.1017/s0963548320000553 - D. Johnston, P.M. Kayll and C. Palmer, Deranged matchings: proofs and conjectures, Amer. Math. Monthly 131 (2024) 95–111.
https://doi.org/10.1080/00029890.2023.2274239 - D. Kühn, A. Lo, D. Osthus and K. Staden, The robust component structure of dense regular graphs and applications, Proc. Lond. Math. Soc. (3) 110 (2015) 19–56.
https://doi.org/10.1112/plms/pdu039 - D. Kühn and D. Osthus, Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments, Adv. Math. 237 (2013) 62–146.
https://doi.org/10.1016/j.aim.2013.01.005 - P. Loya, Amazing and Aesthetic Aspects of Analysis (Springer, New York, 2017).
https://doi.org/10.1007/978-1-4939-6795-7 - B.H. Margolius, Avoiding your spouse at a bridge party, Math. Mag. 74 (2001) 33–41.
https://doi.org/10.2307/2691151 - P. Rémond de Montmort, Essay d'Analyse Sur les Jeux de Hazard, Jacque Quillau, Paris (1708) Seconde Edition, Revûe & augmentée de plusieurs Lettres. Jacque Quillau, Paris (1713). Photographic reprint, Chelsea Publishing Co., New York (1980).
https://doi.org/10.1002/0471725161.ch18 - S. Spiro and E. Surya, Counting deranged matchings, European J. Combin. 120 (2024) 103980.
https://doi.org/10.1016/j.ejc.2024.103980 - R.P. Stanley, Enumerative Combinatorics. Volume 1 (Cambridge University Press, Cambridge, 2012).
https://doi.org/10.1017/CBO9781139058520 - H.S. Wilf, Generatingfunctionology (AK Peters, Ltd., Wellesley, MA, 2006).
- T. Zaslavsky, Complementary matching vectors and the uniform matching extension property, European J. Combin. 2 (1981) 91–103.
https://doi.org/10.1016/S0195-6698(81)80025-X
Close