Perfectly Matchable Set Polynomials and h^*-polynomials for Stable Set Polytopes of Complements of Graphs

Abstract: 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

.

Recommendations

Cited in

(1)

This page was built for publication: Perfectly Matchable Set Polynomials and $h^*$-polynomials for Stable Set Polytopes of Complements of Graphs