CUBO, A Mathematical Journal Vol. 24, no. 02, pp. 263–272, August 2022 DOI: 10.56754/0719-0646.2402.0263 Perfect matchings in inhomogeneous random bipartite graphs in random environment Jairo Bochi 1 Godofredo Iommi 2 Mario Ponce 2,B 1Department of Mathematics, The Pennsylvania State University, USA. bochi@psu.edu 2Facultad de Matemáticas, Pontificia Universidad Católica de Chile, Santiago, Chile. giommi@mat.uc.cl mponcea@mat.uc.cl B 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 bi- partite graphs in a random environment. We show that the expected number of perfect matchings obeys a precise asymptotic. RESUMEN En esta nota estudiamos grafos aleatorios bipartitos inho- mogéneos en un ambiente aleatorio. Estos grafos pueden ser pensados como una extensión de los grafos bipartitos aleatorios clásicos de Erdős-Rényi en un ambiente aleato- rio. Mostramos que el número esperado de pareos obedece un comportamiento asintótico preciso. Keywords and Phrases: Perfect matchings, large permanents, random graphs. 2020 AMS Mathematics Subject Classification: 05C80, 05C70, 05C63. Accepted: 13 April, 2022 Received: 15 October, 2021 c©2022 J. Bochi et al. This open access article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. http://cubo.ufro.cl/ https://dx.doi.org/10.56754/0719-0646.2402.0263 https://orcid.org/0000-0003-2833-9957 https://orcid.org/0000-0001-6967-7894 mailto:mponcea@mat.uc.cl https://orcid.org/0000-0002-6617-3145 mailto:bochi@psu.edu mailto:giommi@mat.uc.cl mailto:mponcea@mat.uc.cl 264 J. Bochi, G. Iommi & M. Ponce CUBO 24, 2 (2022) 1 Introduction In their seminal paper [7], Erdős and Rényi studied a certain type of random graphs, which in the case of bipartite graphs correspond to the following. Consider a bipartite graph with set of vertices given by W = {w1, . . . ,wn} and M = {m1, . . . ,mn}. Let p ∈ [0,1], Σ be a probability space and consider the independent random variables X(ij) defined on Σ with law X(ij)(x) =      1 with probability p; 0 with probability 1 − p, for x ∈ Σ. Denote by Gn(x) the bipartite graph with vertex set W ∪ M and edges E(x), where the edge (wi,mj) belongs to E(x) if and only if X(ij)(x) = 1. Let pm(Gn(x)) be the number of perfect matchings of the graph Gn(x) (see Sec. 3 for precise definitions). Erdős and Rényi [8, p. 460] observed that the mean of the number of perfect matchings was given by E(pm(Gn(x))) = n!p n. (1.1) This number has been also studied by Bollobás and McKay [5, Theorem 1] in the context of k−regular random graphs and by O’Neil [11, Theorem 1] for random graphs having a fixed (large enough) proportion of edges. We refer to the text by Bollobás [4] for further details on the subject of random graphs. This paper is devoted to study certain sequences of inhomogeneous random bipartite graphs Gn,ω in a random environment ω ∈ Ω (definitions are given in Sec. 2). Inhomogeneous random graphs have been intensively studied over the last years (see [6], where non-bipartite graphs are also considered). Our main result (see Theorem 3.2 for precise statement) is that there exists a constant c ∈ (0,1) such that for almost every environment ω ∈ Ω and for large n ∈ N En,ω(pm(Gn,ω(x))) ≍ n!cn, (1.2) where the meaning of the asymptotic ≍ will be explained later. Moreover, we have an explicit formula for the number c. The result in equation (1.2) should be understood in the sense that the mean number of perfect matchings for inhomogeneous random bipartite graphs in a random environment is asymptotically the same as the one of Erdős-Rényi bipartite graphs in which p = c. Note that p is a constant that does not depend on n. The number c is the so-called scaling mean of a function related to the random graphs. Scaling means were introduced, in more a general setting, in [2] and are described in Sec. 3. CUBO 24, 2 (2022) Perfect matchings in inhomogeneous random bipartite graphs... 265 2 Inhomogeneous random bipartite graphs in random envi- ronment Consider the following generalization of the Erdős-Rényi bipartite graphs. Let W = {w1, . . . ,wn} and M = {m1, . . . ,mn} be two disjoint sets of vertices. For every pair 1 ≤ i,j ≤ n, let aij ∈ [0,1] and consider the independent random variables X(ij), with law X(ij)(x) =    1 with probability a(ij); 0 with probability 1 − a(ij). Denote by Gn(x) the bipartite graph with vertices W,M and edges E(x), where the edge (wi,mj) belongs to E(x) if and only if X(ij)(x) = 1. As it is clear from the definition all vertex of the graph do not play the same role. This contrasts with the (homogenous) Erdős-Renyi graphs (see [6] for details). We remark that in relation to the graphs we are considering it is possible to include the stochastic block model (see [10]) that is used, for example, in problems of community detection, in the context of machine learning. In this note we consider inhomogeneous random bipartite graphs in random environments, that is, the laws of X(ij) (and hence the numbers a(ij)) are randomly chosen following an exterior environment law. This approach to stochastic processes has developed since the groundbreaking work by Solomon [12] on Random Walks in Random Environment and subsequent work of a large community (see [3] for a survey on the subject). The model we propose is to consider the vertex sets W,M as the environment and to consider that the number a(ij), which is the probability that the edge connecting wi with mj occurs in the graph, is a random variable depending on wi and mj. We now describe precisely this model. The space of environments is as follows. Fix α ∈ N and a stochastic vector (p1,p2, . . . ,pα). Endow the set {1, . . . ,α} with the probability measure PW defined by PW ({i}) = pi. Denote by ΩW the product space ∏∞ i=1{1,2, . . . ,α} and by µW the corresponding product measure. Let (ΩM,µM) be the analogous probability measure space for the set {1,2, . . . ,β} and the stochastic vector (q1,q2, . . . ,qβ). The space of environments is Ω = ΩW × ΩM with the measure µΩ = µW × µM and an environment is an element ω ∈ Ω. Note that every environment defines two sequences W(ω) = (w1,w2, . . .) ∈ ΩW and M(ω) = (m1,m2, . . .) ∈ ΩM. For each environment ω ∈ Ω we now define the edge distribution Xω,(ij). Let F = [fsr] be a α × β matrix with entries fsr satisfying 0 ≤ fsr ≤ 1 and let f : {1,2, . . . ,α} × {1,2, . . . ,β} → [0,1] be the function defined by f(w,m) = fwm. For each ω ∈ Ω let a(ij)(ω) := f (wi(ω),mj(ω)) = fwi(ω),mj(ω). (2.1) Given an environment ω ∈ Ω the corresponding edge distributions are the random variables Xω,(ij) 266 J. Bochi, G. Iommi & M. Ponce CUBO 24, 2 (2022) with laws Xω,(ij)(x) =    1 with probability a(ij)(ω); 0 with probability 1 − a(ij)(ω). Given an environment ω ∈ Ω, we construct a sequence of random bipartite graphs Gn,ω considering the sets of vertices Wn,ω = (w1(ω), . . . ,wn(ω)) and Mn,ω = (m1(ω), . . . ,mn(ω)), and edge distributions Xω,(ij) given by the values of a(ij)(ω) as in (2.1). We denote by Pn,ω the law of the random graph Gn,ω. Example 2.1. Given a choice of an environment ω ∈ Ω, the probability that the bipartite graph Gn,ω(x) equals the complete bipartite graph Kn,n, using independence of the edge variables, is Pn,ω (Gn,ω(x) = Kn,n) = ∏ 1≤i,j≤n Pn,ω(Xω,(ij) = 1) = ∏ 1≤i,j≤n a(ij)(ω). 3 Counting Perfect Matchings Recall that a perfect matching of a graph G is a subset of edges containing every vertex exactly once. We denote by pm(G) the number of perfect matchings of G. When the graph G is bipartite, and the corresponding bipartition of the vertices has the form W = {w1,w2, . . . ,wn} and M = {m1,m2, . . . ,mn}, a perfect matching can be identified with a bijection between W and M, and hence with a permutation σ ∈ Sn. From this, the total number of perfect matchings can be computed as pm(G) = ∑ σ∈Sn x1σ(1)x2σ(2) · · ·xnσ(n), (3.1) where xij are the entries of the incidence matrix XG of G, that is xij = 1 if (wi,mj) is an edge of G and xij = 0 otherwise. Of course, the right hand side of (3.1) is the permanent, per(XG), of the matrix XG. In the framework of Section 2, we estimate the number of perfect matchings for the sequence of inhomogeneous random bipartite graphs Gn,ω, for a given environment ω ∈ Ω. More precisely, we obtain estimates for the growth of the mean of pm(Gn,ω(x)) = per(XGn,ω(x)) = ∑ σ∈Sn Xω,(1σ(1)) · · ·Xω,(nσ(n)). (3.2) Denote by En,ω the expected value with respect to the probability Pn,ω. Since the edges are CUBO 24, 2 (2022) Perfect matchings in inhomogeneous random bipartite graphs... 267 independent and En,ω(Xω,(ij)) = aij(ω) we have En,ω (pm(Gn,ω)) = En,ω ( ∑ σ∈Sn Xω,(1σ(1)) · · ·Xω,(nσ(n)) ) = ∑ σ∈Sn a(1σ(1))(ω) · · ·a(nσ(n))(ω) = per(An(ω)), where the entries of the matrix are (An(ω))ij = a(ij)(ω). The main result of this note describes the growth of this expected number for perfect matchings. The following number is a particular case of a quantity introduced by the authors in a more general setting in [2]. Definition 3.1. Let F be an α × β matrix with non-negative entries (frs). Let ~p = (p1, . . . ,pα) and ~q = (q1, . . . ,qβ) be two stochastic vectors. The scaling mean of F with respect to ~p and ~q is defined by sm~p,~q(F) := inf (xr)∈R α + ,(ys)∈R β + ( α ∏ r=1 x−prr )( β ∏ s=1 y−qss )( α ∑ r=1 β ∑ s=1 xrfrsysprqs ) . The scaling mean is increasing with respect to the entries of the matrix and lies between the minimum and the maximum of the entries (see [2] for details and more properties). We stress that the scaling mean can be exponentially approximated using a simple iterative process (see Section 5). The main result in this note is the following, Theorem 3.2 (Main Theorem). Let (Gn,ω)n≥1 be a sequence of random bipartite graphs on a random environment ω ∈ Ω. If for every pair (r,s) we have frs > 0 then the following pointwise convergence holds lim n→∞ ( En,ω (pm(Gn,ω)) n! )1/n = sm~p,~q(F), (3.3) for µW × µM-almost every environment ω ∈ Ω. Remark 3.3. As discussed in the introduction Theorem 3.2 shows that there exists a constant c ∈ (0,1), such that for almost every environment ω ∈ Ω and for n ∈ N sufficiently large En,ω(pm(Gn,ω(x))) ≍ n!cn. Namely c = sm~p,~q(F). This result should be compared with the corresponding one obtained by Erdős and Rényi for their class of random graphs, that is E(pm(Gn(x))) = n!p n. 268 J. Bochi, G. Iommi & M. Ponce CUBO 24, 2 (2022) Thus, we have shown that for large values of n the growth of the number of perfect matchings for random graphs in a random environment behaves like the simpler model studied by Erdős and Rényi with p = sm~p,~q(F). Remark 3.4. Theorem 3.2 shows that the expected number of perfect matchings is a quenched variable, in the sense of that it does not depend on the environment ω (see for instance [P]). Remark 3.5. Using the Stirling formula, the limit in (3.3) can be stated as lim n→∞ ( 1 n log (En,ω (pm(Gn,ω))) − log n ) = log sm~p,~q(F) − 1, which gives a quenched result for the growth of the perfect matching entropy for the sequence of graphs Gω,n (see [1]). Remark 3.6. Note that we assume a uniform ellipticity condition on the values of the probabil- ities a(ij) as in (2.1). A similar assumption appears in the setting of Random Walks in Random Environment (see [3, p. 355]). We now present some concrete examples. Example 3.7. Let α = β = 2 and p1 = p2 = q1 = q2 = 1/2. Therefore, the space of en- vironments is the direct product of two copies of the full shift on two symbols endowed with the (1/2,1/2)−Bernoulli measure. The edge distribution matrix F is a 2 × 2 matrix with entries belonging to (0,1). In [2, Example 2.11], it was shown that sm~p,~q   f11 f12 f21 f22   = √ f11f22 + √ f12f21 2 . Therefore, Theorem 3.2 implies that lim n→∞ ( En,ω (pm(Gn,ω)) n! )1/n = √ f11f22 + √ f12f21 2 , for almost every environment ω ∈ Ω. Example 3.8. More generally let α ∈ N with α ≥ 2 and β = 2. Consider the two stochastic vectors ~p = (p1,p2, . . . ,pα) and ~q = (q1,q2). The space of environments is the direct product of a full shift on α symbols endowed with the ~p-Bernoulli measure with a full shift on two symbols endowed with the ~q-Bernoulli measure. The edge distribution matrix F is a α × 2 matrix with entries fr1,fr2 ∈ (0,∞), where r ∈ {1, . . . ,α}. Denote by χ ∈ R+ the unique positive solution of the equation α ∑ r=1 prfr1 fr1 + fr2χ = q1. Then sm~p,~q(F) = sm~p,~q      f11 f12 ... ... fα1 fα2      = q q1 1 ( q2 χ )q2 α ∏ r=1 (fr1 + fr2χ) pr . CUBO 24, 2 (2022) Perfect matchings in inhomogeneous random bipartite graphs... 269 Therefore, Theorem 3.2 implies that lim n→∞ ( En,ω (pm(Gn,ω)) n! )1/n = q q1 1 ( q2 χ )q2 α ∏ r=1 (fr1 + fr2χ) pr , for almost every environment ω ∈ Ω. The quantity in the right hand side first appeared in the work by Halász and Székely in 1976 [9], in their study of symmetric means. In [2, Theorem 5.1] using a completely different approach we recover their result. 4 Proof of the Theorem The shift map σW : ΩW → ΩW is defined by σW (w1,w2,w3, . . .) = (w2,w3, . . .). The shift map σW is a µW -preserving, that is, µW (Λ) = µW(σ −1 W (Λ)) for every measurable set Λ ⊂ ΩW , and it is ergodic, that is, if Λ = σ−1W (Λ) then µW (Λ) equals 1 or 0. Analogously for σM and µM. We define a function Φ : ΩW × ΩM → R by Φ(~w, ~m) = fw1m1. Thus Φ(σi−1W (~w),σ j−1 M (~m)) = fwimj = a(ij)(ω). That is, the matrix An(ω) has entries a(ij)(ω) = Φ(σ i−1 W (~w),σ j−1 M (~m)). We are in the exact setting in order to apply the Law of Large Permanents see [2, Theorem 4.1]. Theorem (Law of Large Permanents). Let (X,µ), (Y,ν) be Lebesgue probability spaces, let T : X → X and S : Y → Y be ergodic measure preserving transformations, and let g : X × Y → R be a positive measurable function essentially bounded away from zero and infinity. Then for µ × ν-almost every (x,y) ∈ X × Y , the n × n matrix Mn(x,y) =        g(x,y) g(Tx,y) · · · g(Tn−1x,y) g(x,Sy) g(Tx,Sy) · · · g(Tn−1x,Sy) ... ... ... g(x,Sn−1y) g(Tx,Sn−1y) · · · g(Tn−1x,Sn−1y)        verifies lim n→∞ ( per (Mn(x,y)) n! )1/n = smµ,ν(g) pointwise, where smµ,ν(g) is the scaling mean of g defined as smµ,ν(g) = inf φ,ψ ∫∫ X×Y φ(x)g(x,y)ψ(y)dµdν exp (∫ X log φ(x)dµ ) exp (∫ Y log ψ(y)dν ), 270 J. Bochi, G. Iommi & M. Ponce CUBO 24, 2 (2022) where the functions φ and ψ are assumed to be measurable, positive and such that their logarithms are integrable. We apply this Law of Large Permanents setting X = ΩW ,Y = ΩM, T = σW ,S = σM , g = Φ and recalling that frs > 0. We have smµW ,µM (Φ) = sm~p,~q(F) as a consequence of an alternative characterization of the scaling mean given in (see [2, Proposition 3.5]). This concludes the proof of the Main Theorem. � Remark 4.1. We have chosen to present our result in the simplest possible setting. That is, the environment space being products of full-shifts endowed with Bernoulli measures. Using the general form of the Law of Large Permanent above our results can be extended for inhomogeneous random graphs in more general random environments. 5 An algorithm to compute the scaling mean The purpose of this section is to show that the scaling mean is the unique fixed point of a contrac- tion. Therefore it can be computed, or approximated, using a suitable iterative process. It should be stressed that, on the other hand, it has been shown that no such algorithm exists to compute the permanent. Denote by Bα ⊂ Rα and by Bβ ⊂ Rβ the positive cones. Define the following maps forming a (non-commutative) diagram: Bα Bα Bβ Bβ I1 K2K1 I2 by the formulas: (I1(~x))i := 1 xi , (I2(~y))i := 1 yi , (K1(~x))j := β ∑ i=1 fijxipi , (K2(~y))j := α ∑ j=1 fijyjqj. Let T : Bα 7→ Bα be the map defined by T := K1 ◦ I2 ◦ K2 ◦ I1. The map T is a contraction for a suitable Hilbert metric. Indeed, for ~x,~z ∈ Bα define the following (pseudo)-metric d(~x,~z) := log ( maxi xi/zi mini xi/zi ) . It was proven in [2, Lemma 3.4] Lemma 5.1. We have that d(T(~x),T(~z)) ≤ ( tanh δ 4 )2 d(~x,~z), CUBO 24, 2 (2022) Perfect matchings in inhomogeneous random bipartite graphs... 271 where δ ≤ 2 log ( maxi,j fij minij fij ) < ∞. The following results was proved in [2, Lemma 3.3] Lemma 5.2. The map T has a unique (up to positive scaling) fixed point ~xT ∈ Bα. Moreover, defining ~yT := K2 ◦ I1(~xT) one has that sm(f) = α ∏ i=1 x pi i β ∏ j=1 y qj j . Therefore, it possible to find good approximations of the scaling mean using an iterative process. Acknowledgments The authors were partially supported by CONICYT PIA ACT172001. J.B. was partially supported by Proyecto Fondecyt 1180371. G.I. was partially supported by Proyecto Fondecyt 1190194. M.P. was partially supported by Proyecto Fondecyt 1180922. 272 J. Bochi, G. Iommi & M. Ponce CUBO 24, 2 (2022) References [1] 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. [2] J. Bochi, G. Iommi and M. Ponce, “The scaling mean and a law of large permanents”, Adv. Math., vol. 292, pp. 374–409, 2016. [3] L. V. Bogachev, “Random walks in random environments”, in Encyclopedia of Mathematical Physics, vol. 4, pp. 353–371. Elsevier: Oxford, 2006. [4] B. Bollobás, Random graphs, Cambridge Studies in Advanced Mathematics, vol. 73, Cam- bridge University Press: Cambridge, 2001. [5] 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. [6] 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. [7] P. Erdős and A. Rényi, ‘On random graphs. I”, Publ. Math. Debrecen, vol. 6, pp. 290–297, 1959. [8] P. Erdős and A. Rényi, “On random matrices”, Magyar Tud. Akad. Mat. Kutató Int. Közl., vol. 8, pp. 455–461, 1964. [9] 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. [10] P. Holland, K. Laskey and S. Leinhardt, “Stochastic blockmodels: first steps”, Social Net- works, vol. 5, no. 2, pp. 109–137, 1983. [11] P. E. O’Neil, “Asymptotics in random (0,1)-matrices”, Proc. Amer. Math. Soc., vol. 25, pp. 290–296, 1970. [12] F. Solomon, “Random walks in a random environment”, Ann. Probability, vol. 3, no. 1, pp. 1–31, 1975. Introduction Inhomogeneous random bipartite graphs in random environment Counting Perfect Matchings Proof of the Theorem An algorithm to compute the scaling mean