\documentclass[12pt]{article} \usepackage{latexsym} \oddsidemargin 0pt % Left margin on odd-numbered pages. \evensidemargin 0pt % Left margin on even-numbered pages. \marginparwidth 40pt % Width of marginal notes. \marginparsep 10pt % Horizontal space between outer margin and % marginal note % VERTICAL SPACING: \topmargin 0pt % Nominal distance from top of page to top of % box containing running head. \headsep 10pt % Space between running head and text. % DIMENSION OF TEXT: \textheight 9.0in %Height of text(including footnotes and figures, % excluding running head and foot). \textwidth 6.0in % Width of text line. \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 5 (1998), \#R13\hfill} \thispagestyle{empty} \newtheorem{theo}{Theorem} \newtheorem{lemma}[theo]{Lemma} \newtheorem{coro}[theo]{Corollary} \newtheorem{prop}[theo]{Proposition} %\newcommand{\leqsim}{<<} \newcommand{\HH}{{\cal H}} \renewcommand{\baselinestretch}{1.0} \title{Perfect matchings in $\epsilon$-regular graphs} \author{Noga Alon\\ \thanks{ 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.} {\small School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540}\\ {\small and}\\ {\small Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences,}\\ {\small Tel Aviv University, Tel Aviv, Israel; \texttt{noga@math.tau.ac.il}.} \and Vojtech R\"odl\thanks{ Research supported by Polish-US NSF grant INT-940671 and by NSF grant DMS-9704114.}\\ {\small Department of Mathematics and Computer Science,} \\ {\small Emory University, Atlanta, USA; \texttt{rodl@mathcs.emory.edu}.} \and Andrzej Ruci\'nski\\ \thanks{ Research supported by Polish-US NSF grant INT-940671 and by KBN grant 2 P03A 023 09.} {\small Department of Discrete Mathematics,} \\ {\small Faculty of Mathematics and Computer Science,} \\ {\small Adam Mickiewicz University, Pozna\'n, Poland; \texttt{rucinski@math.amu.edu.pl}.}} \vspace{20pt} \begin{document} \maketitle \begin{center} Submitted: December 10, 1997; Accepted: February 8, 1998. \end{center} \date{} \begin{abstract} A super $(d,\epsilon)$-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-\epsilon)n$ and $ (d+\epsilon) n$, and for every $U \subset V_1, W \subset V_2$ with $|U| \geq \epsilon n$, $|W| \geq \epsilon n$, $|\frac{e(U,W) }{|U||W|}-\frac{e(V_1,V_2)}{|V_1||V_2|}| < \epsilon.$ We prove that for every $1>d >2 \epsilon >0$ and $n>n_0(\epsilon)$, the number of perfect matchings in any such graph is at least $(d-2\epsilon)^n n!$ and at most $(d+2 \epsilon)^n n!$. The proof relies on the validity of two well known conjectures for permanents; the Minc conjecture, proved by Br\'egman, and the van der Waerden conjecture, proved by Falikman and Egorichev. \end{abstract} \begin{center} {\small Mathematics Subject Classification (1991); primary 05C50, 05C70} secondary 05C80 \end{center} \newpage An {\em $\epsilon$-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 \subset V_1, W \subset V_2$ with $|U| \geq \epsilon n$, $|W| \geq \epsilon n$, \begin{equation} \label{e1} \Bigg|\frac{e(U,W) }{|U||W|}-\frac{e(V_1,V_2)}{|V_1||V_2|}\Bigg| < \epsilon, \end{equation} 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 {\em density} of the graph. Such a graph is a {\em super $(d,\epsilon)$-regular graph} if, in addition, its minimum degree $\delta$ and its maximum degree $\Delta$ satisfy $$ (d-\epsilon)n \leq \delta \leq \Delta \leq (d+\epsilon) n. $$ In this note we prove the following result \begin{theo} Let $G$ be a super $(d,\epsilon)$-regular graph on $2n$ vertices, where $d > 2 \epsilon$ and $n>n_0(\epsilon)$. Then the number $M(G)$ of perfect matchings of $G$ satisfies $$ (d-2 \epsilon)^n n! \leq M(G) \leq (d+2 \epsilon)^n n!. $$ \end{theo} Thus, the number of perfect matchings in any super $(d,\epsilon)$-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 \cite{RR} to derive a new proof of the Blow-Up Lemma of Koml\'os, S\'ark\"ozy and Szemer\'edi. The upper bound in Theorem 1 is true for all bipartite graphs with maximum degree at most $(d+\epsilon)n$ on at least one side, and is an easy consequence of the Minc conjecture \cite{Mi} for permanents, proved by Br\'egman \cite{Br} (c.f. also \cite {AS} 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)\le\prod_{i=1}^nr_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 \in V_1,v \in 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) \leq (k!)^{n/k}$, where $k =\lfloor (d+\epsilon)n \rfloor$, and the upper bound follows by applying the Stirling approximation formula for factorials. It is worth noting that since every $\epsilon$-regular graph with density $d$ and $2n$ vertices contains, in each color class, at most $\epsilon n$ vertices of degree higher than $(d+\epsilon)n$, some version of the above upper bound is also true for any $\epsilon$-regular graph of density $d$. Namely, one can show that for every $d>0$, if $\epsilon$ is sufficiently small as a function of $d$, then for every $\epsilon$-regular graph $G$ on $2n $ vertices with density $d$ we have $$M(G)<(d+3 \epsilon)^n n!\ $$ provided $n >n_0(\epsilon)$. To prove the lower bound observe that by the van der Waerden conjecture, proved by Falikman \cite{Fa} and Egorichev \cite{Eg}, the number of perfect matchings in a bipartite $k$-regular 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=\lceil(d-2\epsilon)n\rceil$. This is proved in the next lemma. \begin{lemma} Let $G$ be a super $(d,\epsilon)$-regular graph on $2n$ vertices, $d > 2 \epsilon$. Then $G$ contains a spanning $k$-factor, where $k=\lceil(d-2\epsilon)n\rceil$. \end{lemma} In the proof of this lemma we will apply the following criterion for containing a $k$-factor, which can be found e.g. in \cite{LP}, page 70, Thm. 2.4.2. \begin{theo} 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\subseteq V_1$ and $Y\subseteq V_2$ \begin{equation} \label{e2} k|X| + k|Y| +e(V_1-X,V_2-Y)\ge kn\ .\Box \end{equation} \end{theo} \noindent {\bf 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 \epsilon)n$ is an integer. By Theorem 3, all we need is to prove inequality (\ref{e2}). If $|X|+|Y| \geq n$ then the left-hand side of (2) is at least $nk$, and we are done. Assume, thus, that $|X|+|Y|(d-2\epsilon)n=k$ neighbors in $V_1-X$, implying that $e(V_1-X,V_2-Y) \geq (n-|Y|)k$, and showing that the left-hand side of (2) is at least $k|X|+ k|Y|+k(n-|Y|) \geq kn$, as needed. Otherwise, $|V_1-X| \geq |V_2-Y| \geq \epsilon n$, and thus, by the $\epsilon$-regularity assumption and the obvious fact that $e(V_1,V_2)/(|V_1||V_2|) \geq d-\epsilon$, it follows that $e(V_1-X,V_2-Y)>(d-2 \epsilon) (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)\geq (d-2\epsilon) (n|X|+n|Y| +(n-|X|)(n-|Y|)) $$ $$ = (d-2\epsilon)(n^2+|X||Y|) \geq (d-2\epsilon) n^2=kn.$$ This completes the proof. $\Box$ \noindent {\bf Remark:} Note that in the last proof the assumption (\ref{e1}) may be relaxed, as we only used the fact that for every $U \subset V_1, W \subset V_2$, of cardinality at least $\epsilon n$ each, $\frac{e(W,U)}{|W||U|} \geq \frac{e(V_1,V_2)}{|V_1||V_2|}-\epsilon.$ 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 $\epsilon$ can also be omitted. \newpage \begin{thebibliography}{99} \bibitem{AS} N. Alon and J. Spencer, The Probabilistic Method, Wiley, New York, 1992. \bibitem{Br} L. M. Br\'egman, Some properties of nonnegative matrices and their permanents, Soviet Math. Dokl. 14 (1973), 945-949 [Dokl. Akad. Nauk SSSR 211 (1973), 27-30]. \bibitem{Eg} G.P. Egorichev, The solution of the van der Waerden problem for permanents, Dokl. Akad. Nauk SSSR 258 (1981), 1041-1044. \bibitem{Fa} 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. \bibitem{LP} L. Lov\'asz and M. D. Plummer, Matching Theory, Akad\'emiai Kiad\'o, Budapest, 1986 \bibitem{Mi} H. Minc, Nonnegative Matrices, Wiley, 1988 \bibitem{RR} V. R\"odl and A. Ruci\'nski, Perfect matchings in $\epsilon$-regular graphs and the Blow-up lemma, submitted. \end{thebibliography} \end{document}