\magnification=1200
\hsize=4.2in
\nopagenumbers
\noindent
{\bf Noga Alon, Vojtech R\"odl and Andrzej Ruci\'nski}
\medskip
\noindent
{\bf Perfect Matchings in $\epsilon$-regular Graphs}
\vskip.5cm


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$,
$|{{e(U,W) }\over{|U||W|}}-{{e(V_1,V_2)}\over{|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. 


\bye