13 problems

Perfect-contractility conjecture. The following conditions are equivalent:

Stable-set ideal conjecture. The following conditions are equivalent:

Given an integer $\ell \geq 1$, let $n_+(\ell)$ be the smallest number of vertices of a graph with $\operatorname{LS}_+$-rank $\ell$. A graph $G$ is $\ell$-minimal if $r_+(G)=\ell$…

Let $C_n$ be the cycle graph on $n$ vertices, let $p(C_n;z)$ denote its perfectly matchable set polynomial, and let $\overline{h}^*(C_n;z)$ denote the normalized $h^*$-polynomial o…

Let $G$ be a cycle graph with $\ell\geq 3$, let $R=E_{\mathbb{K}}[\operatorname{STAB}(G)]$ be its Ehrhart ring, and write its h-vector as $(h_0,h_1,\ldots,h_s)$ with $h_s\neq 0$. S…

Let $G^{0}_{k_{I}}=(V^{0}_{k_{I}},E^{0})$ be the edgeless graph with $V^{0}_{k_{I}}=\{1,\dots,k_{I}\}$, and let $r_{k_{I}}$ denote the number of facets of its stable set matrix pol…

Let $G$ be a perfect finite simple graph, and let $I_G$ denote the toric ideal associated with the stable set polytope of $G$. Let ${\mathcal A}$ be the class of graphs with no odd…

Ben Rebea's conjecture. The clique-family inequalities, together with the non-negativity constraints and clique inequalities, describe the stable set polytope of every quasi-line g…

$N_+$-Perfect Graph Conjecture. The stable set polytope of every $N_+$-perfect graph can be described by facet-defining inequalities with near-bipartite support.

Let ${\operatorname{LS}}_+(G)$ denote the Lovász–Schrijver positive semidefinite relaxation of the stable set polytope, and call $G$ ${\operatorname{LS}}_+$-perfect when…

Let ${\operatorname{LS}}_+(G)$ denote the Lovász–Schrijver positive semidefinite relaxation of the stable set polytope. A graph is ${\operatorname{LS}}_+$-perfect when…

A graph is near-perfect if its stable set polytope is defined by non-negativity constraints, clique constraints, and the full-rank constraint $\sum_{u\in V(G)}x_u\leq\alpha(G)$, wh…

For a graph $G$, let $\operatorname{STAB}(G)$ be its stable set polytope, $\operatorname{NB}(G)$ the near-bipartite polyhedral relaxation, and ${\operatorname{LS}}_+(G)$ the Lovász…