Schrijver's lower bound gives the number of perfect matchings in a $k$-regular bipartite graph as $\Big(\frac{(k-1)^{k-1}}{k^{k-2}}\Big)^n$. What is the corresponding lower bound for minimum-degree $k$ and average degree $k'$ bipartite graphs given that at least an $\alpha\in(0,1)$ fraction of the vertices of at least one color have degree $k$?

  • 3
    $\begingroup$ It is possible to have no perfect matchings at all no matter how high the minimum degree is. Take the union of K(k,k+1) and K(k+1,k). A more interesting (but vague) question is to ask what is the weakest condition that regularity can be replaced by and still have an exponential lower bound. The same example shows that having only two different degrees is not enough. $\endgroup$ – Brendan McKay May 4 '16 at 1:08
  • $\begingroup$ @BrendanMcKay I did not think of this before. Interesting. May be there degree sequence approach or fraction of vertices with min-degree? $\endgroup$ – Brout May 4 '16 at 1:22
  • $\begingroup$ See mathoverflow.net/questions/261115/… for an answer to a very similar question. Essentially minimum degree $k$ and at least one perfect matching guarantees at least $k!$. $\endgroup$ – Ben Barber Feb 2 '17 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.