English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Friedland's Lower Matching Conjecture asserts that if $G$ is a $d$--regular bipartite graph on $v(G)=2n$ vertices, and $m_k(G)$ denotes the number of matchings of size $k$, then $$m_k(G)\geq {n \choose k}^2\left(\frac{d-p}{d}\right)^{n(d-p)}(dp)^{np},$$ where $p=\frac{k}{n}$. When $p=1$, this conjecture reduces to a theorem of Schrijver which says that a $d$--regular bipartite graph on $v(G)=2n$ vertices has at least $$\left(\frac{(d-1)^{d-1}}{d^{d-2}}\right)^n$$ perfect matchings. L. Gurvits proved an asymptotic version of the Lower Matching Conjecture, namely he proved that $$\frac{\ln m_k(G)}{v(G)}\geq \frac{1}{2}\left(p\ln \left(\frac{d}{p}\right)+(d-p)\ln \left(1-\frac{p}{d}\right)-2(1-p)\ln (1-p)\right)+o_{v(G)}(1).$$ In this paper, we prove the Lower Matching Conjecture. In fact, we will prove a slightly stronger statement which gives an extra $c_p\sqrt{n}$ factor compared to the conjecture if $p$ is separated away from $0$ and $1$, and is tight up to a constant factor if $p$ is separated away from $1$. We will also give a new proof of Gurvits's and Schrijver's theorems, and we extend these theorems to $(a,b)$--biregular bipartite graphs.

Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems