论文标题
稳定多项式，方向和匹配的简短调查
Short survey on stable polynomials, orientations and matchings
论文作者
论文摘要
这是关于稳定多项式及其应用理论的简短调查。它给出了Schrijver两个定理的独立证明。其中一位断言，对于$ d $ - 常规的两分图$ g $，$ 2N $顶点，完美匹配的数量，由$ \ mathrm {pm {pm}（g）$表示，满足$ \ mathrm {pm}（g）（g）\ geqq \ geq \ geq \ big（ \ bigg）^{n}。$$其他定理声称，即使对于$ d $，$ d $的欧拉尔级数量 - 常规的Graph $ g $ on $ n $ vertices上的$ n $ vertices，以$ \ varepsilon（g）$表示\ bigG（\ frac {\ binom {d} {d/2}} {2^{d/2}}} \ bigG）^n。$$来证明这些定理我们使用稳定的多项式理论，并给出了两个定理的普遍常规化。
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)\geq \bigg( \frac{(d-1)^{d-1}}{d^{d-2}} \bigg)^{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 $\varepsilon(G)$, satisfies $$\varepsilon(G)\geq \bigg(\frac{\binom{d}{d/2}}{2^{d/2}}\bigg)^n.$$ To prove these theorems we use the theory of stable polynomials, and give a common generalization of the two theorems.
