MARKOV RANDOM FIELDS AND ITERATED TORIC FIBRE PRODUCTS

arXiv:1612.06737v2 [math.AC] 7 Feb 2018

JAN DRAISMA AND FLORIAN M. OOSTERHOF

Abstract. We prove that iterated toric fibre products from a finite collection of
toric varieties are defined by binomials of uniformly bounded degree. This implies
that Markov random fields built up from a finite collection of finite graphs have
uniformly bounded Markov degree.

1. Introduction and main results
The notion of toric fibre product of two toric varieties goes back to [Sul07]. It is of
relevance in algebraic statistics since it captures algebraically the Markov random
field on a graph obtained by glueing two graphs along a common subgraph; see
[RS16] and also below. In [Sul07, RS16, RS14] it is proved that under certain conditions, one can explicitly construct a Markov basis for the large Markov random
field from bases for the components. For related results see [Shi12, EKS14, KR14].
However, these conditions are not always satisfied. Nevertheless, in [RS16, Conjecture 56] the hope was raised that when building larger graphs by glueing copies
from a finite collection of graphs along a common subgraph, there might be a
uniform upper bound on the Markov degree of the models thus constructed, independent of how many copies of each graph are used. A special case of this
conjecture was proved in the same paper [RS16, Theorem 54]. We prove the
conjecture in general, and along the way we link it to recent work [SS17] in representation stability. Indeed, an important point we would like to make, apart from
proving said conjecture, is that algebraic statistics is a natural source of problems
in asymptotic algebra, to which ideas from representation stability apply. Our main
theorems are reminiscent of Sam’s recent stabilisation theorems on equations and
higher syzygies for secant varieties of Veronese embeddings [Sam17a, Sam17b].
Markov random fields. Let G = (N, E) be a finite, undirected, simple graph and
for each node j ∈ N let X j be a random variable taking values in the finite set
[d j ] := {1, . . . , d j }. A joint probability distribution on (X j ) j∈N is said to satisfy the
local Markov properties imposed by the graph if for any two non-neighbours j, k ∈ N
the variables X j and Xk are conditionally independent given {Xl | {j, l} ∈ E}.
On the other hand, a joint probability distribution f on the X j is said Q
to factorise
according to G if for each maximal clique C of G and configuration α ∈ j∈C [d j ] of
C
the random variables labelled by
Q C there exists an interaction parameter θα such
that for each configuration β ∈ j∈N [d j ] of all random variables of G:
Y
f (β) =
θCβ|C
C∈mcl(G)

where mcl(G) is the set of maximal cliques of G, and β|C is the restriction of β to C.
1

2

JAN DRAISMA AND FLORIAN M. OOSTERHOF

These two notions are connected by the Hammersley-Clifford theorem, which says
that a positive joint probability distribution on G factorises according to G if and
only if it satisfies the Markov properties; see [HC71] or [Lau98, Theorem 3.9].
The set of all positive joint probability distributions on G that satisfy the Markov
properties is therefore a subset of the image of the following map:


 Y

Q
Q
Q


[d
]
[d
]
C
C
ϕG : C C∈mcl(G) j∈C j → C j∈N j ,
(θα )C,α 7→ 
θβ|C 


C∈mcl(G)

β

It is the ideal IG of polynomials vanishing on im ϕG that is of interest in algebraic
statistics. Since the components of ϕG are monomials, IG is generated by finitely
many
binomials (differences of two monomials) in the standard coordinates on
Q
C j∈N [d j ] , and any finite generating set of binomials can be used to set up a Markov
chain for testing whether given observations of the variables X j are compatible
with the assumption that their joint distribution factorises according to the graph
G [DS98]. The zero locus of IG is often called the graphical model of G.
Now suppose we have graphs G1 , . . . , Gs with node sets N1 , . . . , Ns , that Ni ∩ Nk
equals a fixed set N0 for all i , k in [s], and that the graphSinduced on N0 by each
Gi is equal to a fixed graph H. Moreover, for each j ∈ i Ni fix a number d j of
states. We can then glue copies of the Gi along their common subgraph H, by
which we mean first taking disjoint copies of the Gi and then identifying the nodes
labelled by a fixed j ∈ N0 across all copies. For a1 , . . . , aP
s ∈ Z≥0 , we denote
P the
graph obtained by glueing ai copies of graph Gi , i ∈ [s] by aH1 G1 +H · · · +H aHs Gs :
H
P2

H

H
+H

P1

H

=

Theorem 1. Let G1 , . . . , Gs be graphs with a common subgraph H and a number of states
associated to each node. Then there exists a uniform
bound D ∈PZ≥0 such that for all
P
multiplicities a1 , . . . , as , the ideal IG of G = aH1 G1 +H · · · +H aHs Gs is generated by
binomials of degree at most D.
Our proof shows that one needs only finitely many combinatorial types of binomials, independent of a1 , . . . , as , to generate IG . This result is similar in flavour
to the Independent Set Theorem from [HS12], where the graph is fixed but the d j
vary. Interestingly, the underlying categories responsible for these two stabilisation
phenomena are opposite to each other; see Remark 23.
Example 2. In [RS14] it is proved that the ideal IG for the complete bipartite graph
G = K3,N , with two states for each of the random variables, is generated in degree
at most 12 for all N. The graph G is obtained by glueing N copies of K3,1 along their
common subgraph consisting of 3 nodes without any edges.
We derive Theorem 1 from a general stabilisation result on toric fibre products, which
we introduce next.

MARKOV RANDOM FIELDS AND ITERATED TORIC FIBRE PRODUCTS

3

Toric fibre products. Fix a ground field K, let r be a natural number, and let
U1 , . . . , Ur , V1 , . . . , Vr be finite-dimensional vector spaces over K.
Define a bilinear operation
Y
Y
Y
(1)
Uj ×
Vj →
(U j ⊗ V j ),
j

j

(u, v) 7→ u ∗ v := (u1 ⊗ v1 , . . . , ur ⊗ vr ).

j

Definition 3. The toric fibre product X ∗ Y of Zariski-closed subsets X ⊆
Q
Y ⊆ j V j equals the Zariski-closure of the set {u ∗ v | u ∈ X, v ∈ Y}.

Q

j

U j and
♣

Remark 4. In [Sul07], the toric fibre product is defined at the level of ideals: if
j
j
(xi )i are coordinate functions on U j and (yk )k are coordinate functions on V j , then
j

j

j

(zi,k := xi ⊗ yk )i,k are coordinate functions on U j ⊗ V j . The ring homomorphism of
coordinate rings




Y 
Y

Y
j
j
j




K[(zi,k ) j,i,k ] = K  (U j ⊗ V j ) → K 
Uj ×
V j  = K[(xi ) j,i , (yk ) j,k ]




j

j

j

j

j

j

dual to (1) sends zi,k to xi ·yk . If we compose this homomorphism with the projection
modulo the ideal of X × Y, then the kernel of the composition is precisely the toric
fibre product of the ideals of X and Y as introduced in [Sul07]. In that paper,
multigradings play a crucial role for computing toric fibre products of ideals, but
do not affect the definition of toric fibre products.
♣
The product ∗ is associative and commutative up to reordering tensor factors. We
can iterate this construction and form products like X∗2 ∗ Y ∗ Z∗3 , where Z also lives
Q
in a product of r vector spaces W j . This variety lives in j (U⊗2
) ⊗ V j ⊗ (W ⊗3
).
j
j
We will not be taking toric fibre products of general varieties, but rather Hadamardstable ones. For this, we have to choose coordinates on each U j , so that U j = Kd j .
Definition 5. On Kd the Hadamard product is defined as (a1 , . . . , ad ) (b1 , . . . , bd ) =
(a1 b1 , . . . , adQ
bd ). On U := U1 ×· · ·×Ur , where U j = Kd j , it is defined component-wise.
A set X ⊆ j U j is called Hadamard-stable if X contains the all-one vector 1U (the
unit element of ) and if moreover x z ∈ X for all x, z ∈ X.
♣
Remark 6. By [ES96, Remark after Proposition 2.3], X is Hadamard-stable if and
only if its ideal is generated by differences of two monomials.
P
In particular, the Zariski-closure in U of a subtorus of the j d j -dimensional torus
Q
dj
j (K \ {0}) is Hadamard-stable. These are the toric varieties from the abstract.
d0

Suppose that we
V j = K j and a corresponding Hadamard
Q also fix
Q identifications
Q
multiplication j V j × j V j → j V j . Equipping the spaces U j ⊗ V j with the natural coordinates and corresponding Hadamard multiplication, the two operations
∗ (v v0 ) = (u ∗Q
v) (u0 ∗ v0 ) as well as 1U j ⊗V j = 1U j ⊗ 1V j .
just defined satisfy (u u0 )Q
Consequently, if both X ⊆ j U j and Y ⊆ j V j are Zariski-closed and Hadamardstable, then so is their toric fibre product X ∗ Y. We can now formulate our second
main result.

4

JAN DRAISMA AND FLORIAN M. OOSTERHOF

Theorem 7. Let s, r ∈ Z≥0 . Q
For each i ∈ [s] and j ∈ [r] let di j ∈ Z≥0 and set Vi j := Kdi j .
For each i ∈ [s], let Xi ⊆
j Vi j be a Hadamard-stable Zariski-closed subset. Then
there exists a uniform bound
D
∈ Z≥0 such that for any exponents a1 , . . . , as the ideal of
Q Ns
⊗ai
X1∗a1 ∗ · · · ∗ Xs∗as ⊆ rj=1
V
is generated by polynomials of degree at most D.
i=1 i j
Remark 8. A straightforward generalisation of this theorem also holds, where
each Xi is a closed sub-scheme given by some ideal Ji in the coordinate ring of
Q
j Vi j . Hadamard-stable then says that that the pull-back of Ji under the Hadamard
product lies in the ideal of Xi × Xi , and the toric fibre product is as in Remark 4.
Since this generality would slightly obscure our arguments, we have decided to
present explicitly the version with Zariski-closed subsets—see also Remark 22.
Also, the theorem remains valid if we remove the condition that the Xi contain the
all-one vector, but require only that they be closed under Hadamard-multiplication;
see Remark 21.
♣
Organisation of this paper. The remainder of this paper is organised as follows.
In Section 2 we introduce the categories of (affine) Fin-varieties and, dually, Finop algebras. The point is that, as we will see in Section 4, the iterated toric fibre
products together form such a Fin-variety (or rather a Fins -variety, where Fins is
the product category of s copies of Fin).
Indeed, they sit naturally in a Cartesian product of copies of the Fin-variety of
rank-one tensors, which, as we prove in Section 3, is Noetherian (Theorem 12).
This Noetherianity result is of a similar flavour as the recent result from [SS17]
(see also [DK14, Proposition 7.5] which follows the same proof strategy) that any
finitely generated Finop -module is Noetherian; this result played a crucial role in a
proof of the Artinian conjecture. However, our Noetherianity result concerns certain
Finop -algebras rather than modules, and is more complicated. Finally, in Section 4
we first prove Theorem 7 and then derive Theorem 1 as a corollary.
Acknowledgements. Both authors are (partially) supported by Draisma’s Vici
grant Stabilisation in Algebra and Geometry from the Netherlands Organisation for
Scientific Research (NWO). The current paper is partly based on the second author’s Master’s thesis at Eindhoven University of Technology; see [Oos16]. We
thank Johannes Rauh and Seth Sullivant for fruitful discussions at Prague Stochastics, August 2014.
2. Affine Fin-varieties and Finop -algebras
The category Fin has as objects all finite sets and as morphisms all maps. Its
opposite category is denoted Finop . When C is another category whose objects are
called somethings, then a Fin-something is a covariant functor from Fin to C and a
Finop -something is a contravariant functor from Fin to C. The C-homomorphism
associated to a Fin-morphism π is denoted π∗ (the push-forward of π) in the covariant
case and π∗ (the pull-back of π) in the contravariant case.
More generally, we can replace Fin by any category D. The D-somethings themselves form a category, in which morphisms are natural transformations. In our
paper, D is always closely related to Fin or to Fins , the s-fold product of Fin.
Here are three instances of Fin or Finop -somethings crucial to our paper.

MARKOV RANDOM FIELDS AND ITERATED TORIC FIBRE PRODUCTS

5

Example 9. Fix n ∈ Z≥0 . Then the functor S 7→ [n]S is a Finop -set, which to
π ∈ HomFin (S, T) associates the map π∗ : [n]T → [n]S , α 7→ απ, the composition of
α and π.
Building on this example, the functor An : S 7→ K[xα | α ∈ [n]S ], a polynomial
ring in variables labelled by [n]S , is a Finop -K-algebra, which associates to π the
K-algebra homomorphism π∗ : A(T) → A(S), xα 7→ xαπ .
Third, we define an affine Fin-K-vector space Qn by Qn : S 7→ (Kn )⊗S , the space of
n × · · · × n-tensors with factors labelled by S, which sends π ∈ HomFin (S, T) to the
linear morphism π∗ : (Kn )⊗S → (Kn )⊗T determined by


π∗ : ⊗i∈S vi 7→ ⊗ j∈T
i∈π−1 ( j) vi ,
where
is the Hadamard product in Kn . We follow the natural convention that
an empty Hadamard product equals the all-one vector 1 ∈ Kn ; in particular, this
holds in the previous formula for all j ∈ T that are not in the image of π.
The ring An and the space Qn are related as follows: Qn (S) has a basis consisting
of vectors eα := ⊗i∈S eαi , α ∈ [n]S , where e1 , . . . , en is the standard basis of Kn ;
An (S) is the coordinate ring of Qn (S) generated by the dual basis (xα )α∈[n]S ; and
for π ∈ HomFin (S, T) the pullback π∗ : An (T) → An (S) is the homomorphism of
K-algebras dual to the linear map π∗ : Qn (S) → Qn (T). Indeed, this is verified by
the following computation for α ∈ [n]T :
Y
Y



xα (π∗ ⊗i∈S vi ) = xα (⊗ j∈T
=
(vi )απ(i) = π∗ (xα )(⊗i∈S vi ).
i∈π−1 ( j) vi
i∈π−1 ( j) vi ) =
j∈T

αj

i∈S

This is used in Section 3. ♣
In general, by algebra we shall mean an associative, commutative K-algebra with
1, and homomorphisms are required to preserve 1. So a Finop -algebra B assigns to
each finite set S an algebra and to each map π : S → T an algebra homomorphism
π∗ : B(T) → B(S). An ideal in B is a Finop -subset I of B (i.e., I(S) is a subset of B(S) for
each finite set S and π∗ maps I(T) into I(S)) such that each I(S) is an ideal in B(S);
then S 7→ B(S)/I(S) is again a Finop -algebra, the quotient B/I of B by I.
Given a Finop -algebra B, finite sets S j for j in some index set J, and an element
b j ∈ B(S j ) for each j, there is a unique smallest ideal I in B such that each I(S j )
contains b j . This ideal is constructed as:


I(S) = π∗ (b j ) j ∈ J, π ∈ Hom(S, S j )
This is the ideal generated by the b j . A Finop -algebra is called Noetherian if each
ideal I in it is generated by finitely many elements in various I(S j ), i.e., J can be
taken finite.
Example 10. The Finop -algebra A1 is Noetherian. Indeed, A1 (S) is the polynomial
ring K[t] in a single variable t for all S, and the homomorphism A1 (T) → A1 (S)
is the identity K[t] → K[t]. So Noetherianity follows from Noetherianity of the
algebra K[t].
For n ≥ 2 the Finop -algebra An is not Noetherian. For instance, consider the
monomials
u2 := x21 x12 ∈ An ([2]), u3 := x211 x121 x112 ∈ An ([3]), u4 := x2111 x1211 x1121 x1112 ∈ An ([4]),

6

JAN DRAISMA AND FLORIAN M. OOSTERHOF

and so on. For any map π : [k] → [l] with k > l, by the pigeon hole principle
there are two indices i, j ∈ [k] such that π(i) = π( j) =: m ∈ [l]. Then π∗ x1···121···1 ,
where the 2 is in the m-th position, is a variable with at least two indices equal to 2.
Since uk contains no such variable, π∗ ul does not divide uk . So u2 , u3 , . . . generates
a non-finitely generated monomial Finop -ideal in An . (On the other hand, for each
d the piece of An of homogeneous polynomials of degree at most d is Noetherian
as a Finop -module, see [DK14, Proposition 7.5].)
♣
We shall see in the following section that certain interesting quotients of each An
are Noetherian.
3. Rank-one tensors form a Noetherian Fin-variety
Let Q≤1
n (S) be the variety of rank-one tensors, i.e., those of the form ⊗i∈S vi for vectors
vi ∈ Kn . We claim that this defines a Zariski-closed Fin-subvariety Q≤1
n of Qn .
For this, we must verify that for a map π : S → T the map Qn (S) → Qn (T) dual to
≤1
the algebra homomorphism An (T) → An (S) sends Q≤1
n (S) into Qn (T). And indeed,
in Example 9 we have seen that this map sends


⊗i∈S vi 7→ ⊗ j∈T
i∈π−1 ( j) vi .
It is well known that (if K is infinite) the ideal in An (S) of Q≤1
n (S) equals the ideal
In (S) generated by all binomials constructed as follows. Partition S into two parts
S1 , S2 , let αi , βi ∈ [n]Si and write α1 ||α2 for the element of [n]S which equals αi on Si .
Then we have the binomial
(2)

xα1 ||α2 xβ1 ||β2 − xα1 ||β2 xβ1 ||α2 ∈ In (S),

and In (S) is the ideal generated by these for all partitions and all α1 , α2 , β1 , β2 . The
functor S 7→ In (S) is an ideal in the Finop -algebra An ; for infinite K this follows from
the computation above, and for arbitrary K it follows since the binomials above are
mapped to binomials by pull-backs of maps T → S in Fin. Moreover, In is finitely
generated (see also [DK14, Lemma 7.4]):
Lemma 11. The ideal In in the Finop -algebra An is finitely generated.
Proof. In the determinantal equation (2), if there exist distinct j, l ∈ S1 such that
α1 ( j) = α2 (l) and β1 ( j) = β2 (l), then the equation comes from an equation in In (S\{j})
via the map S → S \ {j} that is the identity on S \ {j} and maps j → l. By the pigeon
hole principle this happens when |S1 | > n2 . Similarly for |S2 | > n2 . Hence In is
certainly generated by In ([2n2 − 1]).

The main result in this section is the following.
Theorem 12. For each n ∈ Z≥0 the coordinate ring An /In of the Fin-variety Q≤1
n of
rank-one tensors is a Noetherian Finop -algebra.
Our proof follows the general technique from [SS17], namely, to pass to a suitable
category close to Fin that allows for a Gröbner basis argument. However, the
relevant well-partial-orderedness proved below is new and quite subtle. We use
the category OS from [SS17] (also implicit in [DK14, Section 7]) defined as follows.

MARKOV RANDOM FIELDS AND ITERATED TORIC FIBRE PRODUCTS

7

Definition 13. The objects of the category OS (“ordered-surjective”) are all finite
sets equipped with a linear order and the morphisms π : S → T are all surjective
maps with the additional property that the function T → S, j 7→ min π−1 ( j) is
strictly increasing.
♣
Any Fin-algebra is also an OS-algebra, and OS-Noetherianity implies Fin-Noetherianity. So to prove Theorem 12 we set out to prove the stronger statement that
An /In is, in fact, OS-Noetherian.
We get a more concrete grip on the K-algebra An /In through the following construction. Let Mn denote the (Abelian) Finop -monoid defined by


n
n


X
X




[n]×S
Mn (S) := 
α ∈ Z≥0 | ∀j, l ∈ S :
αi j =
αil 
,




i=1

i=1

in which the multiplication is given by addition, and where the pull-back of a map
π : S → T is the map π∗ : Mn (T) → Mn (S) sending (αi j )i∈[n],j∈T to (αiπ(j) )i∈[n],j∈S .
So elements of Mn (S) are matrices with nonnegative integral entries and constant
column sum. Let KMn denote the Fin-algebra sending S to the monoid K-algebra
KMn (S). The following proposition is a reformulation of a well-known fact.
Proposition 14. The Finop -algebra An /In is isomorphic to the Finop -algebra KMn (and
the same is true when both are regarded as OSop -algebras).
Proof. For each finite set S, the K-algebra homomorphism ΦS : An (S) → KMn (S)
that sends xα , α ∈ [n]S to the [n] × S matrix in Mn (S) with a 1 at the positions
(α j , j), j ∈ S and zeroes elsewhere is surjective and has as kernel the ideal In (S).
Moreover, if π : S → T is a morphism in Fin, then we have ΦT π∗ = π∗ ΦS , i.e., the
(ΦS )S define a natural transformation.

Choose any monomial order > on Zn≥0 , i.e., a well-order such that a > b implies
a + c > b + c for every a, b, c ∈ Zn≥0 . Then for each object S in OS we define a
linear order > on Mn (S), as follows: α > β if α , β and the smallest j ∈ S with
α.,j , β., j (i.e., the j-th column of α is not equal to that of β) satisfies α.,j > β., j in
the chosen monomial order on Zn≥0 . A straightforward verification shows that this
is a monomial order on Mn (S) (we call the elements of Mn (S) monomials, even
though KMn (S) is not a polynomial ring). Moreover, for various S, these orders are
interrelated as follows.
Lemma 15. For any π ∈ HomOS (S, T) and α, β ∈ Mn (T), we have α > β ⇒ π∗ α > π∗ β.
Proof. If j ∈ T is the smallest column index where α and β differ, then α0 := π∗ α
and β0 := π∗ β differ in column l := min π−1 ( j), where they equal α.,j and β. j ,
respectively, and the former is larger than the latter. Furthermore, if l0 is the
smallest position where α0 , β0 differ, then α.,π(l0 ) , β.,π(l0 ) and hence π(l0 ) ≥ j and
hence l0 = min π−1 (π(l0 )) ≥ min π−1 ( j) = l. Hence in fact l = l0 and π∗ α > π∗ β.

In addition to the well-order ≤ on each individual Mn (S), we also need the following
partial order | on the union of all of them.

8

JAN DRAISMA AND FLORIAN M. OOSTERHOF

Definition 16. Let S, T be objects in OS. We say that α ∈ Mn (T) divides β ∈ Mn (S) if
there exist a π ∈ HomOS (S, T) and a γ ∈ Mn (S) such that β = γ + π∗ α. In this case,
we write α|β.
♣
The key combinatorial property of the relation just defined is the following.
Proposition 17. The relation | is a well-quasi-order, that is, for any sequence α(1) ∈
Mn (S1 ), α(2) ∈ Mn (S2 ), . . . there exist i < j such that α(i) |α( j) .
Proof. First, to each α ∈ Mn (S) we associate the monomial ideal P(α) in the polynomial ring R := K[z1 , . . . , zn ] (here K is but a place holder) generated by the
monomials zα.,j , j ∈ S. The crucial fact that we will use about monomial ideals
in R is that in any sequence P1 , P2 , . . . of such ideals there exist i < j such that
Pi ⊇ P j —in other words, monomial ideals are well-quasi-ordered with respect to
reverse inclusion [Mac01].
To prove the proposition, suppose, on the contrary, that there exists a sequence as
above with α(i) 6 | α( j) for all i < j. Such a sequence is called bad. Then by basic
properties of well-quasi-orders, some bad sequence exists in which moreover
(3)

P(α(1) ) ⊇ P(α(2) ) ⊇ . . .

Among all bad sequences with this additional property choose one in which, for each
j = 1, 2, . . . , the cardinality |S j | is minimal among all bad sequences starting with
α(1) , . . . , α(j−1) .
Write α(j) = (γ( j) |β(j) ), where β(j) ∈ Zn≥0 is the last column (the one labelled by the
largest element of S j ), and γ( j) is the remainder. By Dickson’s lemma, there exists a
subsequence j1 < j2 < . . . such that β(j1 ) , β( j2 ) , . . . increase weakly in the coordinatewise ordering on Zn≥0 . By restricting to a further subsequence, we may moreover
assume that also
(4)

P(γ(j1 ) ) ⊇ P(γ( j2 ) ) ⊇ . . .

Then consider the new sequence
α(1) , . . . , α( j1 −1) , γ(j1 ) , γ( j2 ) , . . .
By (4) and (3), and since P(α( j) ) ⊇ P(γ(j) ), this sequence also satisfies (3). We claim
that, furthermore, it is bad.
Suppose, for instance, that γ(j1 ) |γ(j2 ) . Set ai := max S ji for i = 1, 2. Then there exists
a π ∈ HomOS (S j2 \ {a2 }, S j1 \ {a1 }) such that γ(j2 ) − π∗ γ( j1 ) ∈ Mn (S j2 \ {a2 }). But then
extend π to an element π of HomOS (S j2 , S j1 ) by setting π(a2 ) := a1 ; since β(j1 ) is
coordinate-wise smaller than β( j2 ) we find that α( j2 ) − π∗ α( j1 ) ∈ Mn (S j2 ), so α( j1 ) |α( j2 ) ,
in contradiction to the badness of the original sequence.
On the other hand, suppose for instance that α(1) |γ( j2 ) and write a2 := max S j2 . Then
there exists a π ∈ HomOS (S j2 \ {a2 }, S1 ) such that γ( j2 ) − π∗ (α(1) ) ∈ Mn (S j2 \ {a2 }).
Now, and this is why we required that (3) holds, since P(α( j2 ) ) ⊆ P(α(1) ), there exists an
element s ∈ S1 such that the column β( j2 ) is coordinatewise at least as large as the
s-th column of α(1) . Extend π to an element of HomOS (S j2 , S1 ) by setting π(a2 ) = s.
Since a2 is the maximal element of S j2 , this does not destroy the property that the

MARKOV RANDOM FIELDS AND ITERATED TORIC FIBRE PRODUCTS

9

function min π−1 (.) be increasing in its argument. Moreover, this π has the property
that α(j2 ) − π∗ α(1) ∈ Mn (S j2 ), again a contradiction.
Since we have found a bad sequence satisfying (3) but with strictly smaller underlying set at the j1 -st position, we have arrived at a contradiction.

Next we use a Gröbner basis argument.
Proof of Theorem 12. We prove the stronger statement that KMn is Noetherian as
an OS-algebra. Let P be any ideal in An /In = KMn . For each object S in OS, let
L(S) ⊆ Mn (S) denote the set of leading terms of nonzero elements of P(S) relative to
the ordering >. Proposition 17 implies that there exists a finite collection S1 , . . . , SN
and α( j) ∈ L(S j ) such that each element of each L(S) is divisible by some α( j) .
Correspondingly, there exist elements f j ∈ P(S j ) with leading monomial α( j) and
leading coefficient 1. To see that the f j generate P, suppose that there exists an S
such that P(S) is not contained in the ideal generated by the f j , and let g ∈ P(S)
have minimal leading term β among all elements of P(S) not in the ideal generated
by the f j ; without loss of generality g has leading coefficient 1. By construction,
there exists some j and some π ∈ HomOS (S, S j ) such that β − π∗ α(j) ∈ Mn (S). But
now, by Lemma 15, we find that the leading monomial of π∗ f j equals π∗ α( j) , hence
subtracting a monomial times π∗ f j from g we obtain an element of P(S) with smaller
leading monomial that is not in the ideal generated by the f j —a contradiction. 
Below, we need the following generalisation of Theorem 12.
Theorem 18. For any n1 , . . . , nr ∈ (Z)≥0 the Fin-algebra (or OS-algebra) (An1 /In1 ) ⊗
· · · ⊗ (An /In1 ) is Noetherian.
Proof. This algebra is isomorphic to B := K(Mn1 × · · · × Mnr ). There is a natural
embedding ι : Mn1 × · · · × Mnr → Mn1 +...+ns =: Mn by forming a block matrix; its
image consists of block matrices with constant partial column sums. And while a
subalgebra of a Noetherian algebra is not necessarily Noetherian, this is true in the
current setting.
The crucial point is that if αi ∈ (Mn1 × · · · × Mnr )(Si ) for i = 1, 2, then a priori ι(α1 )|ι(α2 )
only means that ι(α2 ) − π∗ ι(α1 ) ∈ Mn (S2 ); but since both summands have constant
partial column sums, so does their difference, so in fact, the difference lies in the
image of ι. With this observation, the proof above for the case where r = 1 goes
through unaltered for arbitrary r.

Remark 19. Similar arguments for passing to sub-algebras are also used in [HS12]
and [Dra10].
♣
4. Proofs of the main results
In this section we prove Theorems 1 and 7.
Toric fibre products. To prove Theorem 7, we work with a product of s copies of
the category Fin; one for each of the varieties Xi whose iterated fibre products are
under consideration. Let s, r ∈ Z≥0 . For each i ∈ [s] and j ∈ [r] let di j ∈ Z≥0 and set

10

JAN DRAISMA AND FLORIAN M. OOSTERHOF

Vi j := Kdi j . Consider the Fins -variety V that assigns to an s-tuple S = (S1 , . . . , Ss )
the product
r O
s
Y
i
Vi⊗S
j
j=1

i=1

and to a morphism π = (π1 , . . . , πs ) : S → T := (T1 , . . . , Ts ) in Fins the linear map
V(S) → V(T) determined by





,
(5)
⊗i ⊗k∈Si vi jk
7→ ⊗i ⊗l∈Ti
k∈π−1 (l) vi jk
j∈[r]

j∈[r]

i

where the Hadamard product is the one on Vi j . Let Q (S) be the Zariski-closed
subset of V(S) consisting of r-tuples of tensors of rank at most one; thus Q≤1 is a
Fins -subvariety of V.
Qr
For each i ∈ [s] let Xi ⊆
j=1 Vi j be a Hadamard-stable Zariski-closed subset.
≤1

Then for any tuple S = (S1 , . . . , Ss ) in Fins the variety X(S) := X1∗S1 ∗ · · · ∗ Xs∗Ss is a
Zariski-closed subset of V(S).

Lemma 20. The association S 7→ X(S) defines a Fins -closed subvariety of Q≤1 .
Proof. From the definition of ∗ in (1) it is clear that the elements of X(S) are r-tuples
of tensors of rank at most 1. Furthermore, for a morphism S → T in Fins the linear
map V(S) → V(T) from (5) sends X(S) into X(T)—here we use that if (vi, j,k ) j∈[r] ∈ Xi
for each k ∈ π−1 (l), then also ( k∈π−1 (l) vi jk ) j∈[r] ∈ Xi since Xi is Hadamard-stable. 
Now Theorem 7 follows once we know that the coordinate ring of Q≤1 is a Noetherian (Fins )op -algebra. For s = 1 and r = 1 this is Theorem 12 with n equal to d11 .
For s = 1 and general r, this is Theorem 18 with n j equal to d1j .
For r = 1 and general s, Theorem 7 follows from a Fins -analogue of Theorem 12,
which is proved as follows. The coordinate ring of Q≤1 (S1 , . . . , Ss ) is the subring
of K(Md11 (S1 ) × · · · × Mds1 (Ss )) spanned by the monomials corresponding to s-tuples
of matrices with the same constant column sum. Using Proposition 17 and the
fact that a finite product of well-quasi-ordered sets is well-quasi-ordered one finds
that the natural Fins -analogue on Md11 × · · · × Mds1 of the division relation | is a
well-quasi-order; and this implies, once again, that the coordinate ring of Q≤1 is a
Noetherian (OSs )op -algebra.
Finally, for general s and general r, the result follows as in the proof of Theorem 18.
This proves the Theorem 7 in full generality.

Remark 21. The only place where we used that the Xi contain the all-one vector is
in the proof of Lemma 20 when π−1 (l) happens to be empty. If we do not require
this, then the conclusion of Theorem 7 still holds, since one can work directly with
the category OSs in which morphisms π are surjective.
Remark 22. If we replace the Xi by Hadamard-stable closed subschemes rather
than subvarieties, then S 7→ X(S) is still a Fins -closed subscheme of Q≤1 , and since
the coordinate ring of the latter is Noetherian, the proof goes through unaltered.

MARKOV RANDOM FIELDS AND ITERATED TORIC FIBRE PRODUCTS

11

Remark 23. In the Independent Set Theorem from [HS12], the graph G = (N, E)
is fixed but the state space sizes d j grow unboundedly for j in an independent set
T ⊆ N and are fixed for j < T. In this case, given a T-tuple of maps (π j : S j → P j ) j∈T
of finite sets, where S j is thought of as the state space of j ∈ T in the smaller model
and P j as the state space in the larger model, we obtain a natural map from the
larger model into the smaller model. Hence then the graphical model is naturally
a (Finop )T -variety and its coordinate ring is a FinT -algebra. Note the reversal of the
roles of these two categories compared to Lemma 20.
Markov random fields. Given a finite (undirected, simple) graph G = (N, E) with a
number d j of states attached to each node j ∈ N, the graphical model is XG := im ϕG ,
where ϕG is the parameterisation


 Y

Q
Q
Q


(θCα )C,α 7→ 
ϕG : C C∈mcl(G) j∈C [d j ] → C j∈N [d j ] ,
θCβ|C  .


C∈mcl(G)

β

Lemma 24. For any finite graph G, the graphical model XG is Hadamard-closed.
Proof. The parameterisation ϕ sends the all-one vector in the domain to the all-one
vector 1 in the target space, so 1 ∈ im ϕ. Moreover, if θ, θ0 are two parameter
vectors, then ϕ(θ θ0 ) = ϕ(θ) ϕ(θ0 ), so im ϕ is Hadamard-closed. Then so is its
closure.

Following [Sul07], we relate graph glueing to toric fibre products. We are given
finite graphs G1 , . . . , Gs with node sets N1 , . . . , Ns such that Ni ∩ Nk = N0 for all i , k
in [s]
S and such that each Gi induces the same graph H on N0 . Moreover, for each
j ∈ i Ni we fix a number d j of states.
Q
Q
For each β0 ∈ j∈N0 [d j ] and each i ∈ [s] set Vi,β0 := C j∈Ni \N0 [d j ] , which we interpret
as the ambient space of the part of the probability table of the variables X j , j ∈ Ni
where we have fixed the states of the variables in N0 to β0 —up to scaling, these are
the conditional joint probabilities
for the X j , j ∈ Ni \ N0 given that the X j , j ∈ N0 are
Q
in joint state β0 . For β ∈ j∈Ni [d j ] write β = β0 ||β0 where β0 , β0 are the restrictions of
β to N0 and Ni \N0 , respectively. For each maximal clique
Q C in Gi define C0 = C∩N0
and C0 = C \ N0 . Correspondingly, decompose α ∈ j∈C [d j ] as α = α0 ||α0 , where
α0 , α0 are the restrictions of α to C0 and C0 , respectively.
Then the graphical model XGi := im ϕGi is the closure of the image of the parameterisation

 
 Y
Y
 
Q
Q



θC(β0 |C ) || (β0 |C0 )   .
ϕi : C C∈mcl(Gi ) j∈C [d j ] →
Vi,β0 ,
(θCα )C,α 7→ 
 
0
Q
C∈mcl(G)
β0 ∈

j∈N0 [d j ]

Q

β0 β0

Setting r := j∈N0 d j , we are exactly in the setting of the previous sections: for each
i, k ∈ [s], we have the bilinear map
Y
Y
Y
∗:
Vi,β0 ×
Vk,β0 →
(Vi,β0 ⊗ Vk,β0 ),
((vi,β0 )β0 , (vk,β0 )β0 ) 7→ (vi,β0 ⊗ vk,β0 )β0 ,
β0

β0

β0

and we can takeQiterated products of this type. The space on the right is naturally
isomorphic to C j∈N1 ∪N2 [d j ] , the space of probability tables for the joint distribution

12

JAN DRAISMA AND FLORIAN M. OOSTERHOF

of the variables labelled by the vertices in the glued graph Gi +H Gk . Under this
identification we have the following.
P
P
Proposition 25. For G := aH1 G1 +H · · · +H aHs Gs we have XG = XG∗a11 ∗ · · · ∗ XG∗ass .
Proof. It suffices to prove this for the gluing of two graphs. Note that a clique in
G := G1 +H G2 is contained entirely in either G1 or G2 , or in both but then already
in H. Let θ, η be a parameter vectors in the domains of ϕG1 , ϕG2 , respectively. Then
ϕG1 (θ) ∗ ϕG2 (η)


 Y



= 
θC(β0 |C ) || (β0 |C0 ) 

0

C∈mcl(G1 )


 Y

= 


C∈mcl(G1 )


 Y

= 


C∈mcl(G1 )





 Y




C
 ∗ 
η
0| 0 )
)
||
(β
(β
|


0 C0
C 

C∈mcl(G )

β0 β0

Q
β0 ∈ j∈N1 \N0 [d j ]

Y

θC(β0 |C

·

) || (β0 |C0 )
0

C∈mcl(G2 )



 Y



C
= 
µ(β0 |C ) || (β0 |C0 ) 

0

C∈mcl(G)

2




θC(β0 |C ) || (β0 |C0 ) 

0


 Y

⊗ 


β0 β0




ηC(β0 |C ) || (β0 |C0 ) 

0




ηC(β0 |C ) || (β0 |C0 ) 

0

Q
β0 ∈ j∈(N1 ∪N2 )\N0 [d j ]

Q

C∈mcl(G2 )







Q
β0 ∈ j∈N2 \N0 [d j ]

Q
β0 ∈ j∈(N1 ∪N2 )\N0 [d j ]




 = ϕG (µ),
















β0

β0

β0

where, for C ∈ mcl(G) and α ∈ j∈C [d j ], the parameter µCα is defined as


θCα
if C ⊆ N1 and C * N0 ,




C
C
µα := 
ηα
if C ⊆ N2 and C * N0 , and



θC ηC if C ⊆ N0 .
α α
This computation proves that XG1 ∗ XG2 ⊆ XG . Conversely, given any parameter
vector µ for G, we can let θ be the restriction of µ to maximal cliques of the first
and third type above, and set ηCα equal to µCα if C is of the second type above and
equal to 1 if it is of the third type. This yields the opposite inclusion.

Proof of Theorem 1. By Proposition 25, the ideal IG is the ideal of the iterated toric
fibre product XG∗a11 ∗ · · · ∗ XG∗ass . By Lemma 24, each of the varieties XGi is Hadamard
closed. Hence Theorem 7 applies, and IG is generated by polynomials of degree
less than some D, which is independent of a1 , . . . , as . Then it is also generated by
the binomials of at most degree D.

References
[DK14]
[Dra10]
[DS98]

Jan Draisma and Jochen Kuttler. Bounded-rank tensors are defined in bounded degree. Duke
Math. J., 163(1):35–63, 2014.
Jan Draisma. Finiteness for the k-factor model and chirality varieties. Adv. Math., 223:243–256,
2010.
Persi Diaconis and Bernd Sturmfels. Algebraic algorithms for sampling from conditional
distributions. Ann. Stat., 26(1):363–397, 1998.

MARKOV RANDOM FIELDS AND ITERATED TORIC FIBRE PRODUCTS

13

[EKS14]

Alexander Engström, Thomas Kahle, and Seth Sullivant. Multigraded commutative algebra
of graph decompositions. J. Algebr. Comb., 39(2):335–372, 2014.
[ES96]
David Eisenbud and Bernd Sturmfels. Binomial ideals. Duke Math. J., 84(1):1–45, 1996.
[HC71] J.M. Hammersley and P. Clifford. Markov fields on finite graphs and lattices. Unpublished,
http://www.statslab.cam.ac.uk/˜grg/books/hammfest/hamm-cliff.pdf, 1971.
[HS12]
Christopher J. Hillar and Seth Sullivant. Finite Gröbner bases in infinite dimensional polynomial rings and applications. Adv. Math., 221:1–25, 2012.
[KR14]
Thomas Kahle and Johannes Rauh. Toric fiber products versus Segre products. Abh. Math.
Semin. Univ. Hamb., 84(2):187–201, 2014.
[Lau98] Steffen L. Lauritzen. Graphical models, volume 17 of Oxford Statistical Science Series. Oxford
Univ. Press., Oxford, 1998.
[Mac01] Diane MacLagan. Antichains of monomial ideals are finite. Proc. Am. Math. Soc., 129(6):1609–
1615, 2001.
[Oos16] Florian M. Oosterhof. Stabilisation of iterated toric fibre products. 2016. Master’s thesis, Eindhoven University of Technology, http://repository.tue.nl/855107.
[RS14]
Johannes
Rauh
and
Seth
Sullivant.
The
Markov
basis
of
k3,N .
\protect\vrule width0pt\protect\href{http://arxiv.org/abs/1406.5936}{arXiv:1406.5936},
2014.
[RS16]
Johannes Rauh and Seth Sullivant. Lifting Markov bases and higher codimension toric fiber
products. J. Symb. Comp, 74:276–307, 2016.
[Sam17a] Steven V. Sam. Ideals of bounded rank symmetric tensors are generated in bounded degree.
Invent. Math., 207(1):1–21, 2017.
[Sam17b] Steven V. Sam. Syzygies of bounded rank symmetric tensors are generated in bounded
degree. Math. Ann., 368(3–4):1095–1108, 2017.
[Shi12]
Takafumi Shibuta. Gröbner bases of contraction ideals. J. Algebr. Comb., 36(1):1–19, 2012.
[SS17]
Steven V. Sam and Andrew Snowden. Gröbner methods for representations of combinatorial
categories. J. Am. Math. Soc., 30(1):159–203, 2017.
[Sul07]
Seth Sullivant. Toric fiber products. J. Algebra, 316(2):560–577, 2007.
(Jan Draisma) Mathematical Institute, University of Bern, Sidlerstrasse 5, 3012 Bern, Switzerland;
and Eindhoven University of Technology, The Netherlands
E-mail address: jan.draisma@math.unibe.ch
(Florian M. Oosterhof) Department of Mathematics and Computer Science, Eindhoven University
of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
E-mail address: f.m.oosterhof@tue.nl

