论文标题
二分的完美匹配作为真实多项式
Bipartite Perfect Matching as a Real Polynomial
论文作者
论文摘要
我们获得了对二分之一的完美匹配决策问题的描述，作为真实的多项式多项式。我们证明它具有全学位和$（1-O_N（1））\ CDOT 2^{n^2} $单元具有非零系数。相比之下，我们表明，在双表示中（切换0和1的角色），单元的数量仅在$θ（n \ log n）$中指数。我们的证明在很大程度上取决于以下事实：“覆盖覆盖”的图形晶格是欧拉（Eulerian）。
We obtain a description of the Bipartite Perfect Matching decision problem as a multilinear polynomial over the Reals. We show that it has full degree and $(1-o_n(1))\cdot 2^{n^2}$ monomials with non-zero coefficients. In contrast, we show that in the dual representation (switching the roles of 0 and 1) the number of monomials is only exponential in $Θ(n \log n)$. Our proof relies heavily on the fact that the lattice of graphs which are "matching-covered" is Eulerian.
