On the connected blocks polytope

Combinatorial aspects of commutative algebra (05E40) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Review text

Let \(G\) be a connected graph and \(\mathcal{B}\) its set of blocks. For a subset of the blocks \(\mathcal{A} \subset \mathcal{B}\), the incidence vector \(\chi^\mathcal{A} \in \{0,1\}^\mathcal{B}\) is defined by\N\[\N\chi^\mathcal{A}_B:= \begin{cases} 1 & \mbox{if } B \in \mathcal{A},\\\N0 & \mbox{otherwise}. \end{cases}\N\]\NThe \textit{connected blocks polytope} \(\mathrm{CBP}(G)\) of \(G\) is the \((0,1)\)-polytope that is the convex hull of the set\N\[\N\{\chi^\mathcal{A} \mid A \subset B, \ G[\mathcal{A}] \mbox{ is connected}\},\N\]\Nwhere \(G[\mathcal{A}] =\bigcup_{B \in \mathcal{A}}B \). The connected blocks polytope of a graph is a generalization of several polytopes arising from graphs.\N\NThe paper under review gives a complete facet description of connected blocks polytopes, characterizes their edges and shows that they are Hirsch, that is, its diameter is at most \(k-d\), where \(k\) denotes the number of facets and \(d\) denotes the dimension. The authors also show that connected blocks polytopes admit a regular unimodular triangulation by constructing a squarefree Gröbner basis. In addition, they prove that connected blocks polytopes are Gorenstein of index \(2\) and that their \(h^*\)-vectors are unimodal.

Cites work

This page was built for publication: On the connected blocks polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6983234)