# Staged tree models with toric structure

Christiane Görgen, Aida Maraj, and Lisa Nicklasson
Max Planck Institute for Mathematics in the Sciences

###### Abstract

A staged tree model is a discrete statistical model encoding relationships
between events. These models are realised by directed trees with coloured
vertices. In algebro-geometric terms, the model consists of points inside a
toric variety. For certain trees, called balanced, the model is in fact the
intersection of the toric variety and the probability simplex. This gives the
model a straightforward description, and has computational advantages. In this
paper we show that the class of staged tree models with a toric structure
extends far outside of the balanced case, if we allow a change of coordinates.
It is an open problem whether all staged tree models have toric structure.

##  1 Introduction

_Staged tree models_ are discrete statistical models introduced by Smith and
Anderson in 2008 [27] that record conditional independence relationships among
certain events. They are realisable as rooted trees with coloured vertices and
labelled edges directed away from the root, called _staged trees_. Vertices in
a staged tree represent events, edge labels represent conditional
probabilities, and the colours on the vertices represent an equivalence
relation—vertices of the same colour have the same outgoing edge labels. We
use $\theta(e)$ to denote the label associated to an edge $e$. The sum of the
labels of all edges emanating from the same vertex in a staged tree must be
equal to one. The staged tree model itself is then defined as the set of
points in $\mathbb{R}^{n}$ parametrised by multiplying edge labels along the
root-to-leaf paths $\lambda_{1},\ldots,\lambda_{n}$ in the staged tree
$\mathcal{T}$:

$\mathcal{M}_{\mathcal{T}}=\left\\{\biggl{(}\prod_{e\in
E(\lambda_{r})}\theta(e)\biggr{)}_{r=1,\ldots,n}\ \left|\
0<\theta(e)<1,\,\sum_{e\in E(v)}\theta(e)=1\text{ for all vertices }v\text{ in
}\mathcal{T}\right.\right\\}$ (1)

where $E(v)$ is the set of edges which emanate from a vertex $v$, and
$E(\lambda_{r})$ is the set of edges of the $r^{\text{th}}$ root-to-leaf path,
$r=1,\ldots,n$. The local sum-to-one conditions ensure that the multiplication
rule of edge labels along root-to-leaf paths in $\mathcal{T}$ induces a well
defined probability distribution. The visual presentation via a coloured tree
has been the key to the staged tree models’ increasing popularity in both
algebra [8, 1, 9, 11] and statistics [24, 19, 4, 25, 17].

By the description Eq. 1, a staged tree model can be interpreted as the
variety of the kernel of a map $\varphi_{\mathcal{T}}$, formally introduced in
Eq. 3, intersected with the probability simplex. We say that a staged tree
model has _toric structure_ if the variety of $\ker\varphi_{\mathcal{T}}$ is a
toric variety. This is equivalent to $\ker\varphi_{\mathcal{T}}$ being a
binomial ideal, possibly after an appropriate linear change of variables.
Duarte and Görgen [8] show that when the tree is balanced, one can safely
ignore the sum-to-one conditions, and the ideal $\ker\varphi_{\mathcal{T}}$ is
binomial. This class has wide intersections with Bayesian networks/directed
graphical models and hierarchical models. The majority of staged trees,
however, are not balanced. This is true even for the small portion of staged
trees which are also Bayesian networks, making the algebraic study of these
models a new and necessary task.

Non-balanced staged trees appear naturally in applications. The most basic
example is one of flipping a biased coin with probability $\theta_{1}$ for
heads, and $\theta_{2}=1-\theta_{1}$ for tails. If it shows heads, flip it
again. The graph in Fig. 1 is a staged tree presentation of this experiment.

Figure 1: The coin-flip model
$\mathcal{M}_{\mathcal{T}}=\\{(\theta_{1}^{2},\theta_{1}\theta_{2},\theta_{2})\mid
0<\theta_{1},\theta_{2}<1,\,\theta_{1}+\theta_{2}=1\\}\subset(0,1)^{3}$
represented by a binary, non-squarefree, not balanced staged tree. Both
internal vertices are in the same stage.

The points in the corresponding model have the parametrisation
$(\theta_{1}^{2},\theta_{1}\theta_{2},\theta_{2})$ for positive
$\theta_{1},\theta_{2}$ that sum up to one. They are the solution set inside
the probability simplex to the non-binomial equation
$p_{1}p_{3}-p_{1}p_{2}+p_{2}^{2}=0$ in the polynomial ring
$\mathbb{R}[p_{1},p_{2},p_{3}]$. Contrary to the balanced case, as the example
suggests, the ideals $\ker\varphi_{\mathcal{T}}$ of non-balanced staged trees
are not generated by binomials; their generating sets are often complicated.

The present paper takes a large leap and proves that in many cases non-
balanced staged tree models have also a toric structure; one needs to find an
appropriate linear change of variables to reveal this friendly structure. For
instance, the linear change of coordinates $p_{1}=q_{1},p_{2}=q_{2}-q_{1}$,
and $p_{3}=q_{3}-q_{2}$ in the example above bijectively transforms the
defining variety into the set of points $(q_{1},q_{2},q_{3})$ that satisfy the
binomial equation $q_{1}q_{3}-q_{2}^{2}=0$.

Why is toric a desirable property? For one, the literature on the algebra of
toric varieties is already very rich and with close connections to polyhedral
geometry and combinatorics. Most importantly, toric ideals have shown to be
particularly useful in algebraic statistics since with the very first works
[7, 26, 16] in this area. For instance, generating sets of toric varieties
produce Markov bases and contribute in hypothesis testing algorithms [7],
toric varieties are intrinsically linked to smoothness criteria in exponential
families [15], and the polytope associated to a toric model is useful when
studying the existence of maximum likelihood estimates [13].

In previous work, the parametrisation defining a staged tree model Eq. 1 is
often assumed to be squarefree. In other words, in the tree graph no two
vertices are in the same stage along the same root-to-leaf path. The theory on
staged tree models with a non-squarefree parametrisation is underdeveloped
because they pose interpretational ambiguities in a statistical context [5]
and computational challenges in algebraic algorithms [18]. However, as the
example of the coin flip confirms, non-squarefree staged tree models are very
natural, and both balanced and non-balanced staged trees can be non-
squarefree. None of the results in our paper are restricted to squarefree
staged tree models, which makes this paper the first to tackle equations
defining non-squarefree staged tree models.

This article is organised as follows. In Section 2 we review the background
literature on staged trees and introduce combinatorial and algebraic tools for
studying these models. We discuss operations called swap and resize on a
staged tree, which are used in Section 3 to prove that all balanced staged
tree models have a quadratic Gröbner basis. It turns out that balanced staged
trees carry properties that are central in commutative algebra, namely they
are Koszul, normal, and Cohen-Macaulay. In Section 4 we prepare for our
investigation of non-balanced trees with toric structure. Informally, the idea
is to look for an ideal inside $\ker\varphi_{\mathcal{T}}$ that is binomial
after a linear change of variables, which can be used to detect a binomial
structure of $\ker\varphi_{\mathcal{T}}$. This theory is then set to practice
in Section 5 where we successfully extend the class of staged trees with toric
structure. Our new class contains trees with a certain subtree-inclusion
property, balanced trees, and combinations of both. In Section 6 we explore
the structure of staged tree models where all vertices share the same colour.
We connect these so-called one-stage trees to Veronese embeddings and show
that all binary one-stage trees are toric. The paper ends in Section 7 with a
discussion on further research directions, conjectures, and examples of staged
trees for which we cannot currently decide whether or not they have toric
structure.

##  2 Staged tree models

A discrete statistical model can be regarded as a subset of the open
probability simplex

${\Delta^{\circ}_{n-1}}={\\{p\in\mathbb{R}^{n}\mid p_{1}+\ldots+p_{n}=1\text{
and }p_{r}\in(0,1)\text{ for all }r=1,\ldots,n\\}}$

of dimension $n-1$. Thus, given a staged tree $\mathcal{T}$, the staged tree
model $\mathcal{M}_{\mathcal{T}}$ in Equation 1 defines a discrete statistical
model. This section starts by studying the combinatorics of a staged tree, and
then introduces the main algebraic object associated to
$\mathcal{M}_{\mathcal{T}}$.

###  2.1 Combinatorics of staged tree models

Given a staged tree $\mathcal{T}$ let $V$ denote its vertex set and $E$ its
edge set. The staged tree $\mathcal{T}$ comes with an equivalence relation
$\sim$ on its vertices. Formally, we say that two inner vertices $u$ and $v$
in $V$ are in the same stage, or share the same colour $c$, if the labels of
the outgoing edges of both vertices are the same. Leaves are by convention
assumed to be trivially in the same stage since their outgoing edge sets are
empty. For two vertices of different stages, the sets of labels of their
outgoing edges are assumed to be disjoint. In depictions of staged trees we
always assume that the outgoing edges of vertices with the same colour are
ordered in the same way, such that their labels are pairwise identified from
top to bottom. Figures 1 and 2 depict first examples.

For simplicity, leaves of a staged tree will be numbered $1,\dots,n$ and the
root-to-leaf paths denoted $\lambda_{1},\dots,\lambda_{n}$. To each leaf an
atomic probability $p_{r}=\prod_{e\in E(\lambda_{r})}\theta(e)$ is associated,
$r=1,\dots,n$. The notation $p_{[v]}$ is shorthand for the probability of
passing through the vertex $v$. Formally, $p_{[v]}$ is the sum of the atomic
probabilities $p_{r}$ for which the root-to-leaf path $\lambda_{r}$ passes
through vertex $v$. If $v_{i}$ is the $i^{\text{th}}$ child of $v$, the label
of the edge $(v,v_{i})$ is equal to the fraction
$\nicefrac{{p_{[v_{i}]}}}{{p_{[v]}}}$ [19]. As a consequence, the staged tree
model $\mathcal{M}_{\mathcal{T}}$ can be described via equations
$p_{[u]}p_{[v_{i}]}=p_{[u_{i}]}p_{[v]}$, for all vertices $u\sim v$. This
characterisation motivates the definition of the ideal of model invariants
studied in Section 4.

From now on, the edge labels will be considered as variables of a polynomial
ring $\mathbb{R}[\Theta]$. For a vertex $v\in V$ we denote by $\mathcal{T}(v)$
the induced subtree of $\mathcal{T}$ which is rooted at $v$ and whose root-to-
leaf paths are $v$-to-leaf paths in $\mathcal{T}$. To this subtree we
associate a polynomial $t(v)\in\mathbb{R}[\Theta]$ which is equal to the sum
of all products of labels along all $v$-to-leaf paths in $\mathcal{T}(v)$
[18]. This is a key object in our study of balanced staged trees. In
particular, we call a staged tree _balanced_ [8] if for any two vertices $u,v$
in the same stage the following is true:

$t(u_{i})t(v_{j})=t(u_{j})t(v_{i})\text{ for all pairs of children of }u\text{
and }v\text{ numbered }i,j=1,\ldots,k.$ ($\star$)

Figure 2 shows examples of balanced staged trees. This class is fairly large
as all decomposable directed graphical models can be represented by balanced
staged trees [8].

Before we can extend the study of balanced staged trees in Section 3, we need
to understand how this property of a tree affects the model it represents. To
this end, note that a staged tree model most often is not uniquely represented
by a single staged tree: there may be different parametrisations for the same
model, giving rise to different polynomial equations cutting out the same
subset of the probability simplex. The class of all staged trees representing
the same model is known as the _statistical equivalence class_. Members of
such a class are connected to each other by two simple graphical operations:
resizes and swaps [20]. For the purposes of this paper we present versions of
these in a constructive manner.

(a) A staged tree with a subgraph on which we perform operations.

(b) The staged tree after performing a resize.

(c) The resized staged tree after performing a swap.

Figure 2: Three balanced staged trees which are statistically equivalent using
a swap and a resize on the highlighted subtrees.

The _swap_ operation is illustrated in Figs. 2(b) and 2(c) where we swap a
two-level subtree. Let $\theta_{1},\ldots,\theta_{k}$ be the labels associated
to a stage of colour $c$. Suppose a vertex $v$ is not of the colour $c$, but
every term in the subtree polynomial $t(v)$ is divisible by one of the
${\theta_{1},\ldots,\theta_{k}}$. Then we can replace the subtree
$\mathcal{T}(v)$ by another tree with the same atomic probabilities but with a
root of colour $c$. This is because in this setting every root-to-leaf path in
$\mathcal{T}(v)$ goes through a vertex of colour $c$ and we can find a another
subtree $\mathcal{T}^{\prime}(v)\subseteq\mathcal{T}(v)$ with root $v$ and
leaves $v_{1},\ldots,v_{m}$ which have the colour $c$ in $\mathcal{T}$. Let
$\mathcal{T}_{v_{i}\theta_{j}}$ denote the induced subtree coming after the
edge labelled $\theta_{j}$ of the vertex $u_{i}$. We obtain a different
representation of $\mathcal{T}(v)$ like this. Start with a root of colour $c$
and to each edge glue a copy of $\mathcal{T}^{\prime}(v)$. Then to each leaf
glue the corresponding tree $\mathcal{T}_{v_{i}\theta_{j}}$. The map which
replaces the original tree by the tree obtained after performing this copying
and reglueing is called a swap.

The _resize_ operation is illustrated in Figs. 2(a) and 2(b) where we resize
two two-level subtrees. Suppose in a staged tree we have a vertex $u$ such
that for every vertex $v$ in the same stage, their children are also pairwise
in the same stages, $u_{i}\sim v_{i}$ for all $i=1,\ldots,k$. Then for each
such $u,v$ we remove their non-leaf children and draw edges from the vertices
directly to their respective grandchildren. This introduces a new set of
labels for the new edges related to the old ones as follows. Let $w$ be a
vertex in the new tree, and $w^{\prime}$ the corresponding vertex in the
original tree. Then if in $t(w)$ we substitute each new label by the product
of the two original that it replaced, we get $t(w^{\prime})$. For the resized
tree to represent the same model as the original tree we require in addition
that no $u_{i}$ and $u_{j}$ are in the same stage for $i\not=j$ and these
colours do not appear anywhere else in the tree. A resize not respecting these
extra conditions were called ‘naïve’ in the original presentation [20]. But
even in the ‘naïve’ cases where we do lose information and effectively create
a bigger statistical model, these operations are useful tools for the analysis
conducted in Section 5. In particular we have the following lemma.

######  Lemma 2.1.

The class of balanced staged trees is invariant under the swap and resize
operations.

###### Proof.

As for the swap, simply observe that this operation does not change the
parametrisation of a staged tree but only locally changes the order of
vertices in a subtree $\mathcal{T}(v)$. Hence, $t(v)$ is invariant under the
swap, not affecting validity of Eq. $\star$.

For the resize, let two vertices $u\sim v$ be in the same stage in the new
tree, after the resize operation has been applied. We want to prove that the
condition Eq. $\star$ is fulfilled, so that
$t(u_{i})t(v_{j})-t(u_{j})t(v_{i})=0$ for all children of $u$ and $v$, indexed
by $i,j=1,\ldots,k$. What we do know is that
$t(u_{i})t(v_{j})-t(u_{j})t(v_{i})$ is zero after we substitute a product of
labels $\theta_{k\ell}=\tau_{k}\sigma_{\ell}$ according to the resize
operation, since the original tree was balanced. In other words, this binomial
is an element of the ideal generated by
$\theta_{k\ell}-\tau_{k}\sigma_{\ell}$, namely

$t(u_{i})t(v_{j})-t(u_{j})t(v_{i})\in\langle\theta_{k\ell}-\tau_{k}\sigma_{\ell}\rangle_{k,\ell}\subset\mathbb{R}[\Theta]$
(2)

where $\Theta$ here denotes the set of labels from both the old tree and the
new. But no $\tau_{\cdot}$’s occur in the new tree, so we must have
$t(u_{i})t(v_{j})-t(u_{j})t(v_{i})=0$. This proves the claim. ∎

This result will provide the basis for proving 3.4.

###  2.2 Algebra of staged tree models

We henceforth treat the atomic probabilities $p_{1},\dots,p_{n}$ of a staged
tree $\mathcal{T}$ as variables spanning a polynomial ring denoted
$\mathbb{R}[p]$. We will use the short notation ${\langle\theta-1\rangle}$ for
the ideal of all local sum-to-one conditions $\langle\sum_{e\in
E(v)}\theta(e)-1\mid v\in V\text{ a non-leaf}\rangle$ in the polynomial ring
$\mathbb{R}[\Theta]$. We choose $\mathbb{R}$ as our base field in this paper
in the style of real algebraic geometry and algebraic statistics, though all
results hold for an arbitrary base field of characteristic zero. Associating
the variables of $\mathbb{R}[p]$ to the atomic probabilities induces a ring
map

$\varphi_{\mathcal{T}}:\mathbb{R}[p]\to\mathbb{R}[\Theta]/{\langle\theta-1\rangle},\quad
p_{r}\mapsto\prod_{e\in E(\lambda_{r})}\theta(e)\text{ for }r=1,\ldots,n.$ (3)

We will now use the notation $p_{[v]}$ for the sum of the variables $p_{r}$ in
the ring $\mathbb{R}[p]$ for which the corresponding root-to-leaf path
$\lambda_{r}$ passes through the vertex $v$. Due to the sum-to-one conditions,
the image $\varphi_{\mathcal{T}}(p_{[v]})$ of an atomic sum $p_{[v]}$ is equal
to the product of the labels along the corresponding root-to-$v$ path.

The kernel of $\varphi_{\mathcal{T}}$ is the _prime ideal of the staged tree_
$\mathcal{T}$. The variety of this ideal gives an implicit description to the
staged tree model $\mathcal{M}_{\mathcal{T}}$. In order to use classical
results of algebraic geometry more comfortably, we will mostly work with the
homogenised version of $\varphi_{\mathcal{T}}$,

${\varphi_{\mathcal{T}}}_{\text{hom}}:\mathbb{R}[p]\rightarrow\mathbb{R}[\Theta,z]/\langle\theta-z\rangle,\quad
p_{r}\mapsto z^{d-d(\lambda_{r})}\prod_{e\in E(\lambda_{r})}\theta(e)$ (4)

where, in analogy to the notation used in Eq. 3, $\langle\theta-z\rangle$
denotes the ideal of homogenised local sum-to-one conditions. Here $z$ is an
artificial parameter, $d(\lambda_{r})$ is the number of edges in the root-to-
leaf path $\lambda_{r}$, and $d$ is the number of edges in the longest root-
to-leaf path in the tree. The integer $d$ will often be regarded as the
_depth_ of the tree. Each of the variables $p_{r}$ are mapped to a monomial of
degree $d$ under ${\varphi_{\mathcal{T}}}_{\text{hom}}$.

######  Remark 2.2.

The homogenisation process is equivalent to completing the staged tree
$\mathcal{T}$ into a staged tree where all leaves are in the same distance $d$
from the root. This is achieved by adding when needed internal vertices of
outdegree one and label $z$: compare Fig. 4. Such changes do not affect the
model. Hence, we will in notation not distinguish between
$\varphi_{\mathcal{T}}$ and ${\varphi_{\mathcal{T}}}_{\text{hom}}$.

An element of significance to this paper is the image of
$\varphi_{\mathcal{T}}$ which is a subring of
$\mathbb{R}[\Theta,z]/\langle\theta-z\rangle$ denoted
$\mathrm{im}\,\varphi_{\mathcal{T}}$. We will also refer to
$\mathrm{im}\,\varphi_{\mathcal{T}}$ as an algebra, as it can be considered as
a vector space over $\mathbb{R}$ and a ring at the same time. One can compare
the algebras of two staged trees $\mathcal{T}^{\prime}\subseteq\mathcal{T}$
sharing the same root. The inclusion
$\mathcal{T}^{\prime}\subseteq\mathcal{T}$ here indicates that
$\mathcal{T}^{\prime}$ can be obtained by removing induced subtrees
$\mathcal{T}(v)$ for vertices $v$ in $\mathcal{T}$.

######  Lemma 2.3.

For any two staged trees $\mathcal{T}^{\prime}\subseteq\mathcal{T}$ that share
the same root one has
$\mathrm{im}\,\varphi_{\mathcal{T}^{\prime}}\subseteq\mathrm{im}\,\varphi_{\mathcal{T}}$.

###### Proof.

The image of $\varphi_{\mathcal{T}^{\prime}}$ is generated by the products of
labels of root-to-leaf paths in $\mathcal{T}^{\prime}$. Each of these paths is
a root-to-$v$ path in $\mathcal{T}$, for some vertex $v$. Hence the same
product lies in the image of $\varphi_{\mathcal{T}}$, as it is the image of
$p_{[v]}$. ∎

The central objective of this paper is to provide conditions under which the
ideal $\ker\varphi_{\mathcal{T}}$ is toric, possibly after a linear change of
variables. Recall thus that a prime ideal in $\mathbb{R}[p]$ is called toric
if it is generated by binomials, or equivalently is the kernel of a monomial
map $\varphi$ from $\mathbb{R}[p]$ to a Laurent ring $\mathbb{R}[y_{1}^{\pm
1},\ldots,y_{m}^{\pm 1}]$. That $\varphi$ is a monomial map means that each
variable $p_{r}$ is mapped to a monomial. The kernel of such a map is
generated by differences of monomials $p^{a}-p^{b}$ such that
$\varphi(p^{a})=\varphi(p^{b})$. The image of $\varphi$ is the subalgebra of
$\mathbb{R}[y_{1}^{\pm 1},\ldots,y_{m}^{\pm 1}]$ generated by the monomials
$\varphi(p_{1}),\ldots,\varphi(p_{n})$. We say that an algebra is a _monomial
algebra_ if it is generated by monomials in a Laurent ring or a polynomial
ring.

Even though the map Eq. 3 appears monomial, its target ring is a quotient ring
instead of a Laurent ring, and we cannot conclude that
$\ker\varphi_{\mathcal{T}}$ defines a toric variety; recall here the coin flip
example from the introduction. For staged tree models, the ideal
$\ker\varphi_{\mathcal{T}}$ is toric in the variables $p_{1},\ldots,p_{n}$ if
and only if the tree $\mathcal{T}$ is balanced.

######  Theorem 2.4.

[8, Theorem 10] The ideal $\ker\varphi_{\mathcal{T}}$ is a toric ideal if and
only if $\mathcal{T}$ is a balanced staged tree.

Hence, if a non-balanced tree has a toric structure, the structure must appear
only after a linear change of coordinates. This can be done either by
explicitly finding a linear change of variables which makes
$\ker\varphi_{\mathcal{T}}$ a binomial ideal, or to prove that
$\mathrm{im}\,\varphi_{\mathcal{T}}$ is a monomial algebra as we state below.

######  Proposition 2.5.

Suppose the algebra $\mathrm{im}\,\varphi_{\mathcal{T}}$ is isomorphic to a
monomial algebra. Then the ideal $\ker\varphi_{\mathcal{T}}$ is toric after an
appropriate linear change of coordinates.

###### Proof.

Let $\mathrm{im}\,\varphi_{\mathcal{T}}$ be isomorphic to an algebra minimally
generated by monomials $m_{1},\ldots,m_{r}$ in some polynomial ring via a map
$f$. Then we have a composition of maps

$\mathbb{R}[p]\overset{\varphi_{\mathcal{T}}}{\longrightarrow}\mathbb{R}[\Theta,z]/\langle\theta-z\rangle\overset{f}{\longrightarrow}\mathbb{R}[m_{1},\ldots,m_{r}]$
(5)

which is a surjective homomorphism. We claim that the linear span of
$f\circ\varphi_{\mathcal{T}}(\\{p_{1},\ldots,p_{n}\\})$ equals the linear span
of $m_{1},\ldots,m_{r}$. Every monomial $m_{i}$ is in the image of
$f\circ\varphi_{\mathcal{T}}$, and if it would not be the image of a linear
form this would contradict the fact that $m_{1},\ldots,m_{r}$ are minimal
generators. Then every $p_{i}$ must be mapped to a linear combination of
$m_{1},\ldots,m_{r}$, since otherwise we would get a non-homogeneous binomial
generator of $\ker\varphi_{\mathcal{T}}$. It follows that there are $n$
linearly independent linear forms $\ell_{1},\ldots,\ell_{n}$ in the union of
preimages $\bigcup_{i=1}^{k}\varphi_{\mathcal{T}}^{-1}\circ f^{-1}(m_{i})$.
The ideal $\ker\varphi_{\mathcal{T}}$ is binomial after the linear change of
variables given by $\ell_{1},\ldots,\ell_{n}$. ∎

######  Example 2.6.

Let $\mathcal{T}$ be the tree in Fig. 3, and let $\Theta^{4}$ denote the set
of monomials of degree four in the variables $\theta_{1}$, $\theta_{2}$. Then
$\mathrm{im}\,\varphi_{\mathcal{T}}$ is the subalgebra of
$\mathbb{R}[\theta_{1},\theta_{2},z]/\langle\theta_{1}+\theta_{2}-z\rangle$
generated by $\theta_{1}^{2}z^{2}$, $\theta_{1}\theta_{2}z^{2}$,
$\theta_{1}^{2}\theta_{2}z$, $\theta_{1}^{1}\theta_{2}^{2}$,
$\theta_{1}\theta_{2}^{3}$, and $\theta_{2}^{2}z^{2}$. All of the generators
can be expressed as linear combinations of the monomials in $\Theta^{4}$,
using the relation $z=\theta_{1}+\theta_{2}$. Conversely, one can verify that
the five monomials in $\Theta^{4}$ are the images of the linear forms
$\ell_{1}=p_{1}-2p_{3}+p_{4}$, $\ell_{2}=p_{3}-p_{4}$, $\ell_{3}=p_{4}$,
$\ell_{4}=p_{5}$, $\ell_{5}=p_{6}-2p_{5}-p_{4}$ under $\varphi_{\mathcal{T}}$.
For instance

$\varphi_{\mathcal{T}}(p_{1}-2p_{3}+p_{4})=\theta_{1}^{2}z^{2}-2\theta_{1}^{2}\theta_{2}z+\theta_{1}^{2}\theta_{2}^{2}=\theta_{1}^{4}+2\theta_{1}^{3}\theta_{2}+\theta_{1}^{2}\theta_{2}^{2}-2\theta_{1}^{3}\theta_{2}-2\theta_{1}^{2}\theta_{2}^{2}+\theta_{1}^{2}\theta_{2}^{2}=\theta_{1}^{4}.$
(6)

It follows that $\Theta^{4}$ is a different generating set for the algebra
$\mathrm{im}\,\varphi_{\mathcal{T}}$. As
$\mathbb{R}[\Theta^{4}]\cap\langle\theta_{1}+\theta_{2}-z\rangle=\\{0\\}$, the
image of $\varphi_{\mathcal{T}}$ is isomorphic to the monomial algebra
$\mathbb{R}[\Theta^{4}]$. To get the change of variables which makes
$\ker\varphi_{\mathcal{T}}$ toric we choose another linear form $\ell_{6}$,
not in the span of $\ell_{1},\ldots,\ell_{5}$, which maps to a monomial of
$\Theta^{4}$. For example we may take $\ell_{6}=p_{2}-p_{3}-p_{5}$, as this
maps to $\theta_{1}^{2}\theta_{2}^{2}$. The ideal $\ker\varphi_{\mathcal{T}}$
is then the kernel of the monomial map
$\mathbb{R}[\ell_{1},\ldots,\ell_{6}]\to\mathbb{R}[\Theta^{4}]$.

Figure 3: A staged tree with edge labels $\theta_{1}$ and $\theta_{2}$ that
has toric structure.

A first application of 2.5 is that if two distinct trees share the same
algebra then they must both be toric or non-toric. The same is true if the two
algebras change by a permutation or when the parameters of a staged tree are
permutations of parameters of another other staged tree.

######  Corollary 2.7.

If for staged trees $\mathcal{T}$ and $\mathcal{T}^{\prime}$ the algebras
$\mathrm{im}\,\varphi_{\mathcal{T}}$ and
$\mathrm{im}\,\varphi_{\mathcal{T}^{\prime}}$ are equal or they change only by
a permutation of variables, the staged tree models $\mathcal{T}$ and
$\mathcal{T}^{\prime}$ are simultaneously toric or non-toric.

##  3 Balanced staged tree models

As stated in Theorem 2.4 the ideal $\ker\varphi_{\mathcal{T}}$ is toric when
the tree $\mathcal{T}$ is balanced. The monomial map defining this toric ideal
is precisely the map (4) with the quotient ring
$\mathbb{R}[\Theta,z]/\langle\theta-z\rangle$ replaced by the polynomial ring
$\mathbb{R}[\Theta,z]$. In this section we continue the study of balanced
staged trees and their prime ideals.

###  3.1 The combinatorial structure of balanced trees

Our main result on the combinatorial structure of balanced trees is 3.1, which
states that a balanced staged tree model always can be represented by a tree
with a certain colour structure. To obtain this colour structure we apply the
homogenisation process already in the tree, as described in Remark 2.2. We
also allow the out-degree one vertices to appear anywhere in the tree, not
just as extensions in the end of a branch. See Fig. 4 for an example.

Figure 4: Colour structure in a balanced tree.

######  Theorem 3.1.

To any balanced staged tree we can apply the swap operation so that for every
pair of vertices $u$ and $v$ in the same stage, one of the following holds.

  1. 1.

For each index $i$ the two children $u_{i}$ and $v_{i}$ are in the same stage.

  2. 2.

The children of $u$ are all in the same stage. The same holds for $v$.

In order to prove Theorem 3.1 we need some preparations. We define the
_multiplicity_ of a colour $c$ at a vertex $v$, denoted
$\operatorname{mult}_{c}(v)$, to be the greatest number $m$ for which every
$v$-to-leaf path goes through at least $m$ vertices of the colour $c$. If
$\theta_{1},\ldots,\theta_{k}$ are the labels associated to the colour $c$ we
can also say that $\operatorname{mult}_{c}(v)$ is the greatest number $m$ for
which every term in $t(v)$ is divisible by a monomial in
$\theta_{1},\ldots,\theta_{k}$ of degree $m$. If
$\operatorname{mult}_{c}(v)>0$ we can use the swap operation to give the
induced subtree $\mathcal{T}(v)$ a root of colour $c$. Notice also that
applying the swap operation to $\mathcal{T}(v)$, or to an induced subtree
inside $\mathcal{T}(v)$, does not change the multiplicities.

######  Lemma 3.2.

Let $u$ and $v$ be vertices of the same stage in a balanced staged tree, and
assume $\operatorname{mult}_{c}(u_{i})>\operatorname{mult}_{c}(u_{j})$ for
some colour $c$ and some indices $i,j$. Then
$\operatorname{mult}_{c}(v_{i})>\operatorname{mult}_{c}(v_{j})$.

###### Proof.

The equality $t(u_{i})t(v_{j})=t(u_{j})t(v_{i})$ implies
$\operatorname{mult}_{c}(u_{i})+\operatorname{mult}_{c}(v_{j})=\operatorname{mult}_{c}(u_{j})+\operatorname{mult}_{c}(v_{i})$.
If $\operatorname{mult}_{c}(u_{i})>\operatorname{mult}_{c}(u_{j})$ then we
must have $\operatorname{mult}_{c}(v_{i})>\operatorname{mult}_{c}(v_{j})$ for
the above equality to hold. ∎

###### Proof of Theorem 3.1.

In this proof vertices $v$ such that

$\mbox{for each}\ i\ \mbox{there is a colour}\ c_{i}\ \mbox{and a}\ j\
\mbox{such that}\
\operatorname{mult}_{c_{i}}(v_{i})>\operatorname{mult}_{c_{i}}(v_{j})$ (7)

will play an important role. If $v$ has the property (7) then we can give each
$v_{i}$ the colour $c_{i}$, using the swap operation on $\mathcal{T}(v_{i})$.
If $v$ does not have the property (7), then either all its children are
leaves, or we can use the swap operation on the $\mathcal{T}(v_{i})$’s to give
all children of $v$ the same colour. It follows from Lemma 3.2 that if $u\sim
v$ then $u$ satisfies (7) if and only if $v$ does with the same colours.

We prove the theorem by providing an algorithm which will give the desired
colour structure, assuming the tree is balanced. The algorithm goes through
the internal vertices of out-degree greater than one whose children are not
leaves. We visit the vertices in weakly increasing order, according to the
distance from the root, and do the following.

  * •

If $v$ has a colour we have not seen before, we check if $v$ satisfies (7). If
it does, we give each $v_{i}$ the colour $c_{i}$, by using the swap operation.
If not, we give all $v_{i}$’s the same colour.

  * •

If $v$ has a colour that we have seen before, we look at the children of the
previous vertex $u$ of that colour. If the children of $u$ does not all have
the same colour, it means the $u$ has the property (7). Then so does $v$, and
we can give each $v_{i}$ the same colour as $u_{i}$. If all the children of
$u$ have the same colour, it means that $u$ did not satisfy (7). Then neither
does $v$, and we give all children of $v$ the same colour.

Notice that these steps do not change the colour of any vertex we have already
visited, or their children. Therefore, condition 1 or 2 in Theorem 3.1 will
hold for all vertices $u$ and $v$ in the same stage of out-degree greater than
one. For the vertices of out-degree one condition 2 always holds, so we are
done. ∎

In squarefree staged trees, the root-to-leaf path $\lambda_{r}$ can be read
off uniquely from the monomial $\varphi_{\mathcal{T}}(p_{r})$. In other words,
the ideal $\ker\varphi_{\mathcal{T}}$ will not contain any relations of degree
one. Next, we will study the structure of balanced trees which are _not_
squarefree. We use the notation $v_{ij}$ for the grandchildren of $v$, meaning
that $v_{ij}$ is the $j$-th child of $v_{i}$.

######  Lemma 3.3.

In a balanced tree, suppose we have a vertex $v$ which is in the same stage as
all of its children. Then $t(v_{ij})=t(v_{ji})$.

###### Proof.

Since $v\sim v_{i}$ we have $t(v_{i})t(v_{ij})=t(v_{j})t(v_{ii})$ which can
also be written as

$(\theta_{1}t(v_{i1})+\theta_{2}t(v_{i2})+\dots+\theta_{k}t(v_{ik}))t(v_{ij})=(\theta_{1}t(v_{j1})+\theta_{2}t(v_{j2})+\dots+\theta_{k}t(v_{jk}))t(v_{ii}).$
(8)

As $v_{i}\sim v_{j}$ we also have $t(v_{ii})t(v_{jm})=t(v_{im})t(v_{ji})$.
Applying this to the right hand side of (8) we get

$(\theta_{1}t(v_{i1})+\theta_{2}t(v_{i2})+\dots+\theta_{k}t(v_{ik}))t(v_{ij})=(\theta_{1}t(v_{i1})+\theta_{2}t(v_{i2})+\dots+\theta_{k}t(v_{ik}))t(v_{ji})$
(9)

and it follows that $t(v_{ij})=t(v_{ji})$. ∎

######  Proposition 3.4.

Let $u$ and $v$ be vertices of the same stage in a balanced staged tree.
Suppose there is a path $\lambda_{r}$ that goes through both $u$ and $v_{j}$,
for some $j$, where $u$ comes first. Then there is a path $\lambda_{s}$ going
through $u_{j}$ such that
$\varphi_{\mathcal{T}}(p_{r})=\varphi_{\mathcal{T}}(p_{s})$.

###### Proof.

It is enough to consider the case when $u$ is the root, as we can restrict to
the subtree $\mathcal{T}(u)$. As a first step we apply the algorithm in the
proof of Theorem 3.1. This does not change the colour of the root, but it
might of course change the appearance of the rest of the tree. However, if we
prove the statement for all $v\sim u$ in the new tree it will hold for all
$v\sim u$ in the old tree as both trees represent the same model in the same
parametrisation.

The proof is by induction over the depth of the tree. The smallest depth where
we can have two vertices in the same stage in the same path is two. One can
easily check that for such a tree to be balanced we need all internal vertices
to be in the same stage. In this case we have
$\varphi_{\mathcal{T}}(p_{r})=\theta_{i}\theta_{j}$ and
$\varphi_{\mathcal{T}}(p_{s})=\theta_{j}\theta_{i}$.

For the induction step we consider three cases.

  1. 1.

The children of $u$ do not all have the same colour. In this case we have
$u_{i}\sim v_{i}$ for all vertices $v$ that are in the same stage as $u$. Then
we use the resize operation on all the vertices in the same stage as $u$. The
new tree is also balanced by Lemma 2.1. As the depth has decreased, it follows
by induction that the statement is true for this tree. We can easily redo the
resize to find the path $\lambda_{s}$ in the original tree.

  2. 2.

The children of $u$ all have the same colour, but not the same colour as $u$
itself. This case is also illustrated in Fig. 5. Here we use the swap
operation on $u$ and its children. This results in a new tree with a root
followed by a number of induced subtrees whose roots are in the same colour as
$u$ in the original tree. By induction there is a path $\lambda_{s}$ in the
same subtree as $\lambda_{r}$, with the desired properties. We can find this
path $\lambda_{s}$ in the original tree by swapping the root and its children
one more time.

  3. 3.

The children of $u$ have the same colour as $u$. If we consider $v$ to be one
on the children of $u$, the result follows from Lemma 3.3. Otherwise we can
swap $u$ and its children and continue as in case 2. ∎

(a) Before the swap.

(b) After the swap.

Figure 5: Illustration of case 2 in the proof of Proposition 3.4. By applying
the swap operation we find the $p_{s}$ such that
$\varphi_{\mathcal{T}}(p_{2})=\varphi_{\mathcal{T}}(p_{s})$ inside a smaller
induced subtree. Here $s=5$.

###  3.2 The toric ideal associated to a balanced tree

We now turn to the problem of finding a generating set for the toric ideal
$\ker\varphi_{\mathcal{T}}$, when $\mathcal{T}$ is balanced. We start with a
quick review of the concept of _Gröbner bases_ for ideals in polynomials
rings. For more details we refer the reader to [12]. Every Gröbner basis
relies on a monomial order $\succ$. Here we will use the _Degree Reverse
Lexicographic_ monomial order (DegRevLex). Assume the variables
$p_{1},\ldots,p_{n}$ are numbered from top to bottom in the tree, with $p_{1}$
in the top. We order the variables by $p_{1}\succ p_{2}\succ\dots\succ p_{n}$.
More generally, the monomials are ordered by $p_{1}^{\alpha_{1}}\cdots
p_{n}^{\alpha_{n}}\succ p_{1}^{\beta_{1}}\cdots p_{n}^{\beta_{n}}$ in
DegRevLex if $\alpha_{1}+\dots+\alpha_{n}\succ\beta_{1}+\dots+\beta_{n}$ or
$\alpha_{1}+\dots+\alpha_{n}=\beta_{1}+\dots+\beta_{n}$ and there is an $i$
for which $\alpha_{i}<\beta_{i}$ and $\alpha_{j}=\beta_{j}$ for all $j>i$.
Every polynomial $f$ is a linear combination of monomials, and the greatest
monomial according to the given order provides the _leading term_ of $f$. Now,
let $I$ be an ideal in a polynomial ring, and let $G$ be a set of polynomials
in $I$. The set $G$ is a Gröbner basis for $I$ if the leading term of any
polynomial in $I$ is divisible by the leading term of a polynomial in $G$. A
fundamental fact is that a Gröbner basis for an ideal $I$ is a generating set
for $I$.

It was conjectured by Duarte and Görgen that the toric ideal of a balanced
staged tree have a Gröbner basis of binomials of degree two, [8, Conjecture
17]. The conjecture was proved by Ananiadi and Duarte [1] in the case of
stratified staged trees with all leaves on the same distance from the root. We
shall now prove the conjecture in full generality, with the modification that
degree one generators are needed in the non-squarefree case. An example of a
balanced staged tree which is not squarefree, and hence not stratified, can be
found in Figure 5.

Let $\mathcal{T}$ be a balanced staged tree. Suppose $u$ and $v$ are vertices
in the same stage in $\mathcal{T}$ and let $\theta_{1},\ldots,\theta_{k}$ be
the labels of this stage. Let $m_{u}$ be the product of the labels along the
path from the root to $u$, and similarly for $m_{v}$. If we multiply ($\star$
‣ 2.1) by $m_{u}m_{v}\theta_{i}\theta_{j}$ we get

$(m_{u}\theta_{i}t(u_{i}))(m_{v}\theta_{j}t(v_{j}))=(m_{u}\theta_{j}t(u_{j}))(m_{v}\theta_{i}t(v_{i})).$
(10)

Notice that the terms in each of the factors correspond to a root-to-leaf
path. As every term has coefficient 1, there is no cancellation. Hence the
above equality gives rise to a number of binomials
$p_{r_{1}}p_{r_{2}}-p_{s_{1}}p_{s_{2}}$ in $\ker\varphi_{\mathcal{T}}$, where
the path $\lambda_{r_{1}}$ goes through $u_{i}$, the path $\lambda_{r_{2}}$
through $v_{j}$, the path $\lambda_{s_{1}}$ through $u_{j}$, and
$\lambda_{s_{2}}$ through $v_{i}$. Let $G$ be the set of all such binomials,
together with all binomials of degree one in $\ker\varphi_{\mathcal{T}}$. The
set $G$ for the tree in Fig. 5(a) is given in Example 3.7. We shall see that
$G$ is a Gröbner basis for $\ker\varphi_{\mathcal{T}}$.

######  Theorem 3.5.

For a balanced staged tree the set $G$ of binomials of degree one and two
defined above is a Gröbner basis for the ideal $\ker\varphi_{\mathcal{T}}$ w.
r. t. DegRevLex.

###### Proof.

We know that $\ker\varphi_{\mathcal{T}}$ is generated by homogeneous
binomials. It follows from Buchberger’s algorithm [12] that every binomial
ideal has a Gröbner basis of binomials. Hence we are done if we can prove that
the leading term of a binomial in $\ker\varphi_{\mathcal{T}}$ is divisible by
the leading term of a binomial of in $G$. Let $f=p_{r_{1}}\dots
p_{r_{d}}-p_{s_{1}}\cdots p_{s_{d}}\in\ker\varphi_{\mathcal{T}}$ where
$p_{r_{1}}\cdots p_{r_{d}}$ is the leading term. We assume that
$p_{r_{1}}\succ\dots\succ p_{r_{d}}$ and $p_{s_{1}}\succ\dots\succ p_{s_{d}}$.
We may also assume that $f$ is not divisible by a monomial. This implies that
$p_{r_{d}}\succ p_{s_{d}}$.

Let $u$ be the vertex where the two paths $\lambda_{r_{d}}$ and
$\lambda_{s_{d}}$ split. Say $\lambda_{r_{d}}$ then follows an edge labelled
$\theta_{i}$, and $\lambda_{s_{d}}$ an edge labelled $\theta_{j}$. As
$p_{r_{d}}\succ p_{s_{d}}$ we have $i<j$. Let $m$ be the product of the labels
along the path from the root to $u$. Then

$\varphi_{\mathcal{T}}(p_{r_{1}})\cdots\varphi_{\mathcal{T}}(p_{r_{d-1}})\frac{\varphi_{\mathcal{T}}(p_{r_{d}})}{m}=\varphi_{\mathcal{T}}(p_{s_{1}})\cdots\varphi_{\mathcal{T}}(p_{s_{d-1}})\frac{\varphi_{\mathcal{T}}(p_{s_{d}})}{m}$
(11)

and since the monomial $\varphi_{\mathcal{T}}(p_{s_{d}})/m$ is divisible by
$\theta_{j}$, one of the factors in the left hand side must be divisible by
$\theta_{j}$ as well. Notice that none of
$\lambda_{r_{1}},\ldots,\lambda_{r_{d}}$ goes through $u_{j}$, as
$p_{r_{1}}\succ\dots\succ p_{r_{d}}$ and $\lambda_{r_{d}}$ takes the $i$-th
edge at $u$. Then we have the following cases.

  1. 1.

Some $\lambda_{r_{t}}$ goes through $u$ and an edge labelled $\theta_{j}$, and
the $\theta_{j}$-edge appears after $u$. Then by Proposition 3.4 there is a
$\lambda_{r^{\prime}_{t}}$ that takes the $j$-th edge at $u$ and
$p_{r_{t}}-p_{r^{\prime}_{t}}\in G$. As $i<j$ we have $p_{r_{t}}\succeq
p_{r_{d}}\succ p_{r^{\prime}_{t}}$, and $p_{r_{t}}$ is the leading term of
$p_{r_{t}}-p_{r^{\prime}_{t}}$.

  2. 2.

Some $\lambda_{r_{t}}$, with $t<d$, goes through $u$ and an edge labelled
$\theta_{j}$, and the $\theta_{j}$-edge appears before $u$.
The $\theta_{j}$-edge is an outgoing edge of some vertex $v$ in the same stage
as $u$. As $v$ and $v_{j}$ lie on the path leading to $u$, the path
$\lambda_{s_{d}}$ must also go through $v_{j}$. At $u$ the path
$\lambda_{r_{t}}$ takes the $l$-th edge for some $l<j$. Then we have
$p_{r_{t}}p_{r_{d}}-p_{r^{\prime}_{d}}p_{r^{\prime}_{t}}\in G$ such that
$p_{r^{\prime}_{t}}$ takes the $j$-th edge at $u$, and $p_{r^{\prime}_{d}}$
takes the $l$-th edge at $v$. Then $p_{r^{\prime}_{d}}\succ
p_{r^{\prime}_{t}}$ and $p_{r_{s}}\succ p_{r^{\prime}_{t}}$, which makes
$p_{r_{t}}p_{r_{d}}$ the leading term.

  3. 3.

Some $\lambda_{r_{t}}$, with $t<d$, goes through an edge labelled $\theta_{j}$
and does not go through $u$. So there is a vertex $v$ in the same stage as
$u$, and they are on different branches. Since $p_{r_{t}}\succ p_{r_{d}}$ the
vertex $v$ must sit above $u$ in the tree. We have
$p_{r_{t}}p_{r_{d}}-p_{r^{\prime}_{t}}p_{r^{\prime}_{d}}\in G$ such that
$\lambda_{r^{\prime}_{d}}$ takes the $j$-th edge at $u$ and
$\lambda_{r^{\prime}_{t}}$ takes the $i$-th edge at $v$. Then
$p_{r^{\prime}_{t}}\succ p_{r^{\prime}_{d}}$ and $p_{r_{d}}\succ
p_{r^{\prime}_{d}}$, which makes $p_{r_{t}}p_{r_{d}}$ the leading term.

In all three cases we have found an element in $G$ with a leading term which
divides the leading term of $f$. ∎

Sometimes it can be useful to identify variables that are mapped to the same
monomial under $\varphi_{\mathcal{T}}$, and in this way get rid of the degree
one relations. For this purpose, let $\mathbb{R}[\bar{p}]$ be the polynomial
ring on the subset of the variables $p_{1},\ldots,p_{n}$ obtained by removing
$p_{r}$ if there is a $s>r$ such that
$\varphi_{\mathcal{T}}(p_{r})=\varphi_{\mathcal{T}}(p_{s})$. Let
$\bar{\varphi}_{\mathcal{T}}$ be the map $\varphi_{\mathcal{T}}$ restricted to
$\mathbb{R}[\bar{p}]$. The two maps have identical images.

######  Theorem 3.6.

For a balanced staged tree, the degree two binomials of
$\ker\bar{\varphi}_{\mathcal{T}}$ are a Gröbner basis for
$\ker\bar{\varphi}_{\mathcal{T}}$ w. r. t. DegRevLex.

###### Proof.

Let $f=p_{r_{1}}\\!\cdots p_{r_{d}}-p_{s_{1}}\\!\cdots
p_{s_{d}}\in\ker\bar{\varphi}$, where $p_{r_{1}}\\!\cdots p_{r_{d}}$ is the
leading term. As we also have $f\in\ker\varphi_{\mathcal{T}}$ the leading term
of $f$ is divisible by the leading term of a binomial
$g\in\ker\varphi_{\mathcal{T}}$ of degree one or two, by Theorem 3.5. However,
the leading terms of the degree one binomials in $\ker\varphi_{\mathcal{T}}$
are precisely the variables we removed in the construction of
$\mathbb{R}[\bar{p}]$. Hence $g$ must be of degree two. The leading term of
$g$ is monomial in (one or two of) the variables
$p_{r_{1}},\ldots,p_{r_{d}}\in\mathbb{R}[\bar{p}]$. If the non-leading term of
$g$ is divisible by some $p_{i}$ for which there is a $j>i$ such that
$\varphi_{\mathcal{T}}(p_{i})=\varphi_{\mathcal{T}}(p_{j})$, we substitute
$p_{i}$ by $p_{j}$ in $g$. This produces a binomial
$\bar{g}\in\ker\bar{\varphi}_{\mathcal{T}}$ and does not change the leading
term. Hence $p_{r_{1}}\\!\cdots p_{r_{d}}$ is divisible by the leading term of
the degree two binomial $\bar{g}\in\ker\bar{\varphi}_{\mathcal{T}}$. ∎

######  Example 3.7.

Consider the tree in Fig. 5(a). The Gröbner basis of degree one and two
binomials of $\ker\varphi_{\mathcal{T}}$ from Theorem 3.5 is

$\displaystyle p_{2}-p_{5},\ p_{4}-p_{7},\ p_{2}p_{3}-p_{1}p_{4},\
p_{2}p_{5}-p_{1}p_{6},\ p_{2}p_{7}-p_{1}p_{8},\ p_{4}p_{5}-p_{3}p_{6},\
p_{4}p_{7}-p_{3}p_{8},\ p_{6}p_{7}-p_{5}p_{8},$ (12) $\displaystyle
p_{2}^{2}-p_{1}p_{6},\ p_{2}p_{3}-p_{1}p_{7},\ p_{2}p_{4}-p_{1}p_{8},\
p_{1}p_{4}-p_{3}p_{5},\ p_{2}p_{4}-p_{3}p_{6},\ p_{4}^{2}-p_{3}p_{8},\
p_{5}^{2}-p_{1}p_{6},\ p_{3}p_{6}-p_{5}p_{7},$ (13) $\displaystyle
p_{4}p_{6}-p_{5}p_{8},\ p_{5}p_{7}-p_{1}p_{8},\ p_{6}p_{7}-p_{2}p_{8},\
p_{7}^{2}-p_{3}p_{8},\ p_{3}p_{5}-p_{1}p_{7},\ p_{3}p_{6}-p_{1}p_{8},\
p_{4}p_{5}-p_{2}p_{7},\ p_{4}p_{6}-p_{2}p_{8}.$ (14)

The Gröbner basis for
$\ker\bar{\varphi}_{\mathcal{T}}\subset\mathbb{R}[p_{1},p_{3},p_{5},p_{6},p_{7},p_{8}]$
in Theorem 3.6 is

$p_{6}p_{7}-p_{5}p_{8},\ p_{5}^{2}-p_{1}p_{6},\ p_{3}p_{6}-p_{5}p_{7},\
p_{5}p_{7}-p_{1}p_{8},\ p_{7}^{2}-p_{3}p_{8},\ p_{3}p_{5}-p_{1}p_{7},\
p_{3}p_{6}-p_{1}p_{8}.$ (15)

###  3.3 The monomial algebra associated to a balanced tree

For a balanced tree $\mathcal{T}$ let $A_{\mathcal{T}}$ denote the subalgebra
of $\mathbb{R}[\Theta,z]$ generated by the monomials corresponding to the
root-to-leaf paths. As this set of monomials is exactly the parametrisation
for the toric ideal $\ker\varphi_{\mathcal{T}}$ we have
$A_{\mathcal{T}}\cong\mathbb{R}[p]/\ker\varphi_{\mathcal{T}}$. In this section
we will discuss some properties of $A_{\mathcal{T}}$ that are central in
commutative algebra. In particular we shall see that $A_{\mathcal{T}}$ is
_Koszul_ , _normal_ , and _Cohen-Macaulay_. We will briefly recall the
definitions of these properties. For a more extensive review we refer the
reader to [12].

A $K$-algebra $A$ is _Koszul_ if the field $K$ has a linear free resolution
over $A$. We recall two fundamental results about Koszul algebras. Suppose
$A=K[x_{1},\ldots,x_{n}]/I$. If $A$ is Koszul then $I$ is generated in degree
two. Moreover, if $I$ has a Gröbner basis consisting of polynomials of degree
two then $A$ is Koszul [2]. These give us an immediate corollary of Theorem
3.6.

######  Corollary 3.8.

For a balanced staged tree $\mathcal{T}$, the associated monomial algebra
$A_{\mathcal{T}}$ is Koszul.

An algebra generated by monomials, such as $A_{\mathcal{T}}$, can be
considered a semigroup ring. The semigroup is the set of monomials in the
ring, with multiplication as the semigroup operation. A semigroup $M$ is
called _normal_ if it is finitely generated and has the following property. If
there are $a,b,c\in M$ such that $ab^{N}=c^{N}$ for some positive integer $N$
then there is a $d\in M$ such that $a=d^{N}$. The ring $A_{\mathcal{T}}$ is a
Noetherian domain, meaning that it is a normal ring if it is integrally closed
in its field of fractions. Moreover, recall that a ring $R$ is _Cohen-
Macaulay_ if $\dim(R)=\operatorname{depth}(R)$, where in general
$\dim(R)\geq\operatorname{depth}(R)$. We summarise two important results on
normal semigroup rings.

######  Theorem 3.9.

[23, Proposition 1, Theorem 1] Let $M$ be a semigroup of monomials, and let
$K[M]$ denote the semigroup ring over a field $K$. Then $K[M]$ is normal if
and only if $M$ is normal. Moreover, if $K[M]$ is normal, then it is Cohen-
Macaulay.

Let $\mathcal{T}$ be a balanced staged tree, and let $M$ be the semigroup
generated by the monomials $\varphi_{\mathcal{T}}(p_{r})$, $r=1,\ldots,n$,
considered as monomials in $\mathbb{R}[\Theta,z]$. We shall prove that $M$ is
normal, and hence $A_{\mathcal{T}}$ is normal.

So, suppose we have a monomial $m\in M$ and two monomials
$\varphi_{\mathcal{T}}(p_{r_{1}})\cdots\varphi_{\mathcal{T}}(p_{r_{d}})$ and
$\varphi_{\mathcal{T}}(p_{s_{1}})\cdots\varphi_{\mathcal{T}}(p_{s_{e}})$ such
that
$m(\varphi_{\mathcal{T}}(p_{r_{1}})\cdots\varphi_{\mathcal{T}}(p_{r_{d}}))^{N}=(\varphi_{\mathcal{T}}(p_{s_{1}})\cdots\varphi_{\mathcal{T}}(p_{s_{e}}))^{N}$
for some positive integer $N$. Assume we have indexed
$p_{s_{1}},\ldots,p_{s_{e}}$ so that the path $\lambda_{s_{1}}$ agrees with
$\lambda_{r_{1}}$ in as many steps as possible. Suppose they separate in a
vertex $u$, where $\lambda_{r_{1}}$ takes the edge labelled $\theta_{i}$ and
$\lambda_{s_{1}}$ the edge labelled $\theta_{j}$. Then there must be a
matching $\theta_{j}$ in
$\varphi_{\mathcal{T}}(p_{s_{1}})\cdots\varphi_{\mathcal{T}}(p_{s_{e}})$. Here
we can follow the same steps as in the proof of Theorem 3.5 and get that there
is $p_{s^{\prime}_{1}}$ and $p_{s^{\prime}_{t}}$ such that
$\varphi_{\mathcal{T}}(p_{s^{\prime}_{1}})\varphi_{\mathcal{T}}(p_{s^{\prime}_{t}})=\varphi_{\mathcal{T}}(p_{s_{1}})\varphi_{\mathcal{T}}(p_{s_{t}})$,
for some $t$, and $\lambda_{s^{\prime}_{1}}$ agrees with $\lambda_{r_{1}}$ in
one more step. If $p_{s^{\prime}_{1}}\neq p_{r_{1}}$ we repeat this argument.
Let $p_{s^{\prime}_{1}},\ldots,p_{s^{\prime}_{e}}$ be the variables we end up
with after repeating the process enough times to get
$p_{s^{\prime}_{1}}=p_{r_{1}}$. Now we have

$m\varphi_{\mathcal{T}}(p_{r_{1}})^{N}(\varphi_{\mathcal{T}}(p_{r_{2}})\cdots\varphi_{\mathcal{T}}(p_{r_{d}}))^{N}=\varphi_{\mathcal{T}}(p_{r_{1}})^{N}(\varphi(p_{s^{\prime}_{2}})\cdots\varphi_{\mathcal{T}}(p_{s^{\prime}_{e}}))^{N}$
(16)

which implies

$m(\varphi_{\mathcal{T}}(p_{r_{2}})\cdots\varphi_{\mathcal{T}}(p_{r_{d}}))^{N}=(\varphi(p_{s^{\prime}_{2}})\cdots\varphi_{\mathcal{T}}(p_{s^{\prime}_{e}}))^{N}.$
(17)

We can continue this process until we have cancelled all factors except $m$ in
the left hand side. Then $m$ is indeed the $N$-th power of an element in $M$.
To summarise we have proved the following theorem.

######  Theorem 3.10.

For a balanced staged tree $\mathcal{T}$, the associated monomial algebra
$A_{\mathcal{T}}$ is normal and Cohen-Macaulay.

For a non-balanced tree the algebra $\mathbb{R}[p]/\ker\varphi_{\mathcal{T}}$
need not to be Koszul, normal, or Cohen-Macaulay.

Figure 6: A staged tree for which $A_{\mathcal{T}}$ is not Koszul, normal, or
Cohen-Macaulay.

######  Example 3.11.

The tree in Fig. 6 is not balanced, but the ideal $\ker\varphi_{\mathcal{T}}$
is toric after a linear change of variables. We will return to this fact in
Example 5.7. A computation in Macaulay2 [21] shows that the algebra is neither
normal nor Cohen-Macaulay. A minimal generating set for
$\ker\varphi_{\mathcal{T}}$ needs binomials of degree two and four, so the
quotient ring is not Koszul. This also provides a counter-example to [8,
Conjecture 16] on the generating set of the prime ideal of a staged tree, as
the given generators all are of degree two.

##  4 Ideal of minors for a staged tree model

Associated to a staged tree is its _ideal of model invariants_ [8]. For
$u_{1},\ldots,u_{k}$ denoting the children of an internal vertex $u$ in a
stage of colour $c$, we define

$I_{c}=\langle p_{[u_{i}]}p_{[v]}-p_{[u]}p_{[v_{i}]}\mid\text{ for all
vertices }u,v\text{ in stage }c,\ i=1,\ldots,k\rangle.$ (18)

The ideal of model invariants is the ideal $I_{\mathcal{T}}=\sum_{c}I_{c}$.
This ideal is contained in $\ker\varphi_{\mathcal{T}}$ and is easier to study
than the staged tree’s prime ideal because it has a concrete generating set.
It is related to the model we are interested in by the following result.

######  Theorem 4.1.

[8, Theorem 3, Corollary 8] The staged tree model $\mathcal{M}_{\mathcal{T}}$
is equal to the variety of $I_{\mathcal{T}}$ intersected with the probability
simplex $\Delta^{\circ}_{n-1}$. Moreover, $\ker\varphi_{\mathcal{T}}$ is a
minimal prime for $I_{\mathcal{T}}$.

In order to discover whether a staged tree model has toric structure, we now
search for binomial ideals between the ideal of model invariants
$I_{\mathcal{T}}$ and $\ker\varphi_{\mathcal{T}}$. The following is a key
result in this endeavour, searching for linear transformations of variables
that provide binomial generators.

######  Theorem 4.2.

Let $J$ be an ideal in $\mathbb{R}[p]$ such that $I_{\mathcal{T}}\subseteq
J\subseteq\ker\varphi_{\mathcal{T}}$. Let $\ell_{1},\dots,\ell_{n}$ be linear
forms in $\mathbb{R}[p]$ such that

  1. i.

$\ell_{1},\dots,\ell_{n}$ are linearly independent,

  2. ii.

each $\varphi_{\mathcal{T}}(\ell_{i})$ can be represented by a monomial in
$\mathbb{R}[\Theta,z]/\langle\theta-z\rangle$, and

  3. iii.

the ideal $J$ is generated by binomials in the new variables
$\ell_{1},\dots,\ell_{n}$.

Then $\ker\varphi_{\mathcal{T}}$ is a toric ideal in the new variables
$\ell_{1},\dots,\ell_{n}$.

###### Proof.

For each $i=1,\ldots,n$ let $m_{i}$ be a monomial in $\mathbb{R}[\Theta,z]$
such that $\varphi(\ell_{i})$ can be represented by $m_{i}$ in
$\mathbb{R}[\Theta,z]/\langle\theta-z\rangle$. We define the monomial map
$\psi:\mathbb{R}[p]\to\mathbb{R}[\Theta,z]$ by $\psi(\ell_{i})=m_{i}$. Then
clearly $\ker\psi\subseteq\ker\varphi$, and we shall prove that
$J\subseteq\ker\psi$. Take the binomial
$\ell_{i_{1}}\\!\cdots\ell_{i_{s}}-a\ell_{j_{1}}\\!\cdots\ell_{j_{s}}$ in $J$.
As $J\subseteq\ker\varphi$ the binomial $f=m_{i_{1}}\cdots
m_{i_{s}}-am_{j_{1}}\cdots m_{j_{s}}$ is in $\langle\theta-z\rangle$. We want
to prove that $f$ is in fact the zero polynomial. Let
$g=f/\gcd(m_{i_{1}}\cdots m_{i_{s}},m_{j_{1}}\cdots m_{j_{s}})$. Since
$\langle\theta-z\rangle$ is generated by linear forms it is a prime ideal, and
it does not contain any monomials. It follows that $g$ is in
$\langle\theta-z\rangle$. It remains to prove that $g=0$. If $g$ is not the
zero polynomial, then one of its terms is divisible by a factor, say
$\theta_{1}$. We can find a point in the variety of $\langle\theta-z\rangle$
where $\theta_{1}$ is $0$ and all other coordinates are non-zero. But $g$
evaluated in this point will not be zero, which contradicts $g$ being in
$\langle\theta-z\rangle$. Hence the only option is that $g$ is the zero
polynomial. We have now concluded that
$J\subseteq\ker\psi\subseteq\ker\varphi$. Since $\ker\varphi$ is a minimal
prime of $J$ and $\ker\psi$ is a prime ideal, we must have
$\ker\psi=\ker\varphi$. If one uses $\ell_{1},\ldots,\ell_{n}$ as variables,
$\ker\psi$ is a toric ideal. ∎

In what remains of this section we discuss the _ideal of minors_ for a staged
tree model $\mathcal{T}$ as a candidate for $J$ in Theorem 4.2. Let $c$ be a
stage and let $k$ be the number of children for a vertex of this stage. We
define the _stage matrix_ $M_{c}$ to be the matrix with columns
$[p_{[u_{1}]},\dots,p_{[u_{k}]}]^{\top}$ for each vertex $u$ in the stage $c$.
Let $J_{c}$ be the determinantal ideal generated by all $2\times 2$-minors of
$M_{c}$. The generators of $J_{c}$ has the form
$p_{[u_{i}]}p_{[v_{j}]}-p_{[u_{j}]}p_{[v_{i}]}$. The ideal of minors
$J_{\mathcal{T}}$ for the staged tree $\mathcal{T}$ is the sum of ideals
$J_{c}$ for all stages $c$ of $\mathcal{T}$. Authors in [8] refer this ideal
as the _ideal of paths_. They show in [8, Lemma 9] that $J_{\mathcal{T}}$ is
included in $\ker\varphi_{\mathcal{T}}$ and contains the ideal of model
invariants. These results combined with 4.1 give the following.

######  Lemma 4.3.

For a staged tree $\mathcal{T}$, we have the chain of inclusions
$I_{\mathcal{T}}\subseteq J_{\mathcal{T}}\subseteq\ker\varphi_{\mathcal{T}}$,
and the prime ideal $\ker\varphi_{\mathcal{T}}$ is a minimal prime for the
ideal of minors $J_{\mathcal{T}}$.

The fact that $J_{\mathcal{T}}$ is a determinantal ideal allows us to choose
from many different generating sets via elementary row and column operations.

######  Lemma 4.4.

Elementary row and column operations on a matrix do not change its associated
determinantal ideals.

This lemma is a well known property of determinantal ideals. For completeness
we include a proof for the case of $2\times 2$-minors. The proof for $t\times
t$ minors with $t>2$ is analogous.

###### Proof.

Denote by $m_{ij}$ the $(i,j)$-entry of a matrix $M$ with entries from some
polynomial ring $R$, and by $M_{\\{i,j\\}\times\\{k,l\\}}$ the $2\times 2$
minor of $M$ that uses rows $i<j$, and columns $k<l$. It is enough to prove
that the determinantal ideal does not change when one substitutes row $m_{1}$
by a linear combination of all the rows $a_{1}m_{1}+\dots+a_{n}m_{n}$ with
$a_{1}\neq 0$. Call the second matrix $M^{\prime}$. All the $2\times 2$-minors
not involving the first row in $M^{\prime}$ are the same as the respective
ones in $M$, so
$M^{\prime}_{\\{i,j\\}\times\\{k,l\\}}=M_{\\{i,j\\}\times\\{k,l\\}}$ for
$i\neq 1$. The minors that involve the first row are linear combination of
minors in $M$:

$M^{\prime}_{\\{1,j\\}\times\\{k,l\\}}=\det\left(\begin{bmatrix}a_{1}m_{1k}+\cdots+a_{n}m_{nk}&a_{1}m_{1l}+\cdots+a_{n}m_{nl}\\\
m_{jk}&m_{jl}\end{bmatrix}\right)=\sum\limits_{i=1}^{n}a_{i}\det\left(\begin{bmatrix}m_{ik}&m_{il}\\\
m_{jk}&m_{jl}\end{bmatrix}\right)=0.$ (19)

Since all but the first minor in the sum are already minors in $M^{\prime}$ up
to possibly a change of sign, minors $M^{\prime}_{\\{1,j\\}\times\\{k,l\\}}$
can substitute $M_{\\{1,j\\}\times\\{k,l\\}}$ as generators in the
determinantal ideal of $M$. ∎

The main idea is to apply appropriate row and column operations on each stage
matrix $M_{c}$ that produce a total of exactly $n$ distinct entries in the
final matrices. These entries will be the new variables
$\ell_{1},\ldots,\ell_{n}$ in 4.2.

######  Example 4.5.

Consider the tree in Fig. 8. This tree is not balanced. The ideal of minors
$J_{\mathcal{T}}$ is generated by the $2\times 2$ minors of stage matrices

$M_{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\pgfsys@color@cmyk@stroke{1}{0}{1}{0}\pgfsys@color@cmyk@fill{1}{0}{1}{0}\bullet}=\begin{bmatrix}p_{1}&p_{10}\\\
p_{2}&p_{11}\end{bmatrix}\quad\text{and}\quad
M_{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\bullet}=\begin{bmatrix}p_{3}&p_{6}&p_{1}+p_{2}&p_{1}+\cdots+p_{8}\\\
p_{4}&p_{7}&p_{3}+p_{4}+p_{5}&p_{9}\\\
p_{5}&p_{8}&p_{6}+p_{7}+p_{8}&p_{10}+p_{11}\end{bmatrix}.$ (20)

Substitute the second row of
$M_{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\pgfsys@color@cmyk@stroke{1}{0}{1}{0}\pgfsys@color@cmyk@fill{1}{0}{1}{0}\bullet}$
by the sum of the two rows. In
$M_{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\bullet}$
we first substitute the second row by the sum of its three rows, and then we
substitute its new first column by the sum of its negative, the negative of
the second column, and the third column. This results in the two matrices

$M^{\prime}_{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\pgfsys@color@cmyk@stroke{1}{0}{1}{0}\pgfsys@color@cmyk@fill{1}{0}{1}{0}\bullet}=\begin{bmatrix}p_{1}&p_{10}\\\
p_{1}+p_{2}&p_{10}+p_{11}\end{bmatrix}\ \text{and}\
M^{\prime}_{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\bullet}=\begin{bmatrix}p_{1}+p_{2}-p_{3}-p_{6}&p_{6}&p_{1}+p_{2}&p_{1}+\cdots+p_{8}\\\
p_{1}+p_{2}&p_{6}+p_{7}+p_{8}&p_{1}+\cdots+p_{8}&p_{1}+\cdots+p_{11}\\\
-p_{5}+p_{6}+p_{7}&p_{8}&p_{6}+p_{7}+p_{8}&p_{10}+p_{11}\end{bmatrix}.$ (21)

Take $\ell_{1}=p_{1}$, $\ell_{2}=p_{1}+p_{2}$,
$\ell_{3}=p_{1}+p_{2}-p_{3}-p_{6}$, $\ell_{4}=-p_{5}+p_{6}+p_{7}$,
$\ell_{6}=p_{6}+p_{7}+p_{8}$, $\ell_{7}=p_{8}$, $\ell_{8}=p_{1}+\cdots+p_{8}$,
$\ell_{9}=p_{10}$, $\ell_{10}=p_{10}+p_{11}$ and
$\ell_{11}=p_{1}+\cdots+p_{11}$. One can check that $\ell_{1},\dots,\ell_{11}$
are linearly independent. The ideal of minors is a binomial ideal in the new
variables. Images of $\varphi_{\mathcal{T}}(\ell_{i})$ are represented by
monomials in $\mathbb{R}[\Theta,z]/\langle\theta-z\rangle$. For instance
$\varphi_{\mathcal{T}}(\ell_{1})=\theta_{1}^{2}\tau_{1}$,
$\varphi_{\mathcal{T}}(\ell_{2})=\theta_{1}^{2}z$,
$\varphi_{\mathcal{T}}(\ell_{3})=\theta_{1}^{3}$, and
$\varphi_{\mathcal{T}}(\ell_{11})=z^{3}$. By 4.2, the prime ideal of the
staged tree $\mathcal{T}$ is toric in the new variables
$\ell_{1},\dots,\ell_{11}$.

In the following section we apply 4.2 to a concrete class of staged tree
models with a nice combinatorial description.

Figure 7: A non-balanced staged tree which has a toric structure by Theorem
4.2.

Figure 8: An SIP-tree.

##  5 Extending the class of toric staged tree models

In this section we extend the class of staged tree models for which the ideal
$\ker\varphi_{\mathcal{T}}$ is toric by allowing a linear change of variables.

The trees we will study here are trees where (a subset of) their stages have
the following property concerning induced subtrees. We say that a stage $c$
has the _subtree-inclusion property_ , for short SIP, if there is an index
$i_{c}$ such that for every vertex $v$ of the stage $c$ each induced subtree
$\mathcal{T}(v_{i})$ contains a subtree identical to $\mathcal{T}(v_{i_{c}})$
with root $v_{i}$. A staged tree is henceforth called a SIP-tree if all of its
stages satisfy the subtree-inclusion property.

An example of an SIP-tree is a staged tree where there is an $i$ such that the
$i$-th child of each vertex is a leaf. In particular the tree in Fig. 1 is
SIP. The tree in Fig. 8 is SIP with
$i_{\color[rgb]{1,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,0}\pgfsys@color@cmyk@stroke{0}{0}{1}{0}\pgfsys@color@cmyk@fill{0}{0}{1}{0}\bullet}=1$
or $2$,
$i_{\color[rgb]{0,0.5,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,1}\pgfsys@color@cmyk@stroke{1}{0.50}{0}{0}\pgfsys@color<EMAIL_ADDRESS>and
$i_{\color[rgb]{0.5,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,1,0}\pgfsys@color@cmyk@stroke{0.50}{0}{1}{0}\pgfsys@color<EMAIL_ADDRESS>If we have a SIP-tree, we can always redraw it so that $i_{c}=1$ for each
stage $c$. Throughout this section we will assume all SIP-trees to be
presented in this way.

Consider an SIP-tree $\mathcal{T}$. Our goal is to prove that the ideal
$\ker\varphi_{\mathcal{T}}$ is toric after a linear change of variables. In
order to do this we will introduce a stratified version of $\mathcal{T}$ which
we denote $\mathcal{T}_{\operatorname{str}}$. The staged tree
$\mathcal{T}_{\operatorname{str}}$ is identical to $\mathcal{T}$ as a tree,
not considering edge-labels and colours of vertices. We let two vertices in
$\mathcal{T}_{\operatorname{str}}$ be in the same stage if they lie on the
same distance from the root, and are in the same stage in $\mathcal{T}$. The
edges of $\mathcal{T}_{\operatorname{str}}$ are labelled accordingly. The
stratified version $\mathcal{T}_{\operatorname{str}}$ of a SIP-tree is also
SIP as the subtrees that are required to be identical in $\mathcal{T}$ always
sit at the same distance from the root. The benefit of going via
$\mathcal{T}_{\operatorname{str}}$ to study $\mathcal{T}$ is that there are no
linear relations in the prime ideal of $\mathcal{T}_{\operatorname{str}}$. If
$\Theta_{\operatorname{str}}$ denotes the set of labels in the tree
$\mathcal{T}_{\operatorname{str}}$, and
$\langle\theta-z\rangle_{\operatorname{str}}\subset\mathbb{R}[\Theta_{\operatorname{str}},z]$
the ideal of homogenised sum-to-one conditions, we have a canonical map
$F:\mathbb{R}[\Theta_{\operatorname{str}},z]/\langle\theta-z\rangle_{\operatorname{str}}\to\mathbb{R}[\Theta,z]/\langle\theta-z\rangle$.
In other words, we define $F$ so that the composition
$\varphi_{\mathcal{T}}=F\circ\varphi_{\mathcal{T}_{\operatorname{str}}}$
holds.

The key to proving that $\ker\varphi_{\mathcal{T}}$ is toric is to apply 4.2
with $J$ being the ideal of minors $J_{\mathcal{T}}$. To find a choice of
variables for which $J_{\mathcal{T}}$ is binomial we apply row and column
operations to the matrices $M_{c}$, following Lemma 4.4. The first step is to
translate the SIP into a statement on the entries of the stage matrices
$M_{c}$.

######  Lemma 5.1.

Let $\mathcal{T}$ be an SIP-tree, and let $\theta_{1},\ldots,\theta_{k}$ be
labels corresponding to a stage in the stratified tree
$\mathcal{T}_{\operatorname{str}}$. Let $v\in\mathcal{T}_{\operatorname{str}}$
be a vertex such that the root-to-$v$ path goes through an edge labelled
$\theta_{1}$. Then for each $i=1,\ldots,k$ there is a vertex $u$ such that
$\frac{\theta_{i}}{\theta_{1}}\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]})=\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[u]})$.
Moreover, if $v$ is not a leaf then $u$ and $v$ are in the same stage in
$\mathcal{T}_{\operatorname{str}}$.

###### Proof.

Let $w$ be the vertex where the path to $v$ takes the $\theta_{1}$-edge. Then
$v$ belongs to the subtree $\mathcal{T}_{\operatorname{str}}(w_{1})$. Since
$\mathcal{T}$ is SIP, each induced subtree
$\mathcal{T}_{\operatorname{str}}(w_{i})$ contains a subtree identical to
$\mathcal{T}_{\operatorname{str}}(w_{1})$ with root $w_{i}$. So we can find a
vertex $u$ in $\mathcal{T}_{\operatorname{str}}(w_{i})$ where the path from
$w_{i}$ to $u$ copies the steps of the path from $w_{1}$ to $v$. Then
$\frac{\theta_{i}}{\theta_{1}}\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]})=\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[u]})$,
and if $v$ is not a leaf then $u$ and $v$ are in the same stage. ∎

The first outgoing edges of vertices in our SIP-tree $\mathcal{T}$ will play
an important role in the proof of 5.3. For short we will refer to such edges
as _first-edges_. The next step is to prove that the linear forms that we will
use as a new basis for $\mathbb{R}[p]$ are indeed $n$ linearly independent
forms.

######  Lemma 5.2.

Let $L$ be the set of monomials in
$\mathbb{R}[\Theta_{\operatorname{str}},z]/\langle\theta-z\rangle_{\operatorname{str}}$
given by the root-to-leaf paths in $\mathcal{T}_{\operatorname{str}}$ and
substituting every label of a first-edge by the variable $z$. Then $L$ lies in
the image of the map $\varphi_{\mathcal{T}_{\operatorname{str}}}$, and the
preimage of $L$ is a set of $n$ linearly independent linear forms.

###### Proof.

Let $A$ be the set obtained from the monomials in
$\mathbb{R}[\Theta_{\operatorname{str}},z]/\langle\theta-z\rangle_{\operatorname{str}}$
given by the root-to-leaf paths and substituting every label of a first-edge
by the sum of the labels corresponding to that stage. It follows by repeated
use of 5.1 that each term in the expansion of such expression lies in the
image of $\varphi_{\mathcal{T}_{\operatorname{str}}}$. On the other hand
$A=L$, since the sum of the labels corresponding to a stage equals $z$. This
proves that $L$ is in the image of
$\varphi_{\mathcal{T}_{\operatorname{str}}}$. Moreover, the fact that the
first parameter of each stage does not occur in the monomials in $\mathcal{M}$
makes the distinct monomials in $A$ linearly independent. Now, let’s consider
$\mathbb{R}[p]$ and
$\mathbb{R}[\Theta_{\operatorname{str}},z]/\langle\theta-z\rangle_{\operatorname{str}}$
as $\mathbb{R}$-spaces. More precisely, we consider the subspaces
$\mathbb{R}[p]_{1}=\operatorname{span}(p_{1},\ldots,p_{n})$ and
$\operatorname{span}L$. Recall that there are no linear relations in
$\ker\varphi_{\mathcal{T}_{\operatorname{str}}}$ as
$\mathcal{T}_{\operatorname{str}}$ is squarefree. This is the same as saying
that the restricted map
$\varphi_{\mathcal{T}_{\operatorname{str}}}:\mathbb{R}[p]_{1}\to\operatorname{span}L$
is bijective. But then the preimages of the elements of $A$ is just another
choice of basis for $\mathbb{R}[p]_{1}$. ∎

Now we are ready to prove that the all SIP-trees have toric structure.

######  Theorem 5.3.

If $\mathcal{T}$ is an SIP-tree then the associated ideal
$\ker\varphi_{\mathcal{T}}$ is toric after a change of variables. The
parametrisation revealing the toric structure is given by substituting the
first parameter of each stage by the homogenising variable $z$ in the
monomials

$z^{d-d(\lambda_{i})}\prod_{e\in E(\lambda_{i})}\theta(e)\ \ \ \ \ \text{for
}i=1,\ldots,n$

from Eq. 4. Moreover, $p_{1}+\dots+p_{n}$ is one of the new variables.

###### Proof.

For each stage $c$ of vertices in $\mathcal{T}$ we associate the matrix
$M_{c}$ from which we get the ideal of minors $J_{c}$. Let
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M_{c})$ denote the matrices
obtained by applying $\varphi_{\mathcal{T}_{\operatorname{str}}}$ to the
entries of $M_{c}$. The entries of
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M_{c})$ are represented by
monomials. The idea is to do row and column operations to $M_{c}$ resulting in
a matrix $M_{c}^{\prime}$ such that the entries of
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M_{c}^{\prime})$ are monomials
from the set $\mathcal{M}$ defined as in Lemma 5.2. We point out that the
matrices $M_{c}$ considered here do not necessarily define the ideals of
minors of $\mathcal{T}_{\operatorname{str}}$. The matrix
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M_{c})$ only serves as an
intermediate step in understanding the effect of row and column operations on
$M_{c}$.

Recall that the columns in the matrix $M_{c}$ are indexed by the vertices in
the stage $c$ in $\mathcal{T}$. The entries in the column of
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M_{c})$ indexed by a vertex $v$
are

$\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v_{1}]})=\theta_{1}\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]}),\
\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v_{2}]})=\theta_{2}\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]}),\
\ldots,\
\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v_{k}]})\theta_{k}\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]})$

where $\theta_{1},\ldots,\theta_{k}$ are the labels of the stage of $v$ in
$\mathcal{T}_{\operatorname{str}}$. Suppose the root-to-$v$ path goes through
exactly $m>0$ first-edges, and let

$\\{\tau_{11},\tau_{12},\ldots,\tau_{1k_{1}}\\},\\{\tau_{21},\tau_{22},\ldots,\tau_{2k_{2}}\\},\ldots,\\{\tau_{m1},\tau_{m2},\ldots,\tau_{mk_{m}}\\}$

be the sets of label of the corresponding $m$ stages in
$\mathcal{T}_{\operatorname{str}}$, so that
$\tau_{11}\tau_{21}\cdots\tau_{m1}$ divides
$\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]})$. By repeated use of
Lemma 5.1, we see that for each $m$-tuple $(j_{1},\ldots,j_{m})$ of integers
$1\leq j_{i}\leq k_{i}$ there is a vertex $u$ in the same stage as $v$ such
that

$\frac{\tau_{1j_{1}}\tau_{2j_{s}}\cdots\tau_{mj_{m}}}{\tau_{11}\tau_{21}\cdots\tau_{m1}}\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]})=\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[u]}).$
(22)

Since $u$ is also in the same stage as $v$ in $\mathcal{T}$ there is a column
for $u$ in $M_{c}$. Consider the column operation that replaces the $v$-column
by the sum of the $k_{1}k_{2}\cdots k_{m}$ columns of those $u$’s. Then the
entry $p_{[v_{i}]}$ in row $i$ is replaced by the linear form
$\sum_{u}p_{[u_{i}]}$ such that

$\displaystyle\varphi_{\mathcal{T}_{\operatorname{str}}}\Big{(}\sum_{u}p_{[u_{i}]}\Big{)}$
$\displaystyle=\theta_{i}\sum_{u}\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[u]})$
(23)
$\displaystyle=\theta_{i}\frac{(\tau_{11}+\dots+\tau_{1k_{1}})(\tau_{21}+\dots+\tau_{2k_{2}})(\tau_{m1}+\dots+\tau_{mk_{m}})}{\tau_{11}\tau_{21}\cdots\tau_{m1}}\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]})$
(24)
$\displaystyle=\theta_{i}\frac{z^{m}}{\tau_{11}\tau_{21}\cdots\tau_{m1}}\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]}).$
(25)

In other words, all labels of first-edges in
$\varphi_{\mathcal{T}_{\operatorname{str}}}(p_{[v]})$ were substituted by $z$.
The idea is to do several such column operations, but we must be careful in
which order to do them. Notice that the root-to-$u$ path, for each of the
$u$’s we consider above, goes through at most $m$ first-edges. Moreover it
goes through exactly $m$ first-edges only if $u=v$. So we can order the
columns we want to operate on in weakly decreasing order according to their
associated number $m$ of first-edges. In this way the columns that are used in
each step are columns from the original matrix $M_{c}$.

Let $M^{\prime}_{c}$ be the resulting matrix when we have done the above
operation to all columns where it can be applied. The entries of
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M^{\prime}_{c})$ are all of the
form (23). What remains is to eliminate the $\theta_{1}$’s in the first row.
This is accomplished by the row operation replacing the first row by the sum
of all rows. Let $M^{\prime\prime}_{c}$ denote the matrix obtained after this
row operation. The entries
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M^{\prime\prime}_{c})$ are
monomials obtained from the entries of
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M_{c})$ and substituting the
labels of first-edges by $z$. Now remember that the entries of $M_{c}$ are all
of the form $p_{[v]}$ for some vertex $v$. Consider the root-to-leaf path
going through $v$ and after $v$ taking the first-edge in each step. Then take
the product of the labels along this path, and substitute each label of a
first-edge by $z$. This gives the corresponding entry in the matrix
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M^{\prime\prime}_{c})$, and in
this way we see that all entries of
$\varphi_{\mathcal{T}_{\operatorname{str}}}(M^{\prime\prime}_{c})$ belong to
the set $\mathcal{M}$. By Lemma 5.2 the distinct entries of
$M^{\prime\prime}_{c}$ are linearly independent linear forms
$\ell_{1},\ldots,\ell_{n}$. The 2-minors of $M^{\prime\prime}_{c}$ is then a
set of binomials in $\ell_{1},\ldots,\ell_{n}$ which is a generating set of
the ideal $J_{c}$. It follows that $J_{\mathcal{T}}$ is generated by binomials
in $\ell_{1},\ldots,\ell_{n}$. By this the requirements of Theorem 4.2 are
fulfilled, and we have proved that $\ker\varphi_{\mathcal{T}}$ is toric after
a linear change of variables. Last, $p_{1}+\dots+p_{n}$ is among the new
variables as it is the preimage of $z^{d}$. ∎

We have now seen two types of staged trees giving rise to toric ideals: the
balanced trees and the SIP-trees. Next we shall see that we can combine these
two classes to construct even more toric staged trees.

######  Theorem 5.4.

Let $\mathcal{T}$ be a staged tree, and let $\mathcal{S}$ be a subtree with
the same root as $\mathcal{T}$. Let $v_{1},\ldots,v_{m}$ denote the vertices
of $\mathcal{T}$ which are leaves of the subtree $\mathcal{S}$. Suppose

  1. 1.

the tree $\mathcal{S}$ is balanced,

  2. 2.

no internal vertex of $\mathcal{S}$ is in the same stage as a vertex in some
$\mathcal{T}(v_{i})$,

  3. 3.

the stages of vertices in $\mathcal{T}(v_{1}),\ldots,\mathcal{T}(v_{m})$
satisfy the subtree-inclusion property.

Then $\mathcal{T}$ has toric structure.

###### Proof.

Let
$\varphi_{\mathcal{S}}:\mathbb{R}[q_{1},\ldots,q_{m}]\to\mathbb{R}[\Theta,z]$
and $\varphi_{\mathcal{T}}:\mathbb{R}[p]\to\mathbb{R}[\Theta,z]$ be defined in
the usual way. This means that $\varphi_{\mathcal{S}}$ maps $q_{i}$ to the
product of the edge labels along the path from the root to $v_{i}$, or in
other words $\varphi_{\mathcal{S}}(q_{i})=\varphi_{\mathcal{T}}(p_{[v_{i}]})$.
Let $\overline{\ker\varphi_{\mathcal{S}}}$ denote the ideal of $\mathbb{R}[p]$
obtained from $\ker\varphi_{\mathcal{S}}$ by substituting each $q_{i}$ by
$p_{[v_{i}]}$. As $\mathcal{S}$ is a balanced staged tree the ideal
$\ker\varphi_{\mathcal{S}}$ is binomial. Then
$\overline{\ker\varphi_{\mathcal{S}}}$ is generated by binomials in
$p_{[v_{1}]},\ldots,p_{[v_{m}]}$. We construct the ideal
$\overline{I_{\mathcal{S}}}\subset\mathbb{R}[p]$ from
$I_{\mathcal{S}}\subset\mathbb{R}[q_{1},\ldots,q_{m}]$ in the same way. The
ideal $\overline{I_{\mathcal{S}}}$ is exactly the same as taking the sum of
the ideals $I_{c}$ over all stages $c$ of $\mathcal{T}$ that occurs in the
subtree $\mathcal{S}$.

Let $C$ be the set of stages that occur in the induced subtrees
$\mathcal{T}(v_{1}),\ldots,\mathcal{T}(v_{m})$. For a stage $c\in C$ the
matrix $M_{c}$ is a $1\times m$ block matrix where the $i$-th block is the
matrix of the stage $c$ in $\mathcal{T}(v_{i})$. We can do the column
operations from the proof of Theorem 5.3 to each of the blocks. We can also do
the row operation of replacing the first row by the sum of all rows
simultaneously on all blocks. It then follows in the same way as in the proof
of Theorem 5.3 that $\sum_{c\in C}J_{c}$ is a binomial ideal in linearly
independent linear forms $\ell_{1},\ldots,\ell_{n}$. Among
$\ell_{1},\ldots,\ell_{n}$ we find $p_{[v_{1}]},\ldots,p_{[v_{m}]}$.

The idea is now to apply Theorem 4.2 with the ideal
$J=\overline{\ker\varphi_{\mathcal{S}}}+\sum_{c\in C}J_{c}$. We have seen that
$J$ is generated by binomials in $\ell_{1},\ldots,\ell_{n}$, and it is clear
that $J\subseteq\ker\varphi_{\mathcal{T}}$. We also have the inclusion
$I_{\mathcal{T}}\subseteq J$ as

$I_{\mathcal{T}}=\overline{I_{\mathcal{S}}}+\sum_{c\in
C}I_{c}\subseteq\overline{\ker\varphi_{\mathcal{S}}}+\sum_{c\in C}J_{c}=J$

which completes the proof. ∎

######  Remark 5.5.

The balanced trees are covered by Theorem 5.4, as we can take $\mathcal{S}$ to
be the whole tree. Theorem 5.4 also covers SIP-trees as we can take
$\mathcal{S}$ as just the root.

######  Remark 5.6.

Even though the Theorems 5.3 and 5.4 do not give explicit expressions for the
linear change of variables revealing the toric structure of
$\ker\varphi_{\mathcal{T}}$, the proofs are constructive. Given any staged
tree $\mathcal{T}$ covered by 5.4, the linear change of variables can be
obtained following the steps in the two proofs.

######  Example 5.7.

We now return to the tree $\mathcal{T}$ in Fig. 6 discussed in Example 3.11.
Let $v_{1},\ldots,v_{8}$ be the vertices on distance 3 from the root, and let
$\mathcal{S}$ be the subtree with $v_{1},\ldots,v_{8}$ as leaves. Then
$\mathcal{S}$ is balanced, and the light green and dark green stages in
$\mathcal{T}(v_{1}),\ldots,\mathcal{T}(v_{8})$ satisfy the subtree-inclusion
property as all children of the green vertices are leaves. So we can apply
Theorem 5.4, and it follows that $\ker\varphi_{\mathcal{T}}$ is toric. The
ideal $\overline{\ker\varphi_{\mathcal{S}}}$ defined as in the proof of
Theorem 5.4 is generated by binomials in the linear forms

$\\{p_{[v_{1}]},\ldots,p_{[v_{8}]}\\}=\\{p_{1}+p_{2},\ p_{3},\ p_{4}+p_{5},\
p_{6},\ p_{7}+p_{8},\ p_{9},\ p_{10}+p_{11},\ p_{12}\\}.$ (26)

The ideals
$J_{\color[rgb]{0.5,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,1,0}\pgfsys@color@cmyk@stroke{0.50}{0}{1}{0}\pgfsys@color<EMAIL_ADDRESS>and
$J_{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color<EMAIL_ADDRESS>are given by the determinants

$\begin{vmatrix}p_{1}&p_{10}\\\
p_{2}&p_{11}\end{vmatrix}=\begin{vmatrix}p_{1}+p_{2}&p_{10}+p_{11}\\\
p_{2}&p_{11}\end{vmatrix}\ \text{ and }\ \begin{vmatrix}p_{4}&p_{7}\\\
p_{5}&p_{8}\end{vmatrix}=\begin{vmatrix}p_{4}+p_{5}&p_{7}+p_{8}\\\
p_{5}&p_{8}\end{vmatrix}.$ (27)

Altogether, $\ker\varphi_{\mathcal{T}}$ is a binomial ideal if we choose
$p_{1}+p_{2},\ p_{2},\ p_{3},\ p_{4}+p_{5},\ p_{5},\ p_{6},\ p_{7}+p_{8},\
p_{8},\ p_{9},p_{10}+p_{11},p_{11},p_{12}$ as new variables.

##  6 One-stage tree models

This section explores the algebraic structure of staged trees with all inner
vertices in the same stage, called _one-stage trees_. We connect staged tree
models represented by binary one-stage trees to Veronese embeddings—well known
maps in algebraic geometry and commutative algebra [6, 3, 22]. We further show
that all binary one-stage tree models have toric structure and give evidence
of this toric structure in other classes.

Take positive integers $k$ and $d$ and let $\mathbb{R}[\Theta]$ be the
polynomial ring in variables $\theta_{1},\dots,\theta_{k}$. The Veronese
embedding associated to $k$ and $d$ is defined as the map

$\nu_{k,d}\colon\mathbb{R}[q_{\boldsymbol{i}}\mid\boldsymbol{i}\in\mathbb{Z}_{\geq
0}^{k},i_{1}+\cdots+i_{k}=d]\rightarrow\mathbb{R}[\Theta],\quad\nu_{k,d}(q_{\boldsymbol{i}})=\theta^{\boldsymbol{i}}.$
(28)

The kernel of $\nu_{k,d}$ is the toric ideal of the Veronese embedding. It is
generated by quadratics
$q_{\boldsymbol{i}}q_{\boldsymbol{j}}=q_{\boldsymbol{s}}q_{\boldsymbol{t}}$
such that $\boldsymbol{i}+\boldsymbol{j}=\boldsymbol{s}+\boldsymbol{t}$. The
algebra $\mathrm{im}\,\nu_{k,d}$ in $\mathbb{R}[\Theta]$ over $\mathbb{R}$ is
the _Veronese algebra_ for positive integers $k$ and $d$. We will use this
notion extensively in this section. The set with the $\binom{k+d-1}{d}$
monomials $\Theta^{d}={\\{\theta^{\boldsymbol{i}}\mid i\in\mathbb{Z}_{\geq
0}^{k},i_{1}+\cdots+i_{k}=d\\}}$ is the _canonical basis_ for the Veronese
algebra $\mathrm{im}\,\nu_{k,d}$.

Denote henceforth by $\mathfrak{T}_{k,d}$ the set of all one-stage trees of
depth $d$ with parameters $\theta_{1},\dots,\theta_{k}$. The staged trees with
the lowest number of edges in $\mathfrak{T}_{k,d}$ are the ones that have the
form of a _caterpillar_ , that is they have exactly one internal node at each
level. The symbol $\mathcal{C}$ is now used to indicate such a tree. The trees
in $\mathfrak{T}_{k,d}$ with the highest number of edges are the ones where
all root-to-leaf paths have depth $d$. These are called _maximal_ trees. Even
though one-stage tree models have this strong restriction of having exactly
one stage, they still provide a variety of models not covered by previous
results. For instance, only one-stage maximal trees where all leaves are at
the same distance from the root are balanced. And the staged tree in Fig. 3 as
well as trees
$\mathcal{T}_{8},\mathcal{T}_{10},\mathcal{T}_{11},\mathcal{T}_{14},\mathcal{T}_{18}$
in Fig. 11 do not satisfy the subtree-inclusion property of 5.3.

######  Lemma 6.1.

Maximal trees are the only balanced one-stage tree models in
$\mathfrak{T}_{k,d}$.

###### Proof.

Let $u_{1},\dots,u_{k}$ be children of an internal vertex $u$ of the one-stage
tree $\mathcal{T}$. If the tree is maximal then $t(u_{i})=t(u_{j})$ for all
children $u_{i}$ and $u_{j}$ of $u$. Hence, the equality
$t(u_{i})t(v_{j})=t(u_{j})t(v_{i})$ is true for any two internal vertices in
the maximal one-stage tree. If the tree is not maximal, there must be a vertex
$u$ in $\mathcal{T}$ that has both a leaf $u_{i}$ and another internal vertex
$u_{j}$ as its children. Take any vertex $v$ in $\mathcal{T}$ with all leaves
as its children. The sides of the equation $t(u_{i})t(v_{j})=t(v_{i})t(u_{j})$
are then of different degrees, making equality impossible. ∎

Given a one-stage tree $\mathcal{T}$ and one of its root-to-leaf paths
$\lambda$, let $\boldsymbol{i}_{\lambda}$ be the vector in $\mathbb{Z}_{\geq
0}^{k}$ recording the number of times $\theta_{1},\dots,\theta_{k}$ appear in
$\lambda$. The algebra associated to $\mathcal{T}$ has the form

$\mathrm{im}\,\varphi_{\mathcal{T}}=\mathbb{R}[\theta^{\boldsymbol{i}_{\lambda}}\mid\lambda\text{
root-to-leaf path in }\mathcal{T}]/\langle\theta-z\rangle.$ (29)

######  Lemma 6.2.

The algebra of any one-stage tree model in $\mathfrak{T}_{k,d}$ is a
subalgebra of the Veronese algebra $\mathrm{im}\,\nu_{k,d}$.

###### Proof.

Take $\boldsymbol{i}_{\lambda}=(i_{1},\dots,i_{k})$ as above. By the
multinomial theorem, each generator
$\theta^{\boldsymbol{i}_{\lambda}}z^{d-i_{1}-\cdots-
i_{k}}=\theta^{\boldsymbol{i}_{\lambda}}(\theta_{1}+\cdots+\theta_{k})^{d-i_{1}-\cdots-
i_{k}}$ in the image of $\varphi_{\mathcal{T}}$ is a linear combination of the
generators of $\mathrm{im}\,\nu_{k,d}$. ∎

######  Remark 6.3.

The involvement of Veronese algebras in both the definition of a Multinomial
distribution and in the one-stage tree models allows us to draw a natural
connection between these two concepts. This extends the well-known connection
of squarefree staged trees to these distributions [19]. Recall that a
Multinomial distribution models the outcome of $d$ repeated experiments where
the outcome of each trial has a categorical distribution with state space
$\Omega$ of size $k$ and associated probabilities
$\theta_{1},\dots,\theta_{k}$. The probability that in $d$ trials, the
$i^{\text{th}}$ output in $\Omega$ appears exactly $t_{i}$ times, for
$i=1,\dots,k$, is
$\binom{d}{t_{1},\dots,t_{k}}\theta_{1}^{t_{1}}\dots\theta_{k}^{t_{k}}$ when
$t_{1}+\cdots+t_{k}=d$ and $0$ otherwise. These are all terms in the sum of
root-to-leaf parametrisations in the maximal tree of $\mathfrak{T}_{k,d}$.
Non-maximal one-stage trees can be interpreted as realisations of a
generalisation of a Multinomial distribution which involves conditions. The
terms in the sum of all root-to-leaf parametrisations, again, model the
probabilities of the possible outcomes. Compare for instance the example of
flipping a biased coin from the introduction of this present paper to
subsection on Bernoulli binary models in [3].

Returning to one-stage trees, the following is an immediate consequence of 2.3
and 6.2 and 2.5.

######  Corollary 6.4.

Let $\mathcal{T}\subset\mathcal{T}^{\prime}$ be two trees in
$\mathfrak{T}_{k,d}$ that share the same root. If
$\mathrm{im}\,\varphi_{\mathcal{T}}=\mathrm{im}\,\nu_{k,d}$ then
$\mathrm{im}\>\varphi_{\mathcal{T}^{\prime}}$ is equal to
$\mathrm{im}\,\nu_{k,d}$, too. In particular, all such trees have toric
structure.

In what follows we show that all one-stage trees in $\mathfrak{T}_{2,d}$ have
toric structure. We do this by first proving that any caterpillar tree in
$\mathfrak{T}_{2,d}$ has the Veronese algebra $\mathrm{im}\>\nu_{2,d}$ as its
algebra. 6.4 then completes the proof.

######  Theorem 6.5.

All binary one-stage trees have toric structure and are parametrised by
$\mathrm{im}\,\nu_{2,d}$.

###### Proof.

Take a caterpillar tree $\mathcal{C}$ of depth $d$ formed by cutting off
branches of a staged tree $\mathcal{T}$ in $\mathfrak{T}_{2,d}$. The strategy
is to prove inclusions
$\mathrm{im}\,\nu_{2,d}\subseteq\mathrm{im}\,\varphi_{\mathcal{C}}\subseteq\mathrm{im}\,\varphi_{\mathcal{T}}\subseteq\mathrm{im}\,\nu_{2,d}.$
We only need to prove the first inclusion as the other two hold by 2.3 and
6.2.

Use $\theta(i)$ and $\bar{\theta}(i)$ in $\\{\theta_{1},\theta_{2}\\}$ to
denote the parameters in edges emanating from the $i$-th internal vertex of
the caterpillar $\mathcal{C}$, where $\bar{\theta}(t)$ is in the edge leading
to a leaf and $i=1,\dots,d$; see Fig. 9.

Figure 9: A caterpillar tree in $\mathfrak{T}_{2,d}$. Here we have
$\theta(1)=\theta_{1},\,\bar{\theta}(1)=\theta_{2},\,\theta(2)=\theta_{2},\,\bar{\theta}(2)=\theta_{1}$,
and so on.

For every $t$ between $0$ and $d$, let $f_{t}=\theta(1)\cdots\theta(d-t)z^{t}$
and $\bar{f}_{t}=\theta(1)\cdots\theta(d-t-1)\bar{\theta}(d-t)z^{t}$. In
particular, $f_{d}=\bar{f}_{d}=z^{d}$. The form $\bar{f}_{t}$ changes from
$f_{t}$ only by the use of $\bar{\theta}(d-t)$ instead of $\theta(d-t)$. The
collection $\\{f_{t},\bar{f}_{t}\mid t=0,\cdots,d\\}$ includes all root-to-
leaf parametrisations in tree $\mathcal{C}$, and hence serves as a generating
set for the algebra $\mathrm{im}\>\varphi_{\mathcal{C}}$. Since $z$ is the sum
$\theta_{1}+\cdots+\theta_{k}$, the terms above can be rewritten as sums

$\displaystyle f_{t}$
$\displaystyle=\sum\limits_{i=0}^{t}\binom{t}{i}\theta(1)\cdots{\theta}(d-t)\cdot\theta_{1}^{i}\theta_{2}^{t-i}=\sum\limits_{i=0}^{t}\binom{t}{i}f_{t,i}$
(30) and $\displaystyle\bar{f}_{t}$
$\displaystyle=\sum\limits_{i=0}^{t}\binom{t}{i}\theta(1)\cdots\theta(d-t-1)\bar{\theta}(d-t)\cdot\theta_{1}^{i}\theta_{2}^{t-i}=\sum\limits_{i=0}^{t}\binom{t}{i}\bar{f}_{t,i}.$
(31)

For each $t$, take $F_{t}=\\{f_{t,i}\mid i=0,\ldots,t\\}$ to be the support of
$f_{t}$. Similarly, take the set $\bar{F}_{t}=\\{\bar{f}_{t,i}\mid
i=0,\dots,t\\}$. Notice that when $t$ is not zero, all terms of $f_{t}$ appear
in either $f_{t-1}$ or $\bar{f}_{t-1}$. Therefore, $F_{t}$ is the union of
sets $F_{t-1}$ and $\bar{F}_{t-1}$.

We will show that each $F_{t}$ is included the image of
$\varphi_{\mathcal{C}}$. The set $F_{0}$ contains only one element, namely the
term $f_{0}$ which is one of the generators of
$\mathrm{im}\>\varphi_{\mathcal{C}}$. Assume this is true for the set
$F_{t-1}$. Since $F_{t}=F_{t-1}\cup\bar{F}_{t}$, it is enough to show that
$\bar{F}_{t}$ is in the image of $\varphi_{\mathcal{C}}$. The set
$\bar{F}_{0}$ is in the image of $\varphi_{\mathcal{C}}$ since its only
element is the generator $\bar{f}_{0}$. Take now $\bar{F}_{t}$ for some $t$
greater than zero. Then all but one term of $\bar{F}_{t}$ belong to $F_{t}$.
Indeed, if $\theta(d-t)$ is $\theta_{1}$ then $\bar{f}_{t,i}=f_{t,i-1}$, for
all $i=1,\dots,t$, and if $\theta(d-t)=\theta_{2}$, then
$\bar{f}_{t,i}=f_{t,i+1}$, for all $i=0,\dots,t-1$. In both cases the
remaining term is in the image of $\varphi_{\mathcal{C}}$ due to the sum in
Eq. 31 being in $\mathrm{im}\,\varphi_{\mathcal{C}}$. In particular, the
canonical generating set $F_{d}$ of $\mathrm{im}\,\nu_{2,d}$, is in the image
of $\varphi_{\mathcal{C}}$. Since all three inclusions are achieved, 2.5
concludes that all binary one-stage tree models have toric structure. ∎

######  Remark 6.6.

Example 2.6 suggest how we can use the monomial algebra
$\mathrm{im}\,\nu_{2,d}$ of a binary one-stage tree to obtain linear
transformations of variables that make $\ker\varphi_{\mathcal{T}}$ toric:
search for $n$ linearly independent linear forms $\ell_{1},\dots,\ell_{n}$ ,
where $n$ is the number of leaves, that map to monomials $\Theta^{d}$ of
$\mathbb{R}[\theta_{1},\theta_{2}]$. The resulting ideal is generated by
binomials of degree at most two.

Unfortunately, not all one-stage trees have Veronese algebras as their
defining algebras. Take for instance any caterpillar tree in
$\mathfrak{T}_{k,d}$ for $k$ and $d$ greater than two. For the algebra of a
one-stage tree model to be all $\mathrm{im}\,\nu_{k,d}$, the tree must contain
at least $\binom{k+d-1}{d}$ leaves. The $kd-d+1$ leaves of a caterpillar tree
with $k,d>2$ do not suffice. Even when a one-stage tree has enough leaves,
some of them may contribute to linear relations, and the algebra
$\mathrm{im}\,\varphi_{\mathcal{T}}$ can still be a proper subalgebra of
$\mathrm{im}\,\nu_{k,d}$. Such an example is any tree in the final row of Fig.
11. However, their algebras still appear to be monomial algebras generated by
subsets of the canonical basis of the Veronese algebra
$\mathrm{im}\,\nu_{k,d}$.

######  Theorem 6.7.

All three-parameter one-stage tree models of depth at most three have toric
structure.

###### Proof.

The only staged tree in $\mathfrak{T}_{3,1}$ has $\ker\varphi_{\mathcal{T}}$
equal to the zero ideal. Every algebra in $\mathfrak{T}_{3,2}$ is isomorphic
to the algebra of one of the three staged trees in Fig. 10 up to a permutation
of variables $\theta_{1},\theta_{2}$ and $\theta_{3}$. All of the three trees
in Fig. 10 satisfy the subtree-inclusion property of 5.3. In particular, the
algebra of the second staged tree shown in Fig. 10 is all
$\mathrm{im}\,\nu_{3,2}$. because
$\theta_{3}^{2}=\theta_{3}z-\theta_{1}\theta_{3}-\theta_{2}\theta_{3}$ is in
$\mathrm{im}\,\varphi_{T_{3}}$, providing further evidence of toric structure.

Figure 10: The three one-stage trees in $\mathfrak{T}_{3,2}$ up to a
permutation of parameters. The edges have labels
$\theta_{1},\theta_{2},\theta_{3}$, respectively, read from top to bottom.
They are all SIP trees.

The collection $\mathfrak{T}_{3,3}$ is quite large. As the remainder of this
proof will show, it will be enough to prove that the $20$ trees in Fig. 11
have toric structure.

Figure 11: Staged trees in $\mathfrak{T}_{3,3}$ with labels
$\theta_{1},\theta_{2},\theta_{3}$, respectively, read from top to bottom for
each stage. The trees $\mathcal{T}_{13}$ and $\mathcal{T}_{14}$ are defined by
the Veronese algebra $\mathrm{im}\,\nu_{3,3}$. The algebra of any other one-
stage tree in $\mathfrak{T}_{3,3}$ are either obtained by permuting parameters
of a tree in this table, or up to a permutation of parameters contain one of
the trees $\mathcal{T}_{13}$ or $\mathcal{T}_{14}$.

All but the trees numbered
$\mathcal{T}_{4},\mathcal{T}_{8},\mathcal{T}_{10},\mathcal{T}_{11},\mathcal{T}_{14}$,
and $\mathcal{T}_{18}$ in this table satisfy the subtree-inclusion property
and hence are toric by 5.3. Even more, the algebra of $\mathcal{T}_{13}$ is
the full Veronese algebra $\mathrm{im}\,\nu_{3,3}$. To realise this, compare
the generating set of $\mathcal{T}_{13}$ obtained by all root-to-leaf paths
with the canonical basis of $\mathrm{im}\,\nu_{3,3}$. The monomials
$\theta_{1}\theta_{2}\theta_{3},\theta_{1}\theta_{3}^{2},\theta_{2}\theta_{3}^{2}$
and $\theta_{3}^{3}$ in this basis do not coincide with any root-to-leaf path
parametrisation of $\mathcal{T}_{13}$. However, they all are linear
combinations of the latter ones:
$\theta_{1}\theta_{2}\theta_{3}=\theta_{1}\theta_{2}z-\theta_{1}^{2}\theta_{2}-\theta_{1}\theta_{2}^{2},\quad\theta_{1}\theta_{3}^{2}=\theta_{1}\theta_{3}z-\theta_{1}^{2}\theta_{3}-\theta_{1}\theta_{2}\theta_{3},\quad\theta_{2}\theta_{3}^{2}=\theta_{2}\theta_{3}z-\theta_{1}\theta_{2}\theta_{3}-\theta_{2}^{2}\theta_{3},$
and
$\theta_{3}^{3}=\theta_{3}z^{2}-\theta_{1}\theta_{3}z-\theta_{2}\theta_{3}z-\theta_{1}\theta_{3}^{2}-\theta_{2}\theta_{3}^{2}$.
By 6.2, all one-stage trees in $\mathfrak{T}_{3,3}$ that contain
$\mathcal{T}_{13}$ up to a permutation of parameters have toric structure.

By 2.3, the algebras of staged trees
$\mathcal{T}_{4},\mathcal{T}_{8},\mathcal{T}_{10},\mathcal{T}_{11}$, and
$\mathcal{T}_{18}$ are included in the monomial algebras of
$\mathcal{T}_{5},\mathcal{T}_{16},\mathcal{T}_{18},\mathcal{T}_{17}$, and
$\mathcal{T}_{19}$, respectively. We will show that the inclusions are
equalities, by comparing their root-to-leaf parametrisations. For
$\mathcal{T}_{4}$, its root-to-leaf parametrisation changes from the one of
$\mathcal{T}_{5}$ only by the absence of $\theta_{1}^{3}$. However,
$\theta_{1}^{3}$ is equal to the linear combination
$\theta_{1}^{2}z-\theta_{1}^{2}\theta_{2}z-\theta_{1}^{2}\theta_{3}z$ of
elements in $\mathrm{im}\,\varphi_{\mathcal{T}_{4}}$, read by root-to-leaf
paths. Via a similar argument, $\theta_{1}^{3}$ is equal to
$\theta_{1}^{2}z-\theta_{1}^{2}\theta_{2}z-\theta_{1}^{2}\theta_{3}z$ in
$\mathrm{im}\,\varphi_{\mathcal{T}_{18}}$, which makes the latter one equal to
$\mathrm{im}\>\varphi_{\mathcal{T}_{19}}$. In $\mathcal{T}_{8}$, the only
forms in $\mathrm{im}\,\varphi_{\mathcal{T}_{16}}$ not appearing in its root-
to-leaf paths are $\theta_{1}\theta_{3}z$ and $\theta_{3}^{2}z$. These can be
expressed as linear combinations of forms read from root-to-leaf paths
$\theta_{1}\theta_{3}z=-\theta_{1}^{2}\theta_{3}-\theta_{1}\theta_{2}\theta_{3}-\theta_{1}\theta_{3}^{2}$,
and
$\theta_{3}^{2}z=\theta_{3}z^{2}-\theta_{1}\theta_{3}z-\theta_{2}\theta_{3}z$
in $\mathrm{im}\,\varphi_{\mathcal{T}_{8}}$. The latter equality serves to
prove that
$\mathrm{im}\,\varphi_{\mathcal{T}_{10}}=\mathrm{im}\,\varphi_{\mathcal{T}_{18}}$
and
$\mathrm{im}\,\varphi_{\mathcal{T}_{11}}=\mathrm{im}\,\varphi_{\mathcal{T}_{17}}$.
By 2.7, the staged trees
$\mathcal{T}_{4},\mathcal{T}_{8},\mathcal{T}_{10},\mathcal{T}_{11}$, and
$\mathcal{T}_{18}$ have toric structures.

Lastly, the image of $\mathcal{T}_{14}$ is all the Veronese algebra
$\mathrm{im}\,\nu_{3,3}$. Similarly to $\mathcal{T}_{13}$, the four monomials
$\theta_{1}\theta_{2}^{2},\theta_{1}\theta_{3}^{2},\theta_{2}^{3}$, and
$\theta_{3}^{3}$ in the canonical basis of $\mathrm{im}\,\nu_{3,3}$ that do
not appear in the root-to-leaf parametrisation of $\mathcal{T}_{14}$ are
linear combinations of the latter ones:
$\theta_{1}\theta_{2}^{2}=\theta_{1}\theta_{2}z-\theta_{1}^{2}\theta_{2}-\theta_{1}\theta_{2}\theta_{3},\quad\theta_{1}\theta_{3}^{2}=\theta_{1}\theta_{3}z-\theta_{1}^{2}\theta_{3}-\theta_{1}\theta_{2}\theta_{3},\quad\theta_{2}^{3}=\theta_{2}^{2}z-\theta_{1}\theta_{2}^{2}-\theta_{2}^{2}\theta_{3},$
and
$\theta_{3}^{3}=\theta_{3}z^{2}-\theta_{1}\theta_{3}z-\theta_{1}\theta_{2}\theta_{3}-\theta_{2}^{2}\theta_{3}-\theta_{2}\theta_{3}^{2}-\theta_{1}\theta_{3}^{2}-\theta_{2}\theta_{3}^{2}$.
Due to 6.2, all one-stage trees in $\mathfrak{T}_{3,3}$ containing
$\mathcal{T}_{14}$ up to a permutation of parameters have toric structure.

Any tree in $\mathfrak{T}_{3,3}$ that does not appear in Fig. 11 either
contains $\mathcal{T}_{13}$ or $\mathcal{T}_{13}$ up to a permutation of
parameters, or is equal to one of the trees in the table up to such a
permutation. 6.2 and 2.7 thus conclude the proof. ∎

In the proof of 6.7 techniques developed throughout this paper come together.
These techniques can prove the toric structure of many other one-stage tree
models. For instance, the first two trees in Fig. 12 have toric structure, the
second one having $\mathrm{im}\,\nu_{3,4}$ as its defining algebra. There are
however still one-stage trees that provide challenges. The smallest such tree
is the caterpillar in Fig. 12(c).

(a) This is an SIP tree.

(b) This has algebra equal to $\mathrm{im}\,\nu_{3,4}$.

(c) Does this staged tree have toric structure?

Figure 12: Three staged trees in $\mathfrak{T}_{3,4}$. The edge-labels are
$\theta_{1},\theta_{2},\theta_{3}$, respectively, read from top to bottom for
each vertex.

######  Conjecture 6.8.

All one-stage tree models have toric structure.

We end this section with a discussion of the linear relations appearing in the
implicit description of a one-stage tree model. As the following two
propositions will show, unless the structure of the tree is a caterpillar, the
ideal $\ker\varphi_{\mathcal{T}}$ of one-stage tree models always contains
linear relations.

######  Proposition 6.9.

Non-caterpillar one-stage trees contain linear relations in their implicit
description.

###### Proof.

Take a vertex $u$ in the non-caterpillar tree $\mathcal{T}$ that has at least
two internal vertices, say $u_{i}$ and $u_{j}$, as its children. Let
$\theta_{i},\theta_{j}$ be the parameters for the transitions from $u$ to
$u_{i}$ and $u_{j}$, respectively. Take the child $u_{ij}$ of $u_{i}$ whose
associated edge label is $\theta_{j}$. Similarly, let $u_{ji}$ be the child of
$u_{j}$ with edge label $\theta_{i}$. Then,
$\varphi_{\mathcal{T}}(p_{[u_{ij}]})=\varphi_{\mathcal{T}}(p_{[u]})\theta_{i}\theta_{j}=\varphi_{\mathcal{T}}(p_{[u_{ji}]})$,
and $p_{[u_{ij}]}-p_{[u_{ji}]}=0$ is in the kernel of $\varphi_{\mathcal{T}}$.
∎

The following result is valid for all staged trees that share a caterpillar
structure and not only for the one-stage tree models. We thus prove it for the
general case.

######  Proposition 6.10.

Caterpillar trees do not contain linear relations in their implicit form.

###### Proof.

Take $\mathcal{C}$ to be a caterpillar tree. Let
$\theta_{t,1},\theta_{t,2},\dots,\theta_{t,k_{t}}$ be the children of internal
vertex at the level $t-1$ of the caterpillar tree. To avoid heavy notation, we
work with the non-homogenised version. Each root-to-leaf path has a
parametrisation $\theta(1)\cdots\theta(t-1)\cdot\theta_{t,j}$, where $1\leq
t\leq d-1$, $1\leq j\leq k_{t}$, and $\theta_{t,j}\neq\theta(t)$. Assume by
contradiction that the linear relationship $\sum_{i\in U}a_{i}\cdot p_{i}=0$,
where $U$ is a subset of leaves in $\mathcal{C}$ and $a_{i}$ are real values,
is in $\ker\,\varphi_{\mathcal{C}}$. Its image under $\varphi_{\mathcal{C}}$
has the form $\sum_{i\in
U}a_{i}\cdot\theta(1)\cdots\theta(t_{i}-1)\cdot\theta_{t_{i},j_{i}}=0,$ where
again $\theta_{t_{i},j_{i}}$ is always different from $\theta(t_{i})$. Let $s$
be the maximum number of edges appearing in all root-to-leaf paths ending at a
vertex in $U$. Take $U_{0}$ to be the non-empty subset of paths of length $s$
in $I$. After dividing by $\theta(1)\cdots\theta(s-1)$ and separating all the
new linear terms afterwards to the left of the equation, we find

$\sum_{i\in U_{0}}a_{i}\cdot\theta_{s,j_{i}}=-\sum_{i\in U\setminus
U_{0}}a_{i}\cdot\theta(s)\cdots\theta(t_{i}-1)\cdot\theta_{t_{i},j_{i}}.$ (32)

In order for the equality Eq. 32 to hold, the right hand-side must be
simplified to a sum of linear forms. However, manipulating with sum-to-one
conditions can at most give the linear term $\theta(s)$, which is different
from any of the terms $\theta_{s,j_{i}}$ to the left of Eq. 32. ∎

##  7 Further directions

Bayesian networks are arguably the most famous class of staged tree models. In
addition to the staged tree representation, they can be visualised by directed
acyclic graphs (DAGs): we refer to [5] for details on this construction. Those
DAGs which are decomposable are also toric [16]. At the time of writing it is
an open question whether all Bayesian networks have toric structure. Here, we
use Theorem 5.4 to show that the non-decomposable Bayesian networks presented
by DAGs in Figure 13, opening the path for possible applications to methods
developed in this paper in proving that all of them have toric structure. The
staged tree representations of the DAGs in Fig. 13 for binary variables are
shown in Fig. 14 but the patterns of these trees are the same for random
variables with an arbitrary number of states. Both staged trees satisfy the
conditions of 5.4 and hence have toric structure. Here, the set of internal
vertices at distance $3$ from the root serve as $v_{1},\dots,v_{m}$ for the
tree corresponding to Fig. 14(a). Vertices at distance $2$ from the root play
this role in the tree in Fig. 14(b).

######  Conjecture 7.1.

All Bayesian networks have toric structure.

There are staged trees which are not covered by 5.4 but can still be proven to
have a toric structure using Theorem 4.2. In fact we saw such a tree already
in Example 4.5. Recall that one requirement in Theorem 4.2 was that the new
variables are mapped to monomials under $\varphi_{\mathcal{T}}$. This in turn
gives the parametrisation of the variety of $\ker\varphi_{\mathcal{T}}$. In
many cases, such as most balanced trees, the ideal $J_{\mathcal{T}}$ is
properly included in $\ker\varphi_{\mathcal{T}}$. So, in general it is not
sufficient to only prove that $J_{\mathcal{T}}$ is binomial. It can of course
happen that $J_{\mathcal{T}}$ is equal to $\ker\varphi_{\mathcal{T}}$ as in
the example below.

(a) Bayesian network number $9$ in Table $1$ of [14].

(b) Bayesian network number $15$ in Table $1$ of [14].

Figure 13: Two non-decomposable DAGs in four random variables, statistically
equivalent to the staged trees in Fig. 14.

(a) A staged tree representing the DAG in Fig. 13(a).

(b) A staged tree representing the DAG in Fig. 13(b).

Figure 14: Each of the subtrees to the left of the dotted lines are balanced,
and all the subtrees to the right of the doted line satisfy the subtree-
inclusion property.

On the other side, both the trees in Fig. 12(c) and Fig. 16 have
$J_{\mathcal{T}}=\ker\varphi_{\mathcal{T}}$ but none of our endeavours found
linear transformations that give the correct number of distinct entries, and
it is as of now unknown whether these models are toric.

An additional simple idea to find toric structure is a computational approach
we present at:

https://mathrepo.mis.mpg.de/StagedTreesWithToricStructures.

This uses the computer algebra softwares Macaulay2 [21] and Mathematica [28]
to either visually check whether a staged tree’s prime ideal has binomial
generators or to randomly create linear transformations doing row and column
operations on stage matrices as in Example LABEL:ex:nastytoric until we end up
with an isomorphism which reveals underlying toric structure. It is beyond the
scope of this paper to develop efficient algorithms for these ideas.

Figure 15: A staged tree with toric structure not covered by Theorem 4.2.

Figure 16: Does this staged tree have toric structure?

As we extend the class of staged tree models with toric structure and do not
find counter-examples, we dare to finalise this paper with the wishful
conjecture that all of these have toric structure.

######  Conjecture 7.2.

All staged tree models have toric structure.

## Acknowledgements

The authors would like to thank Eliana Duarte for rewarding discussions on the
topics of this paper.

## References

  * [1] Lamprini Ananiadi and Eliana Duarte.  Gröbner bases for staged trees.  Alg. Stat., 12:1–20, 2021.
  * [2] David J. Anick.  On the homology of associative algebras.  Trans. Amer. Math. Soc., 296:641–659, 1986.
  * [3] Cristiano Bocci and Luca Chiantini.  An introduction to algebraic statistics with tensors, volume 1.  Springer, 2019.
  * [4] Federico Carli, Manuele Leonelli, Eva Riccomagno, and Gherardo Varando.  The R-package stagedtrees for structural learning of stratified staged trees.  Preprint available from arXiv:2004.06459[stat.ME], 2020\.
  * [5] Rodrigo A. Collazo, Christiane Görgen, and Jim Q. Smith.  Chain Event Graphs.  Computer Science & Data Analysis Series. Chapman & Hall, 2018.
  * [6] David A Cox, John B Little, and Henry K Schenck.  Toric varieties, volume 124.  American Mathematical Soc., 2011.
  * [7] Persi Diaconis, Bernd Sturmfels, et al.  Algebraic algorithms for sampling from conditional distributions.  Annals of statistics, 26(1):363–397, 1998.
  * [8] Eliana Duarte and Christiane Görgen.  Equations defining probability tree models.  J. Symbolic Comput., 99:127–146, 2020.
  * [9] Eliana Duarte, Orlando Marigliano, and Bernd Sturmfels.  Discrete statistical models with rational maximum likelihood estimator.  Bernoulli, 27(1):135–154, 2021.
  * [10] Eliana Duarte and Liam Solus.  Algebraic geometry of discrete interventional models.  Preprint available from arXiv:2012.03593[math.ST], 2020\.
  * [11] Eliana Duarte and Liam Solus.  Representation of context-specific causal models with observational and interventional data.  Preprint available from arXiv:2101.09271[math.ST], 2021\.
  * [12] Viviane Ene and Jürgen Herzog.  Gröbner Bases in Commutative Algebra, volume 130 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2012.
  * [13] Stephen E Fienberg and Alessandro Rinaldo.  Maximum likelihood estimation in log-linear models.  The Annals of Statistics, 40(2):996–1023, 2012.
  * [14] Luis David Garcia, Michael Stillman, and Bernd Sturmfels.  Algebraic geometry of Bayesian networks.  J. Symbolic Comput., 39(3-4):331–355, 2005.
  * [15] Dan Geiger, David Heckerman, Henry King, and Christopher Meek.  Stratified exponential families: graphical models and model selection.  Ann. Statist., 29(2):505 – 529, 2001.
  * [16] Dan Geiger, Christopher Meek, and Bernd Sturmfels.  On the toric algebra of graphical models.  Ann. Statist., 34(3):1463–1492, 2006.
  * [17] Tim Genewein, Tom McGrath, Grégoire Delétang, Vladimir Mikulik, Miljan Martic, Shane Legg, and Pedro A. Ortega.  Algorithms for causal reasoning in probability trees.  Preprint available from arXiv:2106.04416[cs.AI], 2021\.
  * [18] Christiane Görgen, Anna Bigatti, Eva Riccomagno, and Jim Q. Smith.  Discovery of statistical equivalence classes using computer algebra.  Internat. J. Approx. Reason., 95:167–184, 2018.
  * [19] Christiane Görgen, Manuele Leonelli, and Orlando Marigliano.  The curved exponential family of a staged tree.  Preprint available from arXiv:2010.15515[math.ST], 2020\.
  * [20] Christiane Görgen and Jim Q. Smith.  Equivalence classes of staged trees.  Bernoulli, 24(4A):2676–2692, 2018.
  * [21] Daniel R. Grayson and Michael E. Stillman.  Macaulay2, a software system for research in algebraic geometry.  Available at https://faculty.math.illinois.edu/Macaulay2/.
  * [22] Joe Harris.  Algebraic geometry: a first course, volume 133.  Springer Science & Business Media, 2013.
  * [23] Melvin Hochster.  Rings of invariants of tori, Cohen-Macaulay rings generated by monomials, and polytopes.  Ann. of Mathematics, 96:228–235, 1972.
  * [24] Claire Keeble, Peter A. Thwaites, Paul D. Baxter, Stuart Barber, Roger C. Parslow, and Graham R. Law.  Learning through chain event graphs: the role of maternal factors in childhood type I diabetes.  American Journal of Epidemiology, 186(10):1204–1208, 2017.
  * [25] Manuele Leonelli and Gherardo Varando.  Context-specific causal discovery for categorical data using staged trees.  Preprint available from arXiv:2106.04416[stat.ME], 2021\.
  * [26] Giovanni Pistone, Eva Riccomagno, and Henry P. Wynn.  Algebraic statistics, volume 89 of Monographs on Statistics and Applied Probability.  Chapman & Hall/CRC, Boca Raton, FL, 2001.  Computational commutative algebra in statistics.
  * [27] Jim Q. Smith and Paul E. Anderson.  Conditional independence and chain event graphs.  Artificial Intelligence, 172(1):42–68, 2008.
  * [28] Wolfram Research, Inc.  Mathematica, Version 12.2.  Champaign, IL, 2020.