Perfect matchings in inhomogeneous random bipartite graphs in random environment

  • 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.
Keywords: perfect matchings, large permanents, random graphs

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.

References

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.

Published
2022-08-22
How to Cite
[1]
J. Bochi, G. Iommi, and M. Ponce, “Perfect matchings in inhomogeneous random bipartite graphs in random environment”, CUBO, vol. 24, no. 2, pp. 263–272, Aug. 2022.
Section
Articles

Funding data