Perfect matchings in inhomogeneous random bipartite graphs in random environment

Jairo Bochi; Godofredo Iommi; Mario Ponce

doi:10.56754/0719-0646.2402.0263

DOI:

https://doi.org/10.56754/0719-0646.2402.0263

Abstract

In this note we study inhomogeneous random bipartite graphs in random environment. These graphs can be thought of as an extension of the classical ErdÅ‘s-Rényi random bipartite graphs in a random environment. We show that the expected number of perfect matchings obeys a precise asymptotic.

Keywords

perfect matchings , large permanents , random graphs

Jairo Bochi Department of Mathematics, The Pennsylvania State University, USA.
Godofredo Iommi Facultad de Matemáticas, Pontificia Universidad Católica de Chile, Santiago, Chile.
Mario Ponce Facultad de Matemáticas, Pontificia Universidad Católica de Chile, Santiago, Chile.

Pages: 263–272
Date Published: 2022-08-22
Vol. 24 No. 2 (2022)

M. Abért, P. Csikvári, P. Frenkel and G. Kun, “Matchings in Benjamini-Schramm convergent graph sequences”, Trans. Amer. Math. Soc., vol. 368, no. 6, pp. 4197–4218, 2016.

J. Bochi, G. Iommi and M. Ponce, “The scaling mean and a law of large permanents”, Adv. Math., vol. 292, pp. 374–409, 2016.

L. V. Bogachev, “Random walks in random environments”, in Encyclopedia of Mathematical Physics, vol. 4, pp. 353–371. Elsevier: Oxford, 2006.

B. Bollobás, Random graphs, Cambridge Studies in Advanced Mathematics, vol. 73, Cam- bridge University Press: Cambridge, 2001.

B. Bollobás and B. D. McKay, “The number of matchings in random regular graphs and bipartite graphs”, J. Combin. Theory Ser. B, vol. 41, no. 1, pp. 80–91, 1989.

B. Bollobás, S. Janson and O. Riordan, “The phase transition in inhomogeneous random graphs”, Random Structures Algorithms, vol. 31, no. 1, pp. 3–122, 2007.

P. ErdÅ‘s and A. Rényi, ‘On random graphs. I”, Publ. Math. Debrecen, vol. 6, pp. 290–297, 1959.

P. ErdÅ‘s and A. Rényi, “On random matrices”, Magyar Tud. Akad. Mat. Kutató Int. Közl., vol. 8, pp. 455–461, 1964.

G. Halász and G. J. Székely, “On the elementary symmetric polynomials of independent random variables”, Acta Math. Acad. Sci. Hungar., vol. 28, no. 3–4, pp. 397–400, 1976.

P. Holland, K. Laskey and S. Leinhardt, “Stochastic blockmodels: first steps”, Social Net- works, vol. 5, no. 2, pp. 109–137, 1983.

P. E. O‘Neil, “Asymptotics in random (0, 1)-matrices”, Proc. Amer. Math. Soc., vol. 25, pp. 290–296, 1970.

F. Solomon, “Random walks in a random environment”, Ann. Probability, vol. 3, no. 1, pp. 1–31, 1975.