4 The State Polytope

4.1 Basic Concepts of Polyhedral Geometry

In the first half of this chapter we review some basic concepts from polyhedral geometry. In the second half we introduce the state polytope of an ideal \(I\). It has the property that its vertices are in a natural bijection with the distinct initial ideals \(\mathrm{in}_{{\lt}}(I)\).

Definition 29 Polyhedron

✓

A polyhedron is a finite intersection of closed half-spaces in \(\mathbb {R}^n\). Thus a polyhedron \(P\) can be written as \(P = \{ \mathbf{x} \in \mathbb {R}^n : A \cdot \mathbf{x} \le \mathbf{b} \} \), where \(A\) is a matrix with \(n\) columns.

If \(\mathbf{b} = 0\) then there exist vectors \(\mathbf{u}_1, \dots , \mathbf{u}_m \in \mathbb {R}^n\) such that

\begin{equation} \label{eq:polyhedral_cone_V_rep} P = \operatorname {pos}(\{ \mathbf{u}_1, \dots , \mathbf{u}_m\} ) := \{ \lambda _1 \mathbf{u}_1 + \dots + \lambda _m \mathbf{u}_m : \lambda _1, \dots , \lambda _m \in \mathbb {R}_+ \} . \end{equation}

Definition 30 Polyhedral Cone

✓

A polyhedron of the form ?? is called a (polyhedral) cone.

Here and throughout this book \(\mathbb {R}_+\) denotes the non-negative reals. The polar of a cone \(C\) is defined as

\[ C^* = \{ \boldsymbol {\omega } \in \mathbb {R}^n : \boldsymbol {\omega } \cdot \mathbf{c} \le 0 \text{ for all } \mathbf{c} \in C \} . \]

Definition 31 Polytope

✓

A polyhedron \(Q\) which is bounded is called a polytope. Every polytope \(Q\) can be written as the convex hull of a finite set of points

\begin{equation} \label{eq:polytope_convex_hull} Q = \operatorname {conv}(\{ \mathbf{v}_1, \dots , \mathbf{v}_m\} ) := \left\{ \sum _{i=1}^m \lambda _i \mathbf{v}_i : \lambda _1, \dots , \lambda _m \in \mathbb {R}_+, \sum _{i=1}^m \lambda _i = 1 \right\} . \end{equation}

Here are two examples of 3-dimensional polytopes: The cube and the octahedron.