1
$\begingroup$

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$?

$\endgroup$
3
  • 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$ May 4, 2016 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$
    – Turbo
    May 4, 2016 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, 2017 at 10:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.