### 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, |e(U,W)/|U||W| - 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.

Original language | English (US) |
---|---|

Pages (from-to) | 14DUMMY |

Journal | Electronic Journal of Combinatorics |

Volume | 5 |

Issue number | 1 |

State | Published - Dec 1 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

## Fingerprint Dive into the research topics of 'Perfect matchings in ε-regular graphs'. Together they form a unique fingerprint.

## Cite this

*Electronic Journal of Combinatorics*,

*5*(1), 14DUMMY.