Perfect matchings in ϵ-regular graphs

Noga Alon

∗School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540 and Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences,

Tel Aviv University, Tel Aviv, Israel; Email: noga@math.tau.ac.il.

Vojtech Rödl †Department of Mathematics and Computer Science,

Emory University, Atlanta, USA; Email: rodl@mathcs.emory.edu.

Andrzej Ruciński ‡Department of Discrete Mathematics, Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland; Email: rucinski@math.amu.edu.pl.

Submitted: December 10, 1997; Accepted: February 8, 1998.

Abstract

A super (d, ϵ)-regular graph on 2n vertices is a bipartite graph on the classes of vertices V_{1} and V_{2}, where |V_{1}| = |V_{2}| = n, in which the minimum degree and the maximum degree are between (d − ϵ)n and (d + ϵ)n, and for every U ⊂ V_{1}, W ⊂ V_{2} with |U| ≥ ϵn, |W | ≥ ϵn, |\frac{e(U,W)}{|U||W |} − \frac{e(V_{1},V_{2})}{|V_{1}||V_{2}|}| < ϵ. We prove that for every 1 > d > 2ϵ > 0 and n > n_{0}(ϵ), the number of perfect matchings in any such graph is at least (d − 2ϵ)^{n}n! and at most (d + 2ϵ)^{n}n!. The proof relies on the validity of two well known conjectures for permanents; the Minc conjecture, proved by Brégman, and the van der Waerden conjecture, proved by Falikman and Egorichev.

∗Research supported in part by a USA Israeli BSF grant, by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University and by a State of New Jersey grant.

†Research supported by Polish-US NSF grant INT-940671 and by NSF grant DMS-9704114.

‡Research supported by Polish-US NSF grant INT-940671 and by KBN grant 2 P03A 023 09.

0Mathematics Subject Classification (1991); primary 05C50, 05C70; secondary 05C80

An ϵ-regular graph on 2n vertices is a bipartite graph on the classes of vertices V_{1} and V_{2}, where |V_{1}| = |V_{2}| = n, in which for every U ⊂ V_{1}, W ⊂ V_{2} with |U| ≥ ϵn, |W | ≥ ϵn,

|\frac{e(U, W)}{|U||W |} − \frac{e(V_{1}, V_{2})}{|V_{1}||V_{2}|}| < ϵ,  (1)

where here e(X, Y) denotes the number of edges between X and Y. The quantity \frac{e(V_{1},V_{2})}{|V_{1}||V_{2}|} is called the density of the graph.

Such a graph is a super (d, ϵ)-regular graph if, in addition, its minimum degree δ and its maximum degree Δ satisfy

(d − ϵ)n ≤ δ ≤ Δ ≤ (d + ϵ)n.

In this note we prove the following result

Theorem 1 Let G be a super (d, ϵ)-regular graph on 2n vertices, where d > 2ϵ and n > n_{0}(ϵ). Then the number M(G) of perfect matchings of G satisfies

(d − 2ϵ)^{n}n! ≤ M(G) ≤ (d + 2ϵ)^{n}n!.

Thus, the number of perfect matchings in any super (d, ϵ)-regular graph on 2n vertices is close to the expected number of such matchings in a random bipartite graph with edge probability d (which is clearly d^{n}n!). This result is combined with some additional ideas in [7] to derive a new proof of the Blow-Up Lemma of Komlós, Sárközy and Szemerédi.

The upper bound in Theorem 1 is true for all bipartite graphs with maximum degree at most (d + ϵ)n on at least one side, and is an easy consequence of the Minc conjecture [6] for permanents, proved by Brégman [2] (c.f. also [1] for a probabilistic description of a proof of Schrijver). Indeed, the Minc conjecture states that the permanent of an n by n matrix A with (0, 1) entries satisfies

per(A) ≤ ∏_{i=1}^{n} r_{i}!^{1/r_{i}} ,

where r_{i} is the sum of the entries of the i-th row of A. To derive the upper bound in Theorem 1 apply this estimate to the matrix A = (a_{u,v})_{u∈V_{1},v∈V_{2}} in which a_{u,v} = 1 if u, v are adjacent and a_{u,v} = 0 otherwise. Here M(G) = per(A). Since the function x!^{1/x} is increasing, M(G) ≤ (k!)^{n/k}, where k = ⌊(d + ϵ)n⌋, and the upper bound follows by applying the Stirling approximation formula for factorials.

It is worth noting that since every ϵ-regular graph with density d and 2n vertices contains, in each color class, at most ϵn vertices of degree higher than (d + ϵ)n, some version of the above upper bound is also true for any ϵ-regular graph of density d. Namely, one can show that for every d > 0, if ϵ is sufficiently small as a function of d, then for every ϵ-regular graph G on 2n vertices with density d we have

M(G) < (d + 3ϵ)^{n}n!

provided n > n_{0}(ϵ).

To prove the lower bound observe that by the van der Waerden conjecture, proved by Falikman [4] and Egorichev [3], the number of perfect matchings in a bipartite kregular graph with n vertices in each color class is at least (k/n)^{n}n!. Thus it suffices to show that our graph contains a spanning k-regular subgraph (a k-factor), where k = ⌈(d − 2ϵ)n⌉. This is proved in the next lemma.

Lemma 2 Let G be a super (d, ϵ)-regular graph on 2n vertices, d > 2ϵ. Then G contains a spanning k-factor, where k = ⌈(d − 2ϵ)n⌉.

In the proof of this lemma we will apply the following criterion for containing a k-factor, which can be found e.g. in [5], page 70, Thm. 2.4.2.

Theorem 3 Let G be a bipartite graph on 2n vertices in the classes V_{1} and V_{2}, where |V_{1}| = |V_{2}| = n. Then G has a k-factor if and only if for all X ⊆ V_{1} and Y ⊆ V_{2}

k|X| + k|Y | + e(V_{1} − X, V_{2} − Y) ≥ kn .□  (2)

Proof of Lemma 2. We first assume, to simplify the notation and avoid using floor and ceiling signs when these are not crucial, that (d − 2ϵ)n is an integer.

By Theorem 3, all we need is to prove inequality (2). If |X|+|Y | ≥ n then the lefthand side of (2) is at least nk, and we are done. Assume, thus, that |X| + |Y | < n. Without loss of generality we may and will assume that |V_{1} − X| ≥ |V_{2} − Y |. If |V_{2} − Y | < ϵn, then, since |X| + |Y | < n, it follows that |X| < |V_{2} − Y | < ϵn and thus every vertex of V_{2} − Y has at least δ − |X| > (d − 2ϵ)n = k neighbors in V_{1} − X, implying that e(V_{1} − X, V_{2} − Y) ≥ (n − |Y |)k, and showing that the left-hand side of (2) is at least k|X| + k|Y | + k(n − |Y |) ≥ kn, as needed. Otherwise, |V_{1} − X| ≥ |V_{2} − Y | ≥ ϵn, and thus, by the ϵ-regularity assumption and the obvious fact that e(V_{1}, V_{2})/(|V_{1}||V_{2}|) ≥ d−ϵ, it follows that e(V_{1}−X, V_{2}−Y) > (d−2ϵ)(n−|X|)(n−|Y |). Therefore, the left-hand side of (2) is at least

k|X| + k|Y | + e(V_{1} − X, V_{2} − Y) ≥ (d − 2ϵ)(n|X| + n|Y | + (n − |X|)(n − |Y |))

= (d − 2ϵ)(n^{2} + |X||Y |) ≥ (d − 2ϵ)n^{2} = kn.

This completes the proof. □ Remark: Note that in the last proof the assumption (1) may be relaxed, as we only used the fact that for every U ⊂ V_{1}, W ⊂ V_{2}, of cardinality at least ϵn each, \frac{e(W,U)}{|W ||U|} ≥ \frac{e(V_{1},V_{2})}{|V_{1}||V_{2}|} − ϵ. For the lower bound in Theorem 1 the assumption about the maximum degree of G as well as the assumption that n is sufficiently large as a function of ϵ can also be omitted. the electronic journal of combinatorics 5 (1998), #R13 4

References

[1] N. Alon and J. Spencer, The Probabilistic Method, Wiley, New York, 1992.

[2] L. M. Brégman, Some properties of nonnegative matrices and their permanents, Soviet Math. Dokl. 14 (1973), 945-949 [Dokl. Akad. Nauk SSSR 211 (1973), 27-30].

[3] G.P. Egorichev, The solution of the van der Waerden problem for permanents, Dokl. Akad. Nauk SSSR 258 (1981), 1041-1044.

[4] D. I. Falikman, A proof of van der Waerden’s conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki 29 (1981), 931-938.

[5] L. Lovász and M. D. Plummer, Matching Theory, Akadémiai Kiadó, Budapest, 1986

[6] H. Minc, Nonnegative Matrices, Wiley, 1988

[7] V. Rödl and A. Ruciński, Perfect matchings in ϵ-regular graphs and the Blow-up lemma, submitted.