Matchings in random biregular bipartite graphs

Matchings in Random Biregular Bipartite Graphs Guillem Perarnau∗ Departament de Matem`atica Aplicada IV Universitat Polit`ecnica de Catalunya, BarcelonaTech Barcelona, Spain [email protected] Giorgis Petridis Department of Mathematics University of Rochester Rochester, NY 14627, USA. [email protected] Submitted: Aug 24, 2012; Accepted: Mar 10, 2013; Published: Mar 24, 2013 Mathematics Subject Classifications: 05C80, 05D40, 11B13 Abstract We study the existence of perfect matchings in suitably chosen induced subgraphs of random biregular bipartite graphs. We prove a result similar to a classical theorem of Erd˝os and R´enyi about perfect matchings in random bipartite graphs. We also present an application to commutative graphs, a class of graphs that are featured in additive number theory. Keywords: Random biregular bipartite graphs, Perfect matchings, Commutative graphs. 1 Introduction Let us begin by defining the terms that appear in the title. Recall that, given two sets A and Bof equal size and a bipartite directed graph on vertex set (A, B), a perfect matching (also known as a 1-factor) from Ato Bis a collection of |A|vertex disjoint edges from Ato B. Definition 1. Let k∈Q+be a positive rational number, n∈Z+a positive integer that satisfies kn ∈Z+and d∈Z+a positive integer that satisfies 1 ⩽d⩽nand kd ∈Z+. Let Ybe a set of size nand Zbe a set of size kn. Define G(k, n, d) to be the family of biregular bipartite directed labelled graphs on the vertex set (Y, Z) (with edges directed from Yto Z) where d+(y) = kd for all y∈Yand d−(z) = dfor all z∈Z. Arandom biregular bipartite directed graph (with parameters k, n, d) is a graph chosen from G(k, n, d) uniformly at random. This probability space of random graphs is denoted by G(k, n, d). ∗This work has been partially supported by the Catalan Research Council under grant 2009SGR01387 and the Spanish Council under project MTM2011-28800-C02-01. Eventually, the author wants to thank the FPU grant from the Ministerio de Educaci´on de Espa˜na. the electronic journal of combinatorics 20(1) (2013), #P60 1 The family G(k, n, d) is non-empty. We illustrate this by giving an example for integer k, which is indicative of how biregular bipartite graphs are featured in additive number theory. We identify Zwith Zkn and Ywith the subgroup {0, k, 2k, . . . , (n−1)k}.For y∈Yand z∈Zwe place an edge yz ∈E(G) if z−y∈ {0,1, . . . kd −1}mod (kn).The resulting graph is a member of G(k, n, d). The case where k= 1 has a special relevance since G(1, n, d) is the family of regular bipartite graphs of size nand degree dwhere the edges are canonically oriented from one stable set to the other. Estimating the size of G(1, n, d) as a function of dand n is a question that has been studied extensively [8, 21]. Generalizations of this problem to biregular bipartite graphs [19, 3] as well as to graphs with a prescribed sequence of degrees in each of the stables have also been studied [17, 18]. Using Hall’s theorem it is straightforward to check that every member of G(1, n, d) has a perfect matching (see e.g. [6, Corollary 2.1.3]). For members of G(k, n, d) with k6= 1 there can be no perfect matching as the size of the two stable sets is not equal. The distribution of the number of perfect matchings in random regular bipartite graphs was studied by Bollob´as and McKay in [2], where its expected value and variance are determined. We tackle a different kind of question by studying the existence of a perfect matching in induced subgraphs Hof members of G(k, n, d), whose stable sets have equal size. In particular we determine how the probability of having such a perfect matching changes with d. Our result is analogous to a classical result of Erd˝os and R´enyi. Before stating the main result of the paper we recall that in any model of random graphs a property holds with high probability if the probability that a random graph in the model satisfies this property tends to 1 as ntends to infinity. From now on the phrase will be abbreviated to whp, as it is common in the literature. Theorem 2. Let k∈Q+, n ∈Z+be arbitrarily large and d∈ {1, . . . , n}and suppose that kn, kd ∈Z+with kd ⩽n. Furthermore let Yand Zbe sets of size respectively nand kn, and take subsets A⊆Y and B⊆Zof size kd. Let G∼G(k, n, d)and define H:= G[A, B]to be the subgraph induced by Gon vertex set (A, B). Then (i) No perfect matching exists in Hwhp when kd2 n−log(kd)→ −∞ or when dis a constant. (ii) A perfect matching exists in Hwhp when kd2 n−log(kd)→+∞. Remark 3.The second condition in conclusion (i) has to be included because when dis constant the quantity kd2 n−log(kd) does not tend to −∞. Here and elsewhere, for any y∈Ywe define Γ(y) = {z∈Z:yz ∈E(G)}and for any S⊆Y, Γ(S) = ∪y∈SΓ(y).Similarly we define the inverse neighbourhood of z∈Zby Γ−1(z) and the inverse neighbouhood of T⊆Zby Γ−1(T). The next result is a variation of Theorem 2 when B= Γ(y) for some y∈A. the electronic journal of combinatorics 20(1) (2013), #P60 2 Theorem 4. Let k∈Q+, n ∈Z+be arbitrarily large and d∈ {2, . . . , n}and suppose that kn, kd ∈Z+with kd ⩽n. Furthermore let Yand Zbe sets of size respectively nand kn and G∼G(k, n, d). Take a subset A⊆Yof size kd and y∈A. Define H:= G[A, Γ(y)] to be the subgraph induced by Gon vertex set (A, Γ(y)).Then (i) No perfect matching exists in Hwhp when kd2 n−log(kd)→ −∞ or when dis a constant. (ii) A perfect matching exists in Hwhp when kd2 n−log(kd)→+∞. The case d= 1 is not covered by Theorem 4. It is nonetheless easy to check that for d= 1 a perfect matching exists if and only if k= 1. To put our results in context we briefly describe what holds in the most standard model of random directed bipartite graphs. Definition 5. Let Aand Bbe two sets of size n. A random bipartite graph with parameters n, p is a bipartite graph on the vertex set (A, B) where edges are chosen independently of each other with probability p. The model of random bipartite graphs is denoted by B(n, p). The existence of perfect matchings in random bipartite graphs was investigated by Erd˝os and R´enyi about fifty years ago. They established the following in [7]. Theorem 6 (Erd˝os–R´enyi).Let cbe a constant and nan arbitrarily large positive integer. Furthermore let p=log n+c n and consider a random bipartite graph G0∼B(n, p). Then the probability that G0contains a perfect matching is asymptotically equal to exp(−2e−c). In particular if np −log n→+∞when n→+∞,then there exists a matching in G0 whp; and if np −log n→ −∞ when n→+∞,then no perfect matching exists in G0whp. Theorem 2 is an Erd˝os–R´enyi type result for the induced subgraph H. To make the similarity between Theorem 2 and Theorem 6 as clear as possible we set k= 1 in the former. The induced subgraph His somewhat similar to a random bipartite graph as it has similar properties to G0∼B(d, d/n): The size of the stables of His dand edges appear in (Gand hence also in) Hwith uniform probability d/n. The main difference is that edges do not appear independently in H, yet the dependence is generally speaking small. The similarity between Hand G0is reflected by the fact that a perfect matching exists in both graphs whp when d2/n −log d→+∞. A related question that has been studied more extensively concerns not necessarily bipartite graphs. The models under consideration are Gd(n) (a graph chosen uniformly at random from all d-regular graphs on nvertices) and G(n, p) (a graph on nvertices where edges are chosen independently with probability p) where p=d/n. Two kinds or the electronic journal of combinatorics 20(1) (2013), #P60 3 results have been obtained. On one hand, properties of graphs that hold whp in G(n, p) have been shown to also hold whp in Gd(n) [13, 11, 12]. On the other hand, Kim and Vu have studied the contiguity of both models in [10]. They conjectured that the Gd(n) is contiguous to the G(n, p) when dlog n(Sandwich conjecture), but were only able to show a slightly weaker relation between the models when dn1/3/log2n(their method can be applied in some cases to larger values of dup to d=o(√n)). If their result could be extended to din the √nlog nrange (and also to bipartite graphs) it would imply that the induced subgraph Hand G0∼B(d, d/n) are also contiguous, giving a straightforward proof of Theorem 2 as a corollary of Theorem 6. The main motivation to study the existence of perfect matchings in induced subgraphs of random biregular bipartite graphs has to do with commutative graphs and Pl¨unnecke’s inequality. A comprehensive study of the applications of commutative graphs and Pl¨unnecke’s inequality can be found in [26]. Here we only present the necessary facts that relate commutative graphs with Theorem 4. We begin with two definitions definition. Definition 7. A directed graph Gwith vertex set V(G) = X0∪X1∪···∪Xhis called layered (where the Xiare the layers) if there are edges only between consecutive layers, so that E(Xi, Xj) = ∅unless j=i+ 1 for all 0 ⩽i, j ⩽h. Definition 8. A directed layered graph Gwith layers X0, X1, . . . , Xhis called commutative if 1. For all 1 ⩽i⩽h−1 and uv ∈E(Xi−1, Xi) there exists a perfect matching from a subset of Γ(u) to Γ(v).This condition is called Pl¨unnecke’s upward condition (PU). 2. For all 1 ⩽i⩽h−1 and uv ∈E(Xi, Xi+1) there exists a perfect matching from a subset of Γ−1(v) to Γ−1(u).This condition is called Pl¨unnecke’s downward condition (PD). Observe that when Gis biregular the perfect matching in Pl¨unnecke’s upward (downward) condition is from the whole Γ(u) to Γ(v) (Γ−1(v) to Γ−1(u)). Pl¨unnecke introduced commutative graphs to study the growth of sumsets [24, 25, 22, 27]. He was interested in the magnification ratios of graphs. Di(G) = min ∅6=Z⊆X0 |Γ(i)(Z)| |Z|, where 1 ⩽i⩽hand Γ(i)(Z) is defined iteratively by Γ(i)(Z) = Γ(Γ(i−1)(Z)). Pl¨unnecke proved a powerful inequality that limits the growth of magnification ratios of commutative graphs. Theorem 9 (Pl¨unnecke).Let Gbe a commutative graph. Then the sequence Di(G)1/i is decreasing. In [23] it was shown that the upper bound for Di(G)⩽D1(G)igiven by Theorem 9 is sharp. In particular a commutative graph Gthat satisfies Di(G) = kifor all 1 ⩽i⩽h the electronic journal of combinatorics 20(1) (2013), #P60 4 was constructed for all k∈Q+and h∈Z+. The extremal examples were biregular commutative graphs whose in and out degrees satisfied d+/d−=k. In fact it is easy to check that, in any commutative graph whose degrees satisfy d+/d−=k, the sequence Di(G)1/i is constant and equal to k. We apply Theorem 4 to give a non-constructive, and probabilistic in nature, proof of the existence of graphs that are extremal for Pl¨unnecke’s inequality, answering a question of Gowers. We form a layered directed biregular graph by “placing random biregular bipartite directed graphs on top of each other.” If in each biregular bipartite graph that is induced by two consecutive layers, the out-degree of the bottom layer is large enough compared to its size, then the resulting graph is whp commutative. Theorem 10. Let 1⩽k∈Q+, m ∈Z+be arbitrarily large, d∈ {2, . . . , m}and h∈Z+. Suppose that km, kd ∈Z+. Furthermore let X0, X1, . . . , Xhbe sets with |Xi|=kim. For 1⩽i⩽hlet Gi:= Gi[Xi−1, Xi]∼G(k, ki−1m, d). Let Gbe a graph with vertex set V(G) = X0∪···∪Xhand edge set E(G) = ∪h i=1E(Gi). Then (i) The graph Gis not commutative whp when d⩽q1 3kh−2mlog(km). (ii) The graph Gis commutative whp when d⩾3pkh−2mlog(hkh+1m). Observe that the upper bound and the lower bound in Theorem 10 have the same asymptotic order. We make no effort to optimize the constants as our method does not lead to matching lower and upper bounds. Results on random regular graphs are usually derived using the so-called configuration (or pairing) model due to Bollob´as [1] (for a detailed presentation see [28]). However, this model does not give meaningful results when the degree is large. McKay introduced in [15] a new way to approach problems in random regular graphs when the degree is large, based on switching the edges of the graph. This method has been successfully applied to extend a lot of results for random regular graphs with large degree [20, 13, 5, 4, 11, 12]. Our strategy is to mirror the proof of Theorem 6 of Erd˝os and R´enyi. The biggest obstacle is dealing with dependencies among the edges. We do this by repeatedly using three ingredients: the regularity of the degrees, the symmetry of G(k, n, d) and the idea of edge switchings. The existing estimates on the number of biregular bipartite graphs contain error terms, which are negligible when dis small compared to n, but become significant for larger d. We will not need to estimate |G(k, n, d)|and so we will not be affected by this. The paper is organised as follows. In the next section we introduce the methods we will use repeatedly throughout the paper. In Section 3 we prove a useful result, whose proof demonstrates how the lack of independence in choosing the edges can be overcome. In Section 4 we prove Theorem 4 and in Section 5 we present the backbone of the proof of Theorem 2. Finally in Section 6 we prove Theorem 10. the electronic journal of combinatorics 20(1) (2013), #P60 5 Notation. We conclude the introduction with a quick recap of standard notation we will use throughout the paper. The out-degree of a vertex vis d+(v) = |Γ(v)|and the minimum out-degree of a directed graph Gis δ+(G) = min{d+(v) : v∈V(G)}.The in-degree of a vertex vis similarly defined by d−(v) = |Γ−1(v)|and so is the minimum in-degree δ−(G) of a directed graph G. The minimum degree of a directed graph Gis δ(G) = min{δ−(G), δ+(G)}. For any two functions f, g we write f(n) = O(g(n)) if |f(n)|⩽C|g(n)|for some absolute constant Cand f(n) = Θ(g(n)) if f(n) = O(g(n)) and g(n) = O(f(n)).We also write f(n) = o(g(n)) to mean that limn→+∞f(n)/g(n)=0.In particular we use f(n) = o(1) if limn→+∞f(n)=0. 2 Switching in biregular bipartite graphs The first result we prove illustrates how the regularity of the degrees and the symmetry of biregular bipartite graphs will be used in the paper. Lemma 11. Let k, n, d be like in the statement of Theorem 2. Suppose that G∼ G(k, n, d). (i) Let y, y0∈Y. Then E(|Γ(y)∩Γ(y0)|) = kd(d−1) n−1. (ii) Let y∈Yand B⊆Z. Then E(|Γ(y)∩B|) = d|B| n. Proof. First note that Γ(y) is chosen uniformly at random from all (kd)-element subsets of Z. Without loss of generality we can therefore assume that it is fixed and equal to a set S. Next we observe that E(|Γ(y)∩Γ(y0)|) = X z∈S Pr(z∈Γ(y0)). The probability Pr(z∈Γ(y0)) is equal for all z∈S. To see why take z0, z1∈Sand observe that there exists a bijection θfrom Gz0={G∈ G(k, n, d) : Γ(y) = S∧y0z0∈E(G)} to Gz1={G∈ G(k, n, d) : Γ(y) = S∧y0z1∈E(G)}. The bijection θmaps z0to z1and vice versa and restricts to the identity on V(G)\{z0, z1}. So E(|Γ(y)∩Γ(y0)|) = kd Pr(z0∈Γ(y0)). the electronic journal of combinatorics 20(1) (2013), #P60 6 On the other hand d−1 = E(|Γ−1(z0)\{y}|) =X v∈Y\{y} Pr(z0∈Γ(v)) = (n−1) Pr(z0∈Γ(y0)). The third identity following from the symmetry of random biregular bipartite graphs. The first conclusion follows. The second can be proved similarly. The arguments in the above proof are not sufficient when dealing with more complicated events. To deal with such events we will employ elementary counting arguments that involve switchings. Definition 12. Let a, b ∈Yand c, d ∈Zsuch that ac, bd ∈E(G) and ad, bc /∈E(G).The {ac, bd}-switching of Gis the graph Hwith the same set of vertices as Gand E(H) = E(G)∪{ad, bc}\{ac, bd}. Figure 1 offers an illustration of this natural operation. Observe that if Gis biregular bipartite, then so is H; and that if His the {ac, bd}-switching of G, then Gis the {ad, bc}- switching of H. Switchings between graphs were first used by McKay in [15] to obtain Figure 1: A graph Gand its {ac, bd}-switching H. Solid lines represent edges and dashed lines missing edges. bounds on the probability that a fixed graph appears as a subgraph of a random regular graph. McKay [18] used the same technique to extend the range of din the enumeration of regular graphs to d=o(n1/3). McKay and Wormald in [20] improved that range to d=o(√n) by introducing a new type of switching. Switching is moreover useful in proving that whp regular graphs are expanders [9] or in counting the number of spanning trees subject to an asymptotic condition on the number of cycles [16]. As mentioned in the introduction, switching has more recently been used to study various properties of random regular graphs [13, 5, 4, 11, 12]. We will use it in a similar fashion to compare the sizes of two families of biregular bipartite graphs, say G1and G2. We will count in two ways the number of switchings between the two families. In other words we will double count the number of ordered pairs (G1, G2)∈ G1×G2where G1is a switching of G2,which is equivalent to G2being a switching of G1. the electronic journal of combinatorics 20(1) (2013), #P60 7 3 Preliminary results Let Y,Zand Abe defined as in Theorem 4. The key to most of the calculations leading to the proof of Theorem 4 is having a good upper bound on the probability that there are no edges between two sets S⊆Aand T⊆Γ(y), for some y∈A. As yis joined to all vertices in Γ(y) we assume that S⊆A\ {y}.The main result of this section is the following. Proposition 13. Let Y, Z, G and ybe like in the statement of Theorem 4. Suppose that T⊆Γ(y), z1∈Tand S⊆Y\{y}, where |S|+d⩽n. Then the probability that there are no edges from Sto Tis bounded above by: Pr(Γ(S)∩T=∅)⩽Pr(Γ−1(z1)∩S=∅)|T| =1−|S| n−1|T|1−|S| n−2|T| . . . 1−|S| n−d+ 1|T| ⩽exp −d|S||T| n. Before giving the proof we quickly present a heuristic explanation for the crucial first inequality. For simplicity we take T={z1, z2}. Suppose for a moment that the neighbourhoods of vertices in Swere chosen independently. Then we would have Pr(Γ(S)∩T=∅) = Pr(Γ−1(z1)∩S=∅) Pr(Γ−1(z2)∩S=∅) = Pr(Γ−1(z1)∩S=∅)2. As we do not have independence we have to instead use conditional probabilities: Pr(Γ(S)∩T=∅) = Pr(Γ−1(z1)∩S=∅) Pr(Γ−1(z2)∩S=∅ | Γ−1(z1)∩S=∅). Conditioning on the event Γ−1(z1)⊆Y\Shas an effect on Y\S: the vertices in Γ−1(z1) have one of the kd edges coming out of them “taken up” by z1.One expects that this makes Γ−1(z2) less likely to include them and consequently that Pr(Γ−1(z2)∩S=∅ | Γ−1(z1)∩S=∅)⩽Pr(Γ−1(z1)∩S=∅). Proving this type of upper bound for conditional probabilities is the main task lying ahead. Proof of Proposition 13. The second inequality can be proved by induction on dand the third is standard, so we only prove the first inequality and the expression for Pr(Γ−1(z1)∩ S=∅).We let s=|S|,T={z1, . . . , zt}and proceed by induction on t. When t= 1 we have Pr(Γ−1(z1)∩S=∅) = n−1−s d−1 n−1 d−1=1−s n−11−s n−2. . . 1−s n−d+ 1,(1) the electronic journal of combinatorics 20(1) (2013), #P60 8 as Γ−1(z1)\ {y}is uniformly distributed over all (d−1)-element subsets of Y\ {y}. Another way to interpret this identity is by ordering the edges coming in z1.Without loss of generality we can assume that the first edge is yz1.The probability the second edge coming in z1does not originate from Sis 1 −s/(n−1).The probability the third edge coming in z1does not originate from S, given that the second does not, is 1 −s/(n−2) and so on. For the inductive step let us write T0={z1, . . . , zt−1}.As Pr(Γ−1(T)∩S=∅) = Pr(Γ−1(T0)∩S=∅) Pr(Γ−1(zt)∩S=∅ | Γ−1(T0)∩S=∅), it is enough for our purpose to establish that Pr(Γ−1(zt)∩S=∅ | Γ−1(T0)∩S=∅)⩽Pr(Γ−1(zt)∩S=∅) (2) = Pr(Γ−1(z1)∩S=∅). The last equality follows from the symmetry properties of biregular bipartite graphs. The remainder of the proof is dedicated to proving (2). The strategy is to order the edges ending in ztand successively estimate the probability that each does not originate from S. This will be done in a number of lemmata. We need to keep track of the first jedges ending in zt.To achieve this we denote by y1, . . . , ydthe elements of Γ−1(zt), where y=y1,and, for 1 ⩽j⩽d, we set Fj= {y1, . . . , yj}. The key is to prove the following intuitively clear observation. Suppose that Γ−1(T0) and Fjare disjoint from S. Then for any u∈Sand any v∈Y\Fjthe probability that yj+1 =uis no smaller than the probability that yj+1 =v. We prove the statement in a number of steps. Initially we condition on Fjand Γ−1(T0). Lemma 14. Let 1⩽j⩽d−1be an integer and u∈S. Suppose J⊆Y\Sis a set of size jthat contains y,W⊂Y\Sis another subset of Ythat is disjoint from Sand v /∈W∪J. Then Pr(yj+1 =v|Fj=J∧Γ−1(T0) = W) = Pr(yj+1 =u|Fj=J∧Γ−1(T0) = W). Proof. The statement follows from the symmetry properties of random biregular bipartite graphs: interchanging uand vdoes not affect the events {Γ−1(T0) = W}nor {Fj=J}. Lemma 15. Let 1⩽j⩽d−1be an integer and u∈S. Suppose J⊆Y\Sis a set of size jthat contains y,W⊂Y\Sis another subset of Ythat is disjoint from Sand v∈W\J. Then Pr(yj+1 =v|Fj=J∧Γ−1(T0) = W)⩽Pr(yj+1 =u|Fj=J∧Γ−1(T0) = W). Proof. We first observe that, say, Pr(yj+1 =v|Fj=J∧Γ−1(T0) = W) = Pr(v∈Γ−1(zt)|Fj=J∧Γ−1(T0) = W) d−j the electronic journal of combinatorics 20(1) (2013), #P60 9 and the random variable A+=X y0∈A\{y} 1A+ y0. The linearity of expectation and the symmetry of biregular bipartite graphs gives E(A+)=(kd −1) Pr(A+ y0) for any y0∈A\{y}. Setting S={y0}and T= Γ(y) in Proposition 13 yields E(A+) = Okd exp −kd2 n=O(e−c). When c→+∞the expectation E(A+) = o(1) and so the probability Pr(δ+(H) = 0) = Pr(A+>0) = o(1). To prove the existence of a perfect matching in Hwe will rely on the FrobeniusK¨onig theorem (see e.g. [14, Theorem 1.7.1]), which is equivalent to the well known Hall’s theorem. Lemma 21 (The Frobenius-K¨onig theorem).Let Aand Bbe two sets of equal size. Suppose that His a bipartite graph with vertex set (A, B).Then Hhas no perfect matching if and only if there are non-empty sets S⊆Aand T⊆Bsuch that |S|+|T|=|A|+ 1 and Γ(S)∩T=∅. For any S⊆Aand T⊆B, a pair (S, T) is called problematic if |S|+|T|=|A|+1 and Γ(S)∩T=∅.We show that the probability that a problematic pair (S, T) exists in His o(1) when c→+∞. For technical reasons we need to distinguish between two ranges for c. The third step in the proof of Theorem 4 is to deal with the case when cis larger than a constant multiple of log(kd). Proposition 22. Let Hbe the graph introduced in Theorem 4 and c=kd2 n−log(kd). Suppose that c⩾5 log (kd).Then Pr(There is no perfect matching in H) = Ok2d2exp −kd2 2n. In particular there is a perfect matching in Hwhp. Proof. It follows by Lemma 21 that no perfect matching exists in Hif and only if there are non-empty sets S⊆A\{y}and T⊆Γ(y) such that |S|+|T|=kd +1 and Γ(S)∩T=∅. So we want to bound from above the probability a problematic pair of sets (S, T) exists. the electronic journal of combinatorics 20(1) (2013), #P60 16 For a pair of fixed sets (S, T ) where S⊆A\{y},T⊆Γ(y), |S|=jand |T|=kd+1−j, Proposition 13 gives Pr(Γ(S)∩T=∅)⩽exp −d|S||T| n= exp −dj(kd + 1 −j) n. For a given jthere are at most kd−1 j kd kd+1−j⩽kd jkd j−1possible problematic pairs of sets (S, T).Applying a union bound gives Pr(There is no perfect matching in H)=O kd X j=1 kd j kd j−1exp −j(kd −j+ 1)d n!. Changing jto kd −j+ 1 does not affect the summand, so Pr(There is no perfect matching in H)=O  kd/2 X j=1 kd j kd j−1exp −j(kd −j+ 1)d n  =O X 1⩽j⩽kd/2kd j2 exp −j(kd −j)d n  =O X 1⩽j⩽kd/2k2d2exp −(kd −j)d nj  =O ∞ X j=1 k2d2exp −kd2 2nj!. The lower bound on cimplies that kd →+∞when n→+∞and that k2d2exp −kd2 2n= O((kd)−1)<1. So Pr(There is no perfect matching in H) = Ok2d2exp −kd2 2n=O((kd)−1) = o(1). The above argument does not work when we merely assume that c→+∞.The forth and final task in the proof of Theorem 4 is to adapt the argument provided by Erd˝os and R´enyi in [7] to the induced subgraph H. The key is to consider the minimum out and in degrees. Lemma 18 and Lemma 20 combined imply that Pr({δ−(H) = 1 ∨δ+(H)=0}) = o(1) when c→+∞. So Pr(There is no perfect matching in H) = Pr(There is no perfect matching in H∧δ−(H)>1∧δ+(H)>0)+ Pr(There is no perfect matching in H∧{δ−(H) = 1 ∨δ+(H) = 0}) ⩽Pr(There is no perfect matching in H∧δ−(H)>1∧δ+(H)>0)+ Pr(δ−(H) = 1 ∨δ+(H) = 0) = Pr(There is no perfect matching in H∧δ−(H)>1∧δ+(H)>0)+o(1). the electronic journal of combinatorics 20(1) (2013), #P60 17 So we are only left with proving that Pr(There is no perfect matching in H∧δ−(H)> 1∧δ+(H)>0) = o(1) when c→+∞and c⩽5 log(kd). Proposition 23. Let Hbe the graph introduced in Theorem 4 and c=kd2 n−log(kd). Suppose that 0⩽c⩽5 log(kd).Then Pr(There is no perfect matching in H∧δ−(H)>1∧δ+(H)>0) = o(1). Proof. We once again apply Lemma 21: no perfect matching exists in Hif there are non-empty sets S⊆A\{y}and T⊆Γ(y) such that |S|+|T|=kd + 1 and Γ(S)∩T=∅. We consider the cases |S|⩽|T|and |T|<|S|separately. Let us start with the former. Note that δ+(H)>0 implies that if Sbelongs to a problematic pair, then |S|>1. Suppose for a contradiction that |S|= 1. Then T= Γ(y) and, since (S, T) is problematic, there must be no edges between Sand Tand hence δ+(H) = 0. The size of Slies in the range 2 ⩽|S|⩽(kd + 1)/2 since |S|⩽|T|. The key is to only consider S-minimal problematic pairs (S, T). This means that there exists no proper subset S0(S⊆Aand T0⊆Γ(y) with |S0|+|T0|=kd + 1 such that (S0, T0) is a problematic pair. We crucially observe that every w∈Γ(y)\Tmust have at least two edges landing in S. Otherwise, picking a w∈Γ(y)\Tand s∈Ssuch that E(S, {w}) = {sw}and replacing (S, T) by (S\{s}, T ∪{w}) gives another problematic pair, which contradicts the minimality of S. Keeping all this in mind let us calculate the probability that such a problematic pair of sets (S, T) exists. We fix S⊆A\{y}and T⊆Γ(y) with |S|+|T|=kd + 1 and let j=|S|. We have to bound from above the probability that there are no edges from Sto Tand that all the vertices in Γ(y)\Thave at least two edges starting in S. To keep the notation simple let us write Γ(y)\T={w1, . . . , wj−1}and also name some events: E0={Γ−1(T)∩S=∅} and for 1 ⩽i⩽j−1, Ei= i ^ `=1{|Γ−1(w`)∩S|⩾2}. In this notation we have to bound Pr(E0∧Ej−1) = Pr(E0) j−1 Y i=1 Pr(Ei|E0∧Ei−1).(5) Recall that Proposition 13 states that for a fixed pair of sets (S, T) where |S|=j, the probability that E0occurs is bounded above by Pr(E0)⩽(1 + o(1)) exp −dj(kd + 1 −j) n. the electronic journal of combinatorics 20(1) (2013), #P60 18 So we are left to bound Pr(Ei|E0∧Ei−1) = Pr(|Γ−1(wi)∩S|⩾2|E0∧Ei−1) ⩽X s6=s0∈S Pr({s, s0} ⊆ Γ−1(wi)|E0∧Ei−1).(6) Edges in Gare chosen with probability d/n. If they were chosen independently, then the right hand side would be j 2(d/n)2.We show that a similar upper bound holds for (6). Lemma 24. Let sand s0be two distinct vertices in Sand 1⩽i⩽j−1be an integer. In the notation established above we have Pr({s, s0} ⊆ Γ−1(wi)|E0∧Ei−1)⩽d n−d2 . Proof. As Pr({s, s0} ⊆ Γ−1(wi)|E0∧Ei−1) equals Pr(s∈Γ−1(wi)|E0∧Ei−1) Pr(s0∈Γ−1(wi)|E0∧Ei−1∧s∈Γ−1(wi)),(7) it is enough to prove that both probabilities appearing in the product above are at most d/(n−d).Let us temporarily set Wi−1={w1, . . . , wi−1}. To bound the first probability in (7) we observe that kd =E(d+(s)|E0∧Ei−1) =X z∈Z\T Pr(z∈Γ(s)|E0∧Ei−1) ⩾X z∈Z\(T∪Wi−1) Pr(z∈Γ(s)|E0∧Ei−1) = (kn −kd +j−i) Pr(wi∈Γ(s)|E0∧Ei−1) ⩾(kn −kd) Pr(s∈Γ−1(wi)|E0∧Ei−1). The third (and final) equality follows from the symmetry of random biregular biparite graphs. For the second probability in (7) we proceed similarly kd =E(d+(s0)|E0∧Ei−1∧s∈Γ−1(wi)) ⩾X z∈Z\(T∪Wi−1) Pr(z∈Γ(s0)|E0∧Ei−1∧s∈Γ−1(wi)). In this case we can not deduce the desired bound from the symmetry of random biregular bipartite graphs since not all z∈Z\(T∪Wi−1) have the same role in the graph. Instead we prove via switching that the probability appearing in the sum above is minimal when z=wi. the electronic journal of combinatorics 20(1) (2013), #P60 19 Claim. Pr(wi∈Γ(s0)|E0∧Ei−1∧s∈Γ−1(wi)) ⩽Pr(z∈Γ(s0)|E0∧Ei−1∧s∈Γ−1(wi)), for all z∈Z\(T∪Wi−1). Let us quickly deduce the required inequality for the second probability appearing in (7) before proving the claim: kd ⩾(kn −kd +j−i) Pr(wi∈Γ(s0)|E0∧Ei−1∧s∈Γ−1(wi)) ⩾(kn −kd) Pr(s0∈Γ−1(wi)|E0∧Ei−1∧s∈Γ−1(wi)) . Proof of the claim. We only need to prove the claim when z6=wi. Subtracting the probability Pr({wi, z} ⊆ Γ(s0)|E0∧Ei−1∧s∈Γ−1(wi)) from both sides of the inequality we see that we have to prove that Pr(wi∈Γ(s0)∧z /∈Γ(s0)|E0∧Ei−1∧s∈Γ−1(wi)) is at most Pr(wi/∈Γ(s0)∧z∈Γ(s0)|E0∧Ei−1∧s∈Γ−1(wi)). This is equivalent to proving that |Gwi|⩽|Gz|where Gwi={G∈ G(k, n, d) : wi∈Γ(s0)∧z /∈Γ(s0)∧E0∧Ei−1∧s∈Γ−1(wi)} and Gz={G∈ G(k, n, d) : z∈Γ(s0)∧wi/∈Γ(s0)∧E0∧Ei−1∧s∈Γ−1(wi)}. Like in the proof of Lemma 15, we partition the two families of graphs in subfamilies according to the size of the intersection Γ−1(wi)∩Γ−1(z). For any 0 ⩽`⩽d−1 we define Gwi,` ={G∈ G(k, n, d):wi∈Γ(s0)∧z /∈Γ(s0)∧E0∧Ei−1∧s∈Γ−1(wi)∧|Γ−1(wi)∩Γ−1(z)|=`} and Gz,` ={G∈ G(k, n, d):z∈Γ(s0)∧wi/∈Γ(s0)∧E0∧Ei−1∧s∈Γ−1(wi)∧|Γ−1(wi)∩Γ−1(z)|=`}. The parameter `is at most d−1 in both Gwiand Gzas s0lies in exactly one of the two sets Γ−1(wi) and Γ−1(z). For 0 ⩽`⩽d−1 we count in two ways N`,the number of switchings between Gwi,` and Gz,`.In other words we double count the number of ordered pairs (Gwi, Gz)∈ Gwi,` ×Gz,` such that Gwiis a switching of Gzor equivalently that Gzis a switching of Gwi. Take Gwi∈ Gwi,` and v∈Γ−1(z)\Γ−1(wi).Applying the {s0wi, vz}-switching to Gwi results in a member of Gz,` as the switching does not affect any of the events E0, Ei−1,{s∈ Γ−1(wi)}and {|Γ−1(wi)∩Γ−1(z)|=`}(see Figure 3). There are (d−`) such vand so N`= (d−`)|Gwi,`|. the electronic journal of combinatorics 20(1) (2013), #P60 20 Figure 3: A graph Gwi∈ Gwiand its switching Gz∈ Gz. Solid lines represent edges and dashed lines missing edges. Now take Gz∈ Gz,` and v∈Γ−1(wi)\(Γ−1(z)∪{y, s}).Applying the {s0z, vwi}-switching to Gzresults in a member of Gwi,` as the switching does not affect any of the events E0, Ei−1,{s∈Γ−1(wi)}and {|Γ−1(wi)∩Γ−1(z)|=`}.There are at most (d−`) such v and so N`⩽(d−`)|Gz,`|. Thus |Gwi,`|⩽|Gz,`|for all 0 ⩽`⩽d−1 and |Gwi|= d−1 X `=0 |Gwi,`|⩽ d−1 X `=0 |Gz,`|=|Gz|. This completes the proof of the lemma. We resume the proof of Proposition 23. Inequality (6) becomes Pr(Ei|Ei−1∧E0)⩽j 2 d n−d2 . Substituting the above and the bound on Pr(E0) from Proposition 13 in (5) gives Pr(E0∧Ej−1)⩽(1 + o(1))j 2j−1d n−d2(j−1) exp −dj(kd + 1 −j) n. To bound the probability there is an S-minimal problematic pair with |S|⩽|T|we apply a union bound. For fixed jthere are at most kd jkd j−1ways to choose (S, T) subject to |S|=j. Thus the probability that there is an S-minimal problematic pair with |S|⩽|T| is O  (kd+1)/2 X j=2 kd j kd j−1j 2j−1d n−d2(j−1) exp −dj(kd + 1 −j) n . the electronic journal of combinatorics 20(1) (2013), #P60 21 Applying the well known bound a b⩽(ea b)b,using that n−d⩾n/2 as c=O(log(kd)) and writing `=j−1 we get that the probability that there is an S-minimal problematic pair with |S|⩽|T|is O  kd/2 X `=1 kde−kd2/n Ck2d4e−d(kd−`)/n n2`  for some large enough constant C. The definition of cgives that e−kd2/n =e−c/kd. Observing that kd −`⩾kd/2, the above sum is O e−c kd/2 X `=1 Ckd2 n2e−c/2 √kd !` . As kd2/n ⩽6 log(kd) and e−c⩽1 we get that the probability a problematic pair exists with |S|⩽|T|is O ∞ X l=1 C0log2(kd) √kd `!=Olog2(kd) √kd =o(1), where C0is another large enough constant. The case when |T|<|S|is similar. This time we chose T-minimal problematic pairs. The set Tcannot be a singleton as δ−(H)>1.The minimality of |T|implies that for every v∈A\Sthere are at least two edges starting at vand ending in T. The calculations needed are very similar to those given above and are omitted. Let us quickly recap the proof of Theorem 4. Proof of Theorem 4. When c→ −∞ Lemma 18 gives that there is no perfect matching in Hwhp. When c→+∞Lemma 18 and Lemma 20 give that Pr(δ−(H)>1∨δ+(H)>0) = 1−o(1).Proposition 23 states that the probability there is no perfect matching and δ+(H)>0 or δ−(H)>1 is o(1) provided that c⩽5 log(kd).So there is a perfect matching in Hwhp when c→+∞and c⩽5 log(kd).Finally Proposition 22 gives that there is a perfect matching in Hwhp when c⩾5 log(kd). We conclude the section with some remarks on the probability of the events A+ y0defined in (4) at the beginning of the proof of Lemma 20 on p.15. Suppose for a moment that Gwas chosen uniformly at random from the family of d+-regular bipartite graphs. In other words d+would be constant (and equal to kd), but no restriction on d−would exist. Then the neighbourhoods of vertices in Ywould be chosen uniformly at random from all (kd)-element subsets of Zand independently of each other. So the probability that Γ(y)∩Γ(y0) = ∅would be equal to kn−kd kd /kn kd. the electronic journal of combinatorics 20(1) (2013), #P60 22 The probability that A+ y0occurs increases in random biregular bipartite graphs as the event {Γ(y) = S1∧Γ(y0) = S2}is more likely when S1∩S2=∅than when S1∩S26=∅. This can be proved via switching and is due to the fact that vertices in Γ(y) have one of their dincoming edges “taken up” by y. Thus the edges coming out of y0are more likely to land in Z\Γ(y).We do not give the details of the proof here as a lower bound on Pr(A+ y0) is not necessary. We only state the lower bound and compare it with the upper bound coming from Proposition 13: kn−kd kd  kn kd⩽Pr(A+ y0)⩽ n−2 d−1 n−1 d−1!kd .(8) For d=o(n2/3) both bounds are asymptotically equal to exp(−kd2/n), which is easy to see using Stirling approximation to the binomial coefficients. This reinforces the idea that the dependence among small sets of edges in G(k, n, d) is small. 5 Remarks on Theorem 2 We only outline the proof of Theorem 2 as it is very similar to that of Theorem 4. The difference lies in the induced subgraph under consideration. In Theorem 2, His defined to be G[A, B] where A⊆Yand B⊆Zare sets of size kd. In Theorem 4, Bis taken to be the neighbourhood of some y∈A. This complicates some parts of the proof and is why we opted to give the proof of Theorem 4. When d=o(√n) it is straightforward to show there is no perfect matching in Hwhp. By Lemma 11 we know that for any y∈Athe expected value E(|Γ(y)∩B|) = o(1).Thus the probability Pr(Γ(y)∩B=∅) = 1−o(1) and consequently there is no perfect matching in Hwhp. The first step in dealing with larger values of dis to prove a variation of Proposition 13. As yno longer has a special role it is possible to bound the probability there are no edges from Sto Tby looking one by one at the vertices of Sor T. In Proposition 13 we only worked with the vertices in T. Proposition 25. Let Y, A, Z, B and Gbe like in the statement of Theorem 2. Let S⊆A and T⊆B. Suppose that z∈Tand |S|+d⩽n. Then Pr(Γ(S)∩T=∅)⩽Pr(Γ−1(z)∩S=∅)|T| ⩽1−|S| n|T|1−|S| n−1|T| . . . 1−|S| n−d+ 1|T| ⩽(1 + o(1)) exp −d|S||T| n. the electronic journal of combinatorics 20(1) (2013), #P60 23 Suppose that y∈Sand |T|+kd ⩽kn. Then Pr(Γ(S)∩T=∅)⩽Pr(Γ(y)∩T=∅)|S| ⩽1−|T| kn |S|1−|T| kn −1|S| . . . 1−|T| kn −kd + 1|S| ⩽(1 + o(1)) exp −d|S||T| n. Sketch of proof. For z∈Zthe probability there are no edges from Sto zequals Pr(Γ−1(z)∩S=∅) = n−|S| d n d=1−|S| n1−|S| n−1. . . 1−|S| n−d+ 1 as Γ−1(z) is chosen uniformly at random from all d-element subsets of Y\S. Now let T={z1, . . . , zt}.It can be shown via a switching argument very similar to that in the proof of Proposition 13 that for 2 ⩽i⩽t Pr(Γ−1(zi)∩S=∅ | Γ−1({z1, . . . , zi−1})∩S=∅)⩽Pr(Γ−1(zi)∩S=∅) = Pr(Γ−1(z)∩S=∅). This leads to Pr(Γ(S)∩T=∅)⩽Pr(Γ−1(z)∩S=∅)|T|. A similar approach is applied for the second claim. Next we prove a variation of Lemma 18 for the minimum degree of H,δ(H) = min{δ+(H), δ−(H)}.We no longer need to distinguish between δ+(H) and δ−(H) since B⊆Zis an arbitrary set. Lemma 26. Let Hbe the graph introduced in Theorem 2 and c=kd2 n−log(kd). Then (i) δ(H) = 0 whp when c→ −∞ or when dis a constant. (ii) δ(H)>0whp when c→+∞. In particular there is no perfect matching in Hwhp when c→ −∞. Sketch of proof. We consider two types of events: B+ y={Γ(y)∩B=∅} for y∈A and B− z={Γ−1(z)∩A=∅} for z∈B. the electronic journal of combinatorics 20(1) (2013), #P60 24 We also define the random variables Q+=X y∈A 1B+ y, Q−=X z∈B 1B− zand Q=Q++Q−. The condition δ(H)>0 holds if and only if Q= 0. The probability that B+ yoccurs equals Pr(B+ y) = kn−kd kd  kn kdfor all y∈A, as the neighbourhood of yis chosen uniformly from all (kd)-elements subsets of Z. Similarly Pr(B− z) = n−kd d n dfor all z∈B. When d=o(n2/3) Pr(B+ y),Pr(B− z)=Θexp −kd2 n. So E(Q) = kd(Pr(B+ y) + Pr(B− z)) = Θ kd exp −kd2 n= Θ(e−c). This shows that for d=o(n2/3) and c→+∞,E(Q) = o(1). If c→+∞, but dis not o(n2/3) it is easy to check that E(Q) = o(1). The second conclusion follows. If c→ −∞, it is adequate to prove that Pr(Q−= 0) = o(1) = Pr(Q+= 0). For this we apply Lemma 19 (Chebyshev’s inequality). The upper bound Var(Q−)⩽E(Q−) and Var(Q+)⩽E(Q+) derived in the proof of Lemma 18 holds as Proposition 25 gives that Pr(B− z∧B− z0)⩽Pr(B− z)2for z, z0∈Zand Pr(B+ y∧B+ y0)⩽Pr(B+ y)2for y, y0∈Y. Having proved the first claim of Theorem 2 we proceed to the second. For c⩾5 log(kd) we apply Proposition 25 in the way described in the proof of Proposition 22 to get that there is a perfect matching in Hwhp. We are only left with showing that when c→+∞and c⩽5 log(kd) the probability Pr(There is no perfect matching in H∧δ(H)>0) = o(1). This can be done in a very similar way to the proof of Proposition 23. Some amendments have to be made, for example one has to consider problematic pairs (S, T) where S⊆A and T⊆B, whereas in the proof of Theorem 4, we have S⊆A\{y}where yis some vertex in Aand T⊆Γ(y). the electronic journal of combinatorics 20(1) (2013), #P60 25