Perfect matchings in \(\varepsilon\)-regular graphs (Q1380203)

Summary: A super \((d,\varepsilon)\)-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-\varepsilon)n\) and \( (d+\varepsilon) n\), and for every \(U \subset V_1, W \subset V_2\) with \(|U|\geq \varepsilon n\), \(|W|\geq \varepsilon n\), \(\left|\frac{e(U,W) }{|U||W|}-\frac{e(V_1,V_2)}{|V_1||V_2|}\right|< \varepsilon.\) We prove that for every \(1>d >2 \varepsilon >0\) and \(n>n_0(\varepsilon)\), the number of perfect matchings in any such graph is at least \((d-2\varepsilon)^n n!\) and at most \((d+2 \varepsilon)^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.