Abstract
A super (d,ε)-regular graph on 2n vertices is a bipartite graph on the classes of vertices V1 and V2, where |V1| = |V2| = n, in which the minimum degree and the maximum degree are between (d - ε)n and (d + ε)n, and for every U ⊂ V1,W ⊂ V2 with |U| ≥ εn, |W| ≥ εn, |e(U,W)/|U||W| - e(V1,V2)/|V1||V2|| < ε. 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ε)nn! and at most (d + 2ε)nn!. 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.
Original language | English (US) |
---|---|
Pages (from-to) | 14DUMMY |
Journal | Electronic Journal of Combinatorics |
Volume | 5 |
Issue number | 1 |
State | Published - 1998 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics