Short survey on stable polynomials, orientations and matchings

Abstract

This is a short survey about the theory of stable polynomials and its applications. It gives self-contained proofs of two theorems of Schrijver. One of them asserts that for a $d$--regular bipartite graph $G$ on $2n$ vertices, the number of perfect matchings, denoted by $\mathrm{pm}(G)$, satisfies $$\mathrm{pm}(G)\ge (\frac{(d-1{)}^{d-1}}{d^{d-2}}{)}^n.$$ The other theorem claims that for even $d$ the number of Eulerian orientations of a $d$--regular graph $G$ on $n$ vertices, denoted by $\epsilon (G)$, satisfies $$\epsilon (G)\ge (\frac{\left(\genfrac{}{}{0ex}{}{d}{d/2}\right)}{2^{d/2}}{)}^n.$$ To prove these theorems we use the theory of stable polynomials, and give a common generalization of the two theorems.