On the Ehrhart Theory of Generalized Symmetric Edge Polytopes

A matroid $\mathcal{M}$ consists of a pair $(E,\mathcal{I})$ where $E$ is finite and $\mathcal{I}\subseteq 2^{E}$ satisfies the following three properties:

1. (i)

   $\emptyset\in\mathcal{I}$;

2. (ii)

   if $I\in\mathcal{I}$ and $J\subseteq I$, then $J\in\mathcal{I}$; and

3. (iii)

   if $I,J\in\mathcal{I}$ and $|I|<|J|$, then there is some $x\in J-I$ such that $I\cup x\in\mathcal{I}$.

The set $E$ is called the ground set of $\mathcal{M}$ and the elements of $\mathcal{I}$ are called the independent sets of $\mathcal{M}$.

Matroids are useful for unifying various notions of “independence” in mathematics. For example, if $G$ is a (finite) graph, then there is a corresponding matroid $M(G)$ whose ground set is $E(G)$, the edge set of $G$, and whose independent sets are the sets of edges that form acyclic subgraphs of $G$. This matroid is called the cycle matroid of $G$, and any matroid that is isomorphic to $M(G)$ for some $G$ is a graphic matroid.

Another fundamental example of a matroid uses the columns of a $k\times n$ matrix $A$ as the ground set. Here, the independent sets are the columns of $A$ that form linearly independent sets. This matroid, denoted $M(A)$, is the vector matroid of $A$, and any matroid isomorphic to $M(A)$ for some matrix $A$ is called a representable matroid. More precisely, for a field $K$, the matrix $A$ is called $K$-representable if $M(A)$ is isomorphic to a vector matroid whose ground set consists of vectors in $K^{k}$. Hence, to say a matroid is representable is to say it is $K$-representable for some field $K$. On the other hand, a matroid is regular if it is $K$-representable over every field $K$.

The rank of a matroid $\mathcal{M}=(E,\mathcal{I})$ is defined as

When $\mathcal{M}$ is graphic, $\operatorname{rank}(\mathcal{M})$ is the size of a maximal spanning forest for any $G$ satisfying $\mathcal{M}=M(G)$. When $\mathcal{M}$ is representable, $\operatorname{rank}(\mathcal{M})=\operatorname{rank}(A)$ for any matrix $A$ satisfying $\mathcal{M}=M(A)$. With these definitions in hand, we can now describe some of the many benefits of working with regular matroids.

Note that a matrix satisfying the minor condition in (ii) is called totally unimodular and a matrix satisfying the minor condition in (iii) is called weakly unimodular. Borrowing more terminology from linear algebra, an element of $\mathcal{I}$ of cardinality $\operatorname{rank}(\mathcal{M})$ is called a basis of $\mathcal{M}$. The set $\mathcal{B}=\mathcal{B}(\mathcal{M})$ of bases, together with the ground set set $E$, can be used to define a matroid without explicit mention of independent sets; when this is done, we usually write $\mathcal{M}=(E,\mathcal{B})$.

Now, from a matroid $\mathcal{M}=(E,\mathcal{B})$ we may produce its dual matroid $\mathcal{M}^{*}=(E,\mathcal{B}^{*})$ by setting

Many properties of $\mathcal{M}^{*}$ can be easily deduced from $\mathcal{M}$. For example, $\mathcal{M}^{*}$ is representable if and only if $\mathcal{M}$ is representable. This does not hold for graphic matroids, though: if $\mathcal{M}$ is graphic, then $\mathcal{M}^{*}$ is graphic if and only if $\mathcal{M}=M(G)$ for some planar graph $G$.

There are additional notions in graph theory that have corresponding matroidal analogues. For example, a circuit in a matroid is a minimal dependent set; this is the analogue of a cycle in a graph. Letting $\mathcal{C}=\mathcal{C}(\mathcal{M})$ denote the set of circuits of a matroid, we define the matroid to be bipartite if each of the circuits has even size. This further allows one to call a matroid Eulerian if it is the dual of a bipartite matroid. These definitions reflect the fact that a connected, planar graph is Eulerian if and only if its dual is bipartite.

A loop of $\mathcal{M}$ is a single element of $E$ that forms a circuit; equivalently, a loop is an element that is in no basis of $\mathcal{M}$. On the other hand, a coloop of $\mathcal{M}$, called by some authors an isthmus, is a single element of $E$ that is in every basis of $\mathcal{M}$. Now, given a matroid $\mathcal{M}=(E,\mathcal{I})$ and an element $e\in E$ that is not a coloop, the deletion of $e$ from $\mathcal{M}$ is the matroid $\mathcal{M}-e$ having ground set $E-e$ and independent sets $\{I\in\mathcal{I}\mid e\notin I\}$. The contraction of $\mathcal{M}$ by $e\in E$, where $e$ is not a loop, is denoted $\mathcal{M}/e$ and has ground set $E-e$ and independent sets $\{I-e\mid e\in I\in\mathcal{I}\}$. Deletion and contraction are dual operations: if $e$ is neither a loop nor a coloop of $\mathcal{M}$, then $(\mathcal{M}-e)^{*}=\mathcal{M}^{*}/e$. Many binary operations on graphs extend to matroids as well: the direct sum, or 1-sum, of matroids $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ having disjoint ground sets $E_{1}$ and $E_{2}$ is $\mathcal{M}_{1}\oplus\mathcal{M}_{2}=(E_{1}\cup E_{2},\mathcal{I}_{3})$, where $\mathcal{I}_{3}$ consists of independent sets of the form $I=I_{1}\cup I_{2}$ where $I_{1}\in\mathcal{I}_{1}$ and $I_{2}\in\mathcal{I}_{2}$.

To define the next operation we assume that $E_{1}\cap E_{2}=\{p\}$ and call this element the basepoint. The parallel connection, denoted $P(\mathcal{M}_{1},\mathcal{M}_{2})$, has ground set $E_{1}\cup E_{2}$ and is most efficiently defined through its circuits: if $p$ is neither a loop nor a coloop of $\mathcal{M}_{1}$, then

If $p$ is a loop of $\mathcal{M}_{1}$, then we set

Similarly, if $p$ is a coloop of $\mathcal{M}_{1}$, then we set

Of course, if $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ have disjoint ground sets, then a point of each ground set may be selected and relabeled $p$ to fall into these definition, although the resulting parallel connection may then depend on which points were selected. An important property of this operation is that it preserves regularity: if $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ are both regular matroids, then so is $P(\mathcal{M}_{1},\mathcal{M}_{2})$ [14, Corollary 7.1.25].

It is frequently more tractable to gather the desired information about a polytope by decomposing it into subpolytopes. A dissection, or subdivision, of a polytope $P$ is a collection $\mathcal{S}$ of full-dimensional subpolytopes of $P$ whose union is $P$ and for any $S_{1},S_{2}\in\mathcal{S}$, the intersection $S_{1}\cap S_{2}$ is a face of both. A triangulation of $P$ is a dissection in which every $S\in\mathcal{S}$ is a simplex. There are many ways to create triangulations of a polytope; we will be concerned with one that has been recently introduced in the study of ordinary SEPs in particular.

Given an oriented subgraph $H$ of a graph $G$ on $[n]$, let $Q_{H}=\operatorname{conv}\{e_{i}-e_{j}\mid ij\in H\}$. Thus, if $T$ is a spanning tree of $G$, then $Q_{T}$ is a simplex contained in $\Sigma(G)$. In fact, $Q_{T}$ is a full-dimensional simplex contained in the boundary of $\Sigma(G)$. Further still, $Q_{T}$ is a unimodular simplex: it has normalized volume $1$. It follows that the simplex $\operatorname{conv}\{Q_{T}\cup\{0\}\}$ is a full-dimensional, unimodular simplex contained in $\Sigma(G)$. It is desirable, then, to find a collection $\mathcal{T}$ of oriented spanning trees of $G$ so that the set $\{Q_{T}\mid T\in\mathcal{T}\}$ forms a triangulation of the boundary of $\operatorname{\Sigma}(G)$. Such a set $\mathcal{T}$ is called a dissecting tree set for $G$.

Of course, if $\mathcal{T}$ is a dissecting tree set for $G$, then the normalized volume of $\Sigma(G)$ is exactly $|\mathcal{T}|$. However, there is more information about $\Sigma(G)$ to be extracted from $\mathcal{T}$. To describe this information, consider a fixed vertex $v$ in an oriented tree $T$. For each edge $e\in T$ we say that $e$ points away from $v$ in $T$ if $v$ is contained in the same component as the tail of $e$ in $T-e$. Otherwise, we say $e$ points towards $v$ in $T$.

In order to determine when we have a dissecting tree set, we turn to Gröbner basis techniques. Here, we will introduce the necessary algebraic background to prove our main results. We largely follow the framework given in [9]. For more details about monomial orders and their relationships to triangulations of polytopes, see [16, Chapter 8].

Recall that, given a lattice polytope $P\subseteq\mathbb{R}^{n}$ and a field $K$, we may construct a semigroup algebra

where $x^{v}=x_{1}^{v_{1}}\cdots x_{n}^{v_{n}}$. The toric ideal of $P$ is defined as the kernel of the map

defined by setting $\pi_{P}(t_{v})=x^{v}z$; this ideal is denoted $I_{P}$.

Consider a monomial order $\prec$ on $K[t_{v}\mid v\in P\cap\mathbb{Z}^{n}]$ and any ideal $I$ of this algebra. For each polynomial $f\in I$, its initial term with respect to $\prec$, denoted $\operatorname{in}_{\prec}(f)$, is the term of $f$ that is greatest with respect to $\prec$. The initial ideal of $I$ with respect to $\prec$ is

A Gröbner basis of $I$, which we denote by $\mathscr{G}$, is a finite generating set of $I$ such that $\operatorname{in}_{\prec}(I)=(\operatorname{in}_{\prec}(g)\ |\ g\in\mathscr{G})$. We call $\mathscr{G}$ reduced if each element has a leading coefficient of $1$ and if for any $g_{1},g_{2}\in\mathscr{G}$, $\operatorname{in}_{\prec}(g_{1})$ does not divide any term of $g_{2}$. There are many Gröbner bases of $I$ but there is exactly one reduced Gröbner basis of $I$.

Now suppose $P\subseteq\mathbb{R}^{n}$ is an $n$-dimensional lattice polytope and $P\cap\mathbb{Z}^{n}=\{l_{1},\ldots,l_{s}\}$. Choose a weight vector $w=(w_{1},\ldots,w_{s})\in\mathbb{R}^{s}$ such that the polytope

is $(n+1)$-dimensional, i.e., $P_{w}$ does not lie in an affine hyperplane of $\mathbb{R}^{n+1}$. Some facets of $P_{w}$ will have outward-pointing normal vectors with a negative last coordinate. By projecting these facets back to $\mathbb{R}^{n}$, we obtain the facets of a polyhedral subdivision $\Delta_{w}(P)$ of $P$. Any triangulation that can be obtained in this way for an appropriate choice of $w$ is called a regular triangulation. Importantly, regular unimodular triangulations are in one-to-one correspondence with reduced Gröbner bases whose initial terms are all squarefree [16, Corollary 8.9]. It is well-known that any monomial order obtained as a graded reverse lexicographic (grevlex) order can be represented by a weight vector.

In the case of $P=\Sigma(\mathcal{M})$ for a regular matroid $\mathcal{M}=(E,\mathcal{I})$, we can identify $K[t_{v}\mid v\in P\cap\mathbb{Z}^{n}]$ with

Here, we let $x_{e}$ correspond to the column of a fixed matrix $M$ realizing $\mathcal{M}$ that corresponds to $e$, and we will let $y_{e}$ correspond to the negative of this column. The variable $z$, then, corresponds to the origin. So, for each $e\in E$, we can treat $x_{e}$ and $y_{e}$ as encoding an orientation of $e$. For ease of notation, if we are considering $e\in E$ with a particular orientation, then we let $p_{e}$ denote the corresponding variable and $q_{e}$ the variable corresponding to the opposite orientation.