论文标题
完全可匹配的集合多项式和$ h^*$ - 稳定的套件的多项式图形互补
Perfectly Matchable Set Polynomials and $h^*$-polynomials for Stable Set Polytopes of Complements of Graphs
论文作者
论文摘要
图$ g $的子集$ s $，如果$ s $引起的子图包含完美的匹配，则称为$ g $完全匹配的$ g $。 Ohsugi和Tsuchiya首先是$ g $的完全匹配的$ g $的多项式，是（普通的）生成函数$ p（g; z）$，对于$ g $的完全匹配的集合。 在这项工作中，我们为任意（简单）图的计算$ p（g; z）$提供明确的复发，并使用它们来计算某些晶格多型的ehrhart $ h^*$ - 多项式。也就是说，我们表明$ p（g; z）$是某些类别稳定的集合多型的$ h^*$ - 多项式，其顶点对应于$ g $的稳定集。
A subset $S$ of vertices of a graph $G$ is called a perfectly matchable set of $G$ if the subgraph induced by $S$ contains a perfect matching. The perfectly matchable set polynomial of $G$, first made explicit by Ohsugi and Tsuchiya, is the (ordinary) generating function $p(G; z)$ for the number of perfectly matchable sets of $G$. In this work, we provide explicit recurrences for computing $p(G; z)$ for an arbitrary (simple) graph and use these to compute the Ehrhart $h^*$-polynomials for certain lattice polytopes. Namely, we show that $p(G; z)$ is the $h^*$-polynomial for certain classes of stable set polytopes, whose vertices correspond to stable sets of $G$.
