# Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs

@article{Ebrahimnejad2021CountingAS, title={Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs}, author={Farzam Ebrahimnejad and Ansh Nagda and Shayan Oveis Gharan}, journal={ArXiv}, year={2021}, volume={abs/2103.08683} }

We show that the ratio of the number of near perfect matchings to the number of perfect matchings in d-regular strong expander (non-bipartite) graphs, with 2n vertices, is a polynomial in n, thus the Jerrum and Sinclair Markov chain [JS89] mixes in polynomial time and generates an (almost) uniformly random perfect matching. Furthermore, we prove that such graphs have at leastΩ(d)n many perfect matchings, thus proving the Lovasz-Plummer conjecture [LP86] for this family of graphs. ∗febrahim@cs… Expand

#### References

SHOWING 1-10 OF 26 REFERENCES

Perfect matchings in planar cubic graphs

- Mathematics, Computer Science
- Comb.
- 2012

It is proved that if G is a planar cubic graph with no cutedge, then G has at least 2-V (G), which is the number of perfect matchings in G. Expand

Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids

- Mathematics, Computer Science
- 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
- 2018

It is proved that the multivariate generating polynomial of the bases of any matroid is log-concave as a function over the positive orthant, and a general framework for approximate counting in discrete problems, based on convex optimization is developed. Expand

A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents

- Mathematics, Computer Science
- STOC '98
- 1998

We present a deterministic strongly polynomial algorithm that computes the permanent of a nonnegative n × n matrix to within a multiplicative factor of en. To this end we develop the first strongly… Expand

The number of matchings in random regular graphs and bipartite graphs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 1986

If 3 ≤ k ≤ (logn)13 and n is even, then the number of 1-factors in random labelled k-regular graphs of order n has expectation and variance is 2+o(n−23) e14 and variance e12. Expand

A proof of Alon's second eigenvalue conjecture and related problems

- Mathematics, Computer Science
- ArXiv
- 2004

These theorems resolve the conjecture of Alon, that says that for any > 0a ndd, the second largest eigenvalue of \ most" random dregular graphs are at most 2 p d 1+ (Alon did not specify precisely what \most" should mean or what model of random graph one should take). Expand

A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 2010

These results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph and Jerrum-Vazirani method of approximating permanent by near perfect matchings to construct a deterministic polynomial time approximation algorithm. Expand

Approximating the Permanent

- Mathematics, Computer Science
- SIAM J. Comput.
- 1989

A randomised approximation scheme for the permanent of a 0–1s presented, demonstrating that the matchings chain is rapidly mixing, apparently the first such result for a Markov chain with genuinely c... Expand

Counting 1-Factors in Regular Bipartite Graphs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 1998

We show that anyk-regular bipartite graph with 2nvertices has at least(k?1)k-1kk-2nperfect matchings (1-factors). Equivalently, this is a lower bound on the permanent of any nonnegative… Expand

A bound for the number of vertices of a polytope with applications

- Mathematics, Computer Science
- Comb.
- 2013

We prove that the number of vertices of a polytope of a particular kind is exponentially large in the dimension of the polytope. As a corollary, we prove that an n-dimensional centrally symmetric… Expand

Hafnians, perfect matchings and Gaussian matrices

- Mathematics
- 2014

We analyze the behavior of the Barvinok estimator of the hafnian of even dimension, symmetric matrices with nonnegative entries. We introduce a condition under which the Barvinok estimator achieves… Expand