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$?
$\begingroup$
$\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$– Brendan McKayMay 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$– TurboMay 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 BarberFeb 2, 2017 at 10:38
Add a comment
|