Perfect matchings in ε-regular graphs

Noga Alon, Vojtech Rödl, Andrzej Ruciński

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

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 languageEnglish (US)
Pages (from-to)14DUMMY
JournalElectronic Journal of Combinatorics
Volume5
Issue number1
StatePublished - 1998
Externally publishedYes

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