Abstract. We generalize the definition of the [Formula: see text]-index of an Eulerian poset to the class of semi-Eulerian posets. For connected simplicial semi-Eulerian Buchsbaum posets, we show that all coefficients of the [Formula: see text]-index are nonnegative. This proves a conjecture of Novik for odd-dimensional manifolds and extends it to the even-dimensional case.

Abstract In this paper, we study the connected blocks polytope, which, apart from its own merits, can be seen as the generalization of certain connectivity based or Eulerian subgraph polytopes. We provide a complete facet description of this polytope, characterize its edges and show that it is Hirsch. We also show that connected blocks polytopes admit a regular unimodular triangulation by constructing a squarefree Gröbner basis. In addition, we prove that the polytope is Gorenstein of index 2 and that its $$h^*$$ h ∗ -vector is unimodal.

Abstract Given a graph $$G=(V,E)$$ G = ( V , E ) and a set $$S \subseteq \left( {\begin{array}{c}V\\ 2\end{array}}\right) $$ S ⊆ V 2 of terminal pairs, the minimum multicut problem asks for a minimum edge set $$\delta \subseteq E$$ δ ⊆ E such that there is no s-t-path in $$G -\delta $$ G - δ for any $$\{s,t\}\in S$$ { s , t } ∈ S . For $$|S|=1$$ | S | = 1 this is the well known s-t-cut problem, but in general the minimum multicut problem is NP-complete, even if the input graph is a tree. The multicut polytope $$\textsc {MultC}^\square (G,S)$$ M U L T C □ ( G , S ) is the convex hull of all multicuts in G; the multicut dominant is given by $$\textsc {MultC}(G,S)=\textsc {MultC}^\square (G,S)+\mathbb {R}^E_{{\ge 0}}$$ M U L T C ( G , S ) = M U L T C □ ( G , S ) + R ≥ 0 E . The latter is the relevant object for the minimization problem. While polyhedra associated to several cut problems have been studied intensively there is only little knowledge for multicut. We investigate properties of the multicut dominant and in particular derive results on liftings of facet-defining inequalities. This yields a classification of all facet-defining path- and edge inequalities. Moreover, we investigate the effect of graph operations such as node splitting, edge subdivisions, and edge contractions on the multicut-dominant and its facet-defining inequalities. In addition, we introduce facet-defining inequalities supported on stars, trees, and cycles and show that the former two can be separated in polynomial time when the input graph is a tree.

Abstract. We study [Formula: see text]-vectors associated with [Formula: see text]-vectors of symmetric edge polytopes both from a deterministic and a probabilistic point of view. On the deterministic side, we prove nonnegativity of [Formula: see text] for any graph and completely characterize the case when [Formula: see text]. The latter also confirms a conjecture by Lutz and Nevo in the realm of symmetric edge polytopes. On the probabilistic side, we show that the [Formula: see text]-vectors of symmetric edge polytopes of most Erdős–Rényi random graphs are asymptotically almost surely nonnegative up to any fixed entry. This proves that Gal’s conjecture holds asymptotically almost surely for arbitrary unimodular triangulations in this setting.