2014/06/03 by Péter Csíkvári, Csikvári, Péter · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1406.0766
openalex publication_date 2014/06/03 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Friedland's Lower Matching Conjecture asserts that if G is a d--regular\nbipartite graph on v(G)=2n vertices, and mk(G) denotes the number of\nmatchings of size k, then mk(G)
geq n
choose\nk2
left(
fracd-pd
right)n(d-p)(dp)np, where p=\(k)/(n). When\np=1, this conjecture reduces to a theorem of Schrijver which says that a\nd--regular bipartite graph on v(G)=2n vertices has at least\n
left(
frac(d-1)d-1dd-2
right)n perfect matchings. L. Gurvits\nproved an asymptotic version of the Lower Matching Conjecture, namely he proved\nthat
frac
ln mk(G)v(G)
geq
frac12
left(p
ln\n
left(
fracdp
right)+(d-p)
ln
left(1-
fracpd
right)-2(1-p)
ln\n(1-p)
right)+ov(G)(1).\n In this paper, we prove the Lower Matching Conjecture. In fact, we will prove\na slightly stronger statement which gives an extra cp\√(n) factor\ncompared to the conjecture if p is separated away from 0 and 1, and is\ntight up to a constant factor if p is separated away from 1. We will also\ngive a new proof of Gurvits's and Schrijver's theorems, and we extend these\ntheorems to (a,b)--biregular bipartite graphs.\n