Random perfect matchings in regular graphs

EUROCOMB’23

Bertille Granet Felix Joos

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-069

PDF
Abstract
We prove that in all regular robust expanders $G$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.

Pages:
497–502
References

A. Ferber, K. Hänni, and V. Jain. The probability of selecting k edge-disjoint Hamilton cycles in the complete graph. arXiv:2001.01149, 2020.

B. Granet and F. Joos. Random perfect matchings in regular graphs. arXiv:2301.10131, 2023.
https://doi.org/10.1002/rsa.21172

V. Gruslys and S. Letzter. Cycle partitions of regular graphs. Combin. Probab. Comput., 30:526-549, 2021.
https://doi.org/10.1017/S0963548320000553

D. Johnston, P. M. Kayll, and C. Palmer. Deranged matchings: proofs and conjectures. arXiv:2209.11319, 2022.

J. Kahn and J. H. Kim. Random matchings in regular graphs. Combinatorica, 18:201-226, 1998.
https://doi.org/10.1007/PL00009817

D. Kühn, A. Lo, D. Osthus, and K. Staden. The robust component structure of dense regular graphs and applications. Proc. Lond. Math. Soc., 110:19-56, 2015.
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:62-146, 2013.
https://doi.org/10.1016/j.aim.2013.01.005

S. Spiro and E. Surya. Counting deranged matchings. arXiv:2211.01872, 2022.

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Bertille Granet, Felix Joos

PDF