TORIC ALGEBRA OF HYPERGRAPHS

arXiv:1206.1904v3 [math.AC] 3 Apr 2013

SONJA PETROVIĆ AND DESPINA STASI

Abstract. The edges of any hypergraph parametrize a monomial algebra called the edge subring of the
hypergraph. We study presentation ideals of these edge subrings, and describe their generators in terms
of balanced walks on hypergraphs. Our results generalize those for the defining ideals of edge subrings of
graphs, which are well-known in the commutative algebra community, and popular in the algebraic statistics
community. One of the motivations for studying toric ideals of hypergraphs comes from algebraic statistics,
where generators of the toric ideal give a basis for random walks on fibers of the statistical model specified by
the hypergraph. Further, understanding the structure of the generators gives insight into the model geometry.

1. Introduction
The rich history of the ideal theory of graphs, dating back to the seminal paper [SVV94], shows that fundamental properties of monomial algebras associated to graphs have interesting combinatorial interpretations.
The connection inspired a body of work that joins combinatorial and algebraic methods with at least two
algebraic objects in focus: monomial edge ideals of graphs, and toric ideals of edge subrings of graphs.
The study of quadratic squarefree monomial ideals corresponding to edges of a graph has generated a lot of
interest from the algebraic community. In particular, the comprehensive monograph [Vil00] contains numerous
references on the subject. More recent work includes, for example, [CN09] who describe Betti numbers and
primary decompositions for edge ideals of restricted families of graphs. On the other hand, presentation ideals
of edge subrings of graphs, which are toric rather then monomial, arise as kernels of monomial maps whose
images correspond to the edges of a graph. These toric ideals have been studied in [Vil95], [OH99, OH00],
[Vil00], [RTT12].
Several results for the monomial edge ideals have been extended to the case of hypergraphs (see, for example,
[HT08], [DV11]), where a hypergraph is a generalization of a graph with edges containing more than two
vertices. However, toric ideals of edge subrings remain completely unexplored beyond the graph case. Nevertheless, they are of interest in applications, and as blow-up algebras, since the edge subring of a uniform
hypergraph is isomorphic to the special fiber ring of its edge ideal.
In this work, we extend the theory for these toric ideals from graphs to (uniform) hypergraphs. We study
the combinatorial signatures of presentation ideals of monomial subalgebras parametrized by squarefree
monomials of degree greater than 2. Their generators, Gröbner and Graver bases are given in terms of
monomial walks on hypergraphs, generalizing the constructions that are well-known for graphs.
One of the motivations for studying toric ideals of hypergraphs comes from algebraic statistics, where generating sets of toric ideals play an important role in testing how well a model fits the given data. The edge subring
of a hypergraph corresponds to any exponential family model whose joint probabilities are parametrized by
monomials. For more details, see Section 3. In fact, edge subrings of graphs are already known in algebraic
statistics, most notably in [Mor13], [OHT13], [SW12], [PRF10]. The first author has used these toric ideals
to gain insight into the geometry of a particular random graph model, existence of maximum likelihood
estimators, and a better way to generate Markov moves [PRF10, RPF]. In particular, this work is a starting
point for developing the theory required for the more general algebraic statistical models.
A hypergraph H is d-uniform if every edge contains d vertices. We describe the natural one-to-one correspondence between sets of squarefree monomials of degree d and d-uniform hypergraphs with the following
notation. For a finite d-uniformQhypergraph H on V = {x1 , . . . , xn } and edge set E, each edge ei of H encodes
a squarefree monomial xei := j∈ei xj of degree d in the polynomial ring k[x1 , . . . , xn ] over a field k. Thus,
Date: April 4, 2013.
1

2

SONJA PETROVIĆ AND DESPINA STASI

the hypergraph H can be written as a set of monomials representing the edges: H = {xe1 , . . . , xek }. The edge
subring of the hypergraph H, denoted by k[H], is the monomial subring of the polynomial ring generated by
the edges of H; in symbols,
k[H] := k[xei : ei ∈ E(H)].
Letting tei be a variable representing the edge ei , define a ring homomorphism φH : k[tei ] → k[H] with
φH (tei ) = xei . The kernel of this monomial map, denoted by IH , is the toric ideal of the edge subring of the
hypergraph H. It encodes the algebraic relations among the edges of the hypergraph.
A first problem of interest is to describe the combinatorics of generators of the ideal for an arbitrary hypergraph. With this in mind, we define monomial walks on hypergraphs and the balancing condition in Section 2,
which are the natural direct generalization of monomial walks on graphs. Theorem 2.8 characterizes the binomials in IH in terms of such monomial walks, extending the classical theorems of Villarreal [Vil95, Vil00],
and Ohsugi and Hibi [OH99]. In Section 3 we outline the relevance of our results: the correspondence between
statistical models and hypergraphs is explored in Section 3.1, and we derive a connection to the well-studied
set-theoretical problem of combinatorial discrepancy in Section 3.2. Given the apparent difficulty of the problem of describing all primitive monomial walks on an arbitrary hypergraph, we dedicate Section 4 to sparsely
intersecting hypergraphs, which generalize the three types of primitive walks on graphs. In particular, Propositions 4.2, 4.5, 4.9 and Theorem 4.12 describe several supporting hypergraphs of primitive monomial walks.
Their basic building blocks consist of matchings and sunflowers, well-known in the hypergraph literature. In
Section 5 we show that many of the results for graphs cannot be generalized, and the expected degree bounds
do not hold. Finally, Section 6 outlines some of the many open problems that we hope will be addressed by
the combinatorics community.
Algebraic properties of toric ideals of hypergraphs such as normality, Cohen-Macaulayness, and geometry
of the corresponding polytopes are all open problems of interest, but are beyond the scope of this paper.
Degree bounds of generators are studied in [GP]. The problem of finding these generators algorithmically and
understanding the complexity of such algorithms remains open and would make a significant contribution to
applied algebraic statistics.
2. Monomial Walks on Hypergraphs
We begin with an example in the case when H is 2-uniform.
Example 2.1. Consider the simplest case when H is a graph, say, the complete graph H = K5 on vertices
x1 , . . . , x5 . The edge subring k[K5 ] ⊆ k[x1 , . . . , x5 ] is parametrized by
φK5 : k[tij ] → k[x1 x2 , x1 x3 , . . . , x4 x5 ]
tij 7→ xi xj .
The toric ideal IK5 is generated by the following 10 quadrics:
t24 t35 − t23 t45 ,

t14 t35 − t13 t45 ,

t34 t25 − t23 t45 ,

t14 t25 − t12 t45 ,

t13 t25 − t12 t35 ,

t34 t15 − t13 t45 ,

t24 t15 − t12 t45 ,

t23 t15 − t12 t35 ,

t13 t24 − t12 t34 ,

t23 t14 − t12 t34 .

For example, the binomial f := t13 t24 − t12 t34 ∈ IH is represented in the leftmost graph of Figure 1. Since f
is represented by an even cycle with alternating colors on the edges, we say that it arises from the cycle.
In general, when H is a graph, then the generators of the ideal IH are known in terms of these red-blue
colorings on the edges of the graph:
Theorem 2.2 ([Vil95], [OH99], see also [Vil00]). The toric ideal of the edge subring of a graph G is generated
by binomials arising from (primitive) even closed walks on G.
Such binomials have been characterized by the following result which, in fact, provides a Graver basis for the
toric ideal.
Theorem 2.3 ([Vil95], [OH99], see also [Vil00]). Primitive even closed walks on G are one of the following:
(i) even cycles, (ii) two odd cycles sharing a vertex, or (iii) two odd cycles such that there are two walks
connecting a vertex in one cycle with a vertex in the other.

TORIC ALGEBRA OF HYPERGRAPHS

x1

x2

x1

x3

x4

x2

x3

x7 x6

x1

x4 x5

x2

x3
x4

x12
x5

3

x7
x6

x11 x10
x8 x9

Figure 1. The three types of walks from Theorem 2.3. Colors are explained in Remark 2.5.
An even closed walk is the exact structure in a graph required to give rise to a binomial: the sequence of
edges in the walk induces a bipartition of the edges with multiplicity and all vertices in the walk have the
same degree in each of the two parts. We propose the following generalization of an even closed walk on a
hypergraph. Following [Vil00], we call it a monomial walk.
Definition 2.4. A monomial walk on a d-uniform hypergraph is an even sequence of edges W := {e1 , e2 , . . . , e2k },
where each edge ei in the sequence intersects the subsequence {e1 , e2 , . . . , ei−1 }, and each vertex v ∈ ∪2k
i=1 ei
covered by W satisfies the following balancing condition: |{ei ∈ W : v ∈ ei and i is odd}| = |{ei ∈ W : v ∈
ei and i is even}|.
Each monomial walk gives rise to a binomial in the ideal IH . Namely, we say that a binomial fW arises from
W if
k
k
Y
Y
fW :=
te2i−1 −
te2i .
i=1

i=1

A monomial walk is said to be primitive if there does not exist a proper subwalk, that is, a collection W 0 of
odd- and even-numbered edges, properly contained in W, such that W 0 is also a monomial walk.
For the remainder of the paper, we occasionally refer to a monomial walk as a walk. For convenience, all
hypergraphs in this paper will be uniform. In the non-uniform case, binomials in IH are not necessarily
supported by alternating monomial walks; although one can extend the balancing condition to the non1 homogeneous toric ideals.
uniform case. Algebraically, we are simply considering
Remark 2.5 (bicoloring the edges in fW ). The classical theorems for graphs use odd and even numbered
edges to describe fW . For hypergraphs, however, we have found this notation and related pictorial representations extremely tedious. Thus, from now on, we refer to the even- and odd-numbered edges as blue and red
edges. This bicoloring is implicit in the graphs case as well.
Example 2.6. Consider a complete 3-uniform hypergraph on 12 vertices. Figure 2 shows three monomial
walks on this hypergraph.

(a)

(b)

(c)

Figure 2. Examples of Walks

In general, there is no squarefree assumption on the binomial fW . Walking along the same edge multiple times
during W is allowed, so it is possible that ei = ej for i 6= j. (See Figure 2(C) for an example.) If an edge
in a monomial walk appears as both red and blue, then these two copies of the edge can be safely removed.
The remaining set of edges constitutes another monomial walk. On the binomial side, this corresponds to a
multiple of a smaller binomial.

4

SONJA PETROVIĆ AND DESPINA STASI

Definition 2.7. Let E be a (multiset) collection of an even number of edges in H. We say that E is balanced
with respect to a given bicoloring of H if for each vertex v covered by E, the number of red edges containing
v equals the number of blue edges containing v; in symbols:
(?)

degblue (v) = degred (v).

The constructions above imply the following.
Theorem 2.8. Let H be a uniform hypergraph. Any balanced collection of edges E ⊂ E(H) constitutes a
monomial walk, or a collection of disjoint monomial walks.
In particular, the ideal IH is generated by binomials fW arising from primitive monomial walks W on H.
Proof. A binomial f is in the ideal IH if and only if the set of edges E appearing in the support of the
binomial is balanced. Namely, f ∈ IH is given by a collection of edges such that
Y
Y
t e0
f=
te −
blue edges e

red edges e0

where the coloring is induced by the binomial f itself. Being in the kernel of ϕH is equivalent to




Y
Y
ϕH 
te  = ϕH 
t e0  .
blue edges e

red edges e0

This, in turn, is equivalent to Condition (?).
We need to show that any balanced collection of edges with respect to some bicoloring can be written as
arising from a monomial walk, or a set of disjoint monomial walks. Throughout the proof we will maintain a
sequence of visited edges W from E, and the set of red and blue degrees of each vertex v covered by E, which
we denote by degred (v; E) and degblue (v; E) respectively.
We begin with W = ∅. Pick an arbitrary blue edge e ∈ E, define e1 := e, and update W = W ∪ {e1 },
E = E − {e1 }, noting that degblue (v; E) has decreased by 1, for every v ∈ e1 . Pick an arbitrary u1 ∈ e1 .
By (?), there exists a red edge e0 ∈ E such that u ∈ e0 . Let e2 := e0 and update W = W ∪ {e2 }, E = E − {e2 },
noting that degred (v; E) has decreased by 1, for every v ∈ e2 . Clearly, u1 is now balanced in W.
Repeat recursively as follows. Check whether degblue (v; E) = degred (v; E) for all v. If not, there must exist
an unbalanced vertex covered by W. For odd (resp. even) i, there exists a blue (resp. red) edge in E that
intersects an even (resp. odd) edge ej in W, j < i. Call this edge ei and move it to W.
On the other hand, if degblue (v; E) = degred (v; E) holds for every v, we have produced a monomial walk W.
In the case where E is not empty, the algorithm restarts on the current E with empty W to find additional
edge-disjoint monomial walks. Finally, the algorithm stops when E is empty.
What we have shown is that every binomial in the ideal IH arises from a finite collection of monomial walks.
That only primitive binomials are necessary to generate the ideal follows from standard arguments: e.g. see
Lemma 4.6 in [Stu96].

Naturally, if a certain edge appeared multiple times in E, each occurrence of the edge gets a unique label, so
that the above argument is valid for multisets of edges.
Recall that the Graver basis is a special generating set of the toric ideal, usually very large and algebraically
redundant, but combinatorially nice. What we have shown above is that the Graver basis of IH consists of
primitive monomial walks with support on the edge set of H. In addition, as in the graphs case, since the
Graver basis contains all reduced Gröbner bases, we can say the following:
Corollary 2.9. If f is a polynomial in any reduced Gröbner basis of IH , then f = fW for some primitive
monomial walk W.
The natural problem now is to understand primitive monomial walks on a given hypergraph H. We will
concern ourselves with a criterion which will allow us to determine if a given set of edges is a primitive
monomial walk. To this end, we make the following definition.

TORIC ALGEBRA OF HYPERGRAPHS

5

Definition 2.10. A multihypergraph H is called a monomial hypergraph if its edges can be colored so that
they are balanced (see Definition 2.7). Such an H is primitive if there exists a balanced bicoloring that makes
the corresponding monomial walk primitive.
The purpose of this definition is twofold. First, note that a monomial hypergraph corresponds to a monomial
walk. However, a given walk comes equipped with the blue and red bicoloring of the edges (i.e., the binomial
is given explicitly); whereas in a monomial hypergraph, the coloring is not fixed (i.e., it represents the support
of the binomial). In the graph case, this distinction is less important because the coloring is more obvious.
For example, when we say that “even cycles are generators of the toric ideal of a graph”, we do not specify
how to color the edges of the cycle; however, upon the inspection of the proof, of course, it is obvious that the
edges are colored in alternating colors to give rise to a binomial. In hypergraphs, such a choice of coloring may
not always be immediate or unique, so this distinction is important. Second, a monomial hypergraph is not
a simple hypergraph: there is no squarefree assumption on the monomial walks, so an edge in a hypergraph
may be traced multiple times in a walk over its edge set. This generality is required since we cannot assume
that the binomials in IH are squarefree.
Corollary 2.11. The set of binomials
{fW |W is a bicolored primitive monomial hypergraph over the hypergraph H}
is a universal Gröbner basis for the toric ideal IH .
In summary: a monomial walk has an alternating coloring on the edges and requires that all the visited
vertices are balanced with respect to that coloring; and a monomial hypergraph is a multihypergraph with
the supporting edge set being that of H, it corresponds to a monomial walk, but its coloring is not fixed. The
monomial hypergraph corresponding to the monomial walk W is the combinatorial signature of the binomial
fW ∈ I H .
3. Monomial hypergraphs: from log-linear models to discrepancy
Before exploring the structure of monomial hypergraphs in the next section, let us briefly reflect on their
relevance. We explain how they arise naturally in algebraic statistics, and proceed to show how they relate
to combinatorial discrepancy of hypergraphs.
3.1. Parameter hypergraphs. Monomial maps make a notable appearance in statistics: they encode important families of statistical models for discrete random variables called log-linear models. A log-linear model
is a family of joint probability distributions that are described by monomials in the model parameters (equivalently, minimal sufficient statistics of the model are in the row span of a linear map, and hence the name;
but let us not dwell on this here). To see how monomial maps arise, let us consider the following very simple
example. Two random variables Z1 and Z2 , taking a and b values, respectively, are said to be independent
if the joint probability Pij := P rob(Z1 = i, Z2 = j) factors as follows: Pij = P rob(Z1 = i)P rob(Z2 = j) for
all i ∈ [a] and j ∈ [b]. Denote the probabilities P rob(Z1 = i) and P rob(Z2 = j) by xi and xa+j , respectively.
The unknown quantities x1 , . . . , xa+b are called the model parameters; they completely determine this family
of distributions. We can summarize this simple example by saying that the independence model for Z1 and
Z2 is specified by the monomial map that sends Pij to xi xa+j . In this sense, the edge subring k[Ka,b ] of the
complete bipartite graph Ka,b on the vertex set {x1 , . . . , xa } t {xa+1 , . . . , xa+b } describes the structure of the
joint probability distributions that belong to the independence model.
This correspondence can be naturally extended to any more complicated model for discrete random variables
Z1 , . . . , Zm , whose joint probabilities are parametrized by squarefree monomials in the model parameters
x1 , . . . , xn . Each such log-linear model M is encoded by a hypergraph HM on the vertex set x1 , . . . , xn ,
constructed as follows: {xj }j∈J is an edge of HM if and only if the index set J describes one of the joint
probabilities
in the model; that is, there exist values i1 , . . . , im such that P rob(Z1 = i1 , . . . , Zm = im ) =
Q
x
.
j∈J j
Henceforth, we will name HM the parameter hypergraph of the model M. Somewhat surprisingly, toric ideals
IHM are quite relevant for testing goodness of fit of the model M. Without going into statistical details, a
non-asymptotic test for model/data fit is carried out by exploring the fiber of a given point in the image of

6

SONJA PETROVIĆ AND DESPINA STASI

the monomial map φHM . In terms of the hypergraph HM , an observed data point corresponds to a collection
of edges; for convenience, think of them as colored blue. The fiber of that data point then consists of all red
edge sets that balance it, and thus have the same image under the map φHM . The recipe for exploring a fiber
is to move from any point to another point by applying a Markov move, which corresponds to a generator
of the toric ideal IHM of the model. Since the binomials in IHM are supported by balanced edge sets, this
move is interpreted as removing the observed (blue) edges and replacing them by the red edges, arriving at
another monomial with the same image. The correspondence between Markov moves and toric generators
is well-known in algebraic statistics literature, and often referred to as the fundamental theorem of Markov
bases. The technical description of how such a random walk on a fiber is actually implemented is beyond the
scope of this paper; but the interested reader is referred to [DSS09] and the recent text [AHT12].
In general, finding Markov bases for many relevant statistical modes is a wide-open problem; some complexity
bounds and a few structural theorems are known. Therefore, our goal is to understand the combinatorial
structure of monomial hypergraphs supported on HM . Instead of focusing on one log-linear model, we explore
combinatorial signatures of general monomial hypergraphs. We focus on homogeneous ideals, thus the models
parametrized by uniform hypergraphs. Finally, as explained in [AHT12], for homogenous toric models with
statistical sampling constraints or with structural zeros in the model, a minimal generating set of the toric
ideal may not suffice for connecting the fibers, and instead squarefree part of the Graver basis is used.
As mentioned in the introduction, the edge subring of a graph has appeared in several results in algebraic
statistics. By defining the parameter hypergraph HM , which the reader should agree is quite a natural
generalization, we give an applied motivation to extend the well-known results on toric ideals of graphs
to the more general case. By Theorem 2.8, Markov moves for any (homogeneous) log-linear model M are
encoded by primitive monomial hypergraphs supported on a (uniform) HM . One of our main goals is to
frame this problem in terms of combinatorics of hypergraphs.
3.2. A dual problem: combinatorial discrepancy. To that end, we begin by noting a relation between
monomial hypergraphs and zero-discrepancy hypergraphs. Broadly, the combinatorial discrepancy problem
asks for a coloring of the vertices of a hypergraph H = (V, E) such that each hyperedge contains roughly the
same number of vertices of each color. (The reader is directed to [Mat10, Cha02] for a detailed introduction
to discrepancy theory.) Let us formally define the discrepancy of a hypergraph.
Definition 3.1. The
Pdiscrepancy of a hypergraph H = (V, E), denoted disc(H), is the quantity disc(H) =
minχ:V →±1 maxe∈E v∈e χ(v). In words, it is the minimum, over all colorings χ, of the maximum discrepancy
of an edge in H.
Given a hypergraph H, the dual hypergraph H ∗ is the hypergraph containing a vertex v ∗ for each edge
e ∈ E(H) and an edge e∗ for each v ∈ V (H); here e∗ = {v ∗ ∈ V (H ∗ ) : v ∗ corresponds to an edge e ∈
E(H) that is incident in H to vertex v}. More briefly, the vertex-edge incidence matrix of H ∗ is the transpose
of the vertex-edge incident matrix of H.
It is not hard to see that a zero-discrepancy hypergraph H ∗ = (V ∗ , E ∗ ) is dual to a monomial hypergraph
H = (V, E): the mapping χ : V ∗ → ±1 acts on the vertices of H ∗ but it acts on the edges of H. Zero
discrepancy for H ∗ implies that each edge of H ∗ contains the same number of red and blue vertices, and
by consequence each vertex of H is incident to the same number of red and blue edges. This establishes the
following theorem.
Theorem 3.2. A hypergraph H is a monomial hypergraph if and only if disc(H ∗ ) = 0. Furthermore, a
monomial hypergraph H is primitive if and only if no coloring χ : V ∗ → ±1 realizing disc(H ∗ ) = 0, also
induces a zero discrepancy coloring on a (non-empty) subhypergraph H̃ of H ∗ produced by deleting any subset
of vertices and shrinking the edges.
Deleting a vertex from H ∗ and shrinking its incident edges is equivalent to deleting an edge in the dual
hypergraph H. There are some other interesting facts here. While a monomial hypergraph can have multiple
edges, this is not true or necessary for the dual zero-discrepancy hypergraph, as multiple edges in H would
correspond to vertices that are incident to the same set of edges in the dual.
An important inapproximabillity result of [CNN11] on discrepancy implies that it is NP-Hard to decide
whether a hypergraph H = (V, E) is the support for a monomial hypergraph, or p
whether for every bicoloring
of E(H), there exists a vertex v ∈ V (H) such that |degred (v) − degblue (v)| ≥ Ω( |E(H)|).

TORIC ALGEBRA OF HYPERGRAPHS

7

Given the difficulty of deciding the discrepancy of a hypergraph, we pursue a structural theorem for monomial
hypergraphs in the next section.
4. Sparse Bouquets
Theorem 2.8 can be used to give a characterization of (primitive) monomial walks in terms of the existence
of an edge partition satisfying the degree condition (?). However it gives no other information about the
structure of the supporting hypergraphs.
In this section, we use Theorem 2.8 to construct and study supports of monomial hypergraphs that parallel
the graphs case. For example, consider case (ii) from Theorem 2.3. Two odd cycles glued at a vertex support
a primitive monomial walk on a graph. Increasing the degree of that core vertex could produce monomial
walks, but they can never be primitive. In contrast, the core vertices in hypergraph supports of primitive
walks can have degree larger than 2; in fact, it can be arbitrarily high!
The first three results in this section directly generalize cases (i), (ii) and (iii) (for short cycles) from
Theorem 2.3. First, a pair of perfect matchings generalizes an even cycle, and its supporting hypergraph is
characterized in Proposition 4.2. Second, a monomial sunflower generalizes a bow-tie (two 3-cycles sharing
a vertex), and its supporting hypergraphs are characterized in Proposition 4.5. Finally, a partitioned core
sunflower generalizes two 3-cycles connected by two paths, and the supporting hypergraphs are described in
Proposition 4.9.
A further generalization summarizing the above propositions is given in Theorem 4.12. So, unlike in the case
of graphs, these three results do not exhaustively characterize monomial hypergraphs. Nevertheless, starting
from sunflowers and matchings, natural building blocks of monomial hypergraphs, we can obtain much more
complex structures. We delve more into the open problem of structurally characterizing primitive monomial
hypergraphs in Section 6.
4.1. Matchings.
Definition 4.1. A matching on a hypergraph H = (V, E) is a subset M ⊂ E of independent edges, that
is, no two edges intersect. A matching is called perfect if it covers all the vertices of the hypergraph, i.e.,
V (M ) = V .
The simplest monomial hypergraph can be formed using a pair of perfect matchings on the same set of
variables. Next we give a sufficient and necessary condition for the primitivity of such a monomial hypergraph.
A hypergraph H = (V, E) is said to be connected if its primal graph is connected, where the primal graph
has the same vertex set and an edge between any two vertices contained in the same hyperedge.
Proposition 4.2 (Pair of matchings). Let H = (V, E) be a d-uniform hypergraph such that E = Mr t Mb ,
where Mr , Mb form two edge-disjoint perfect matchings on the vertex set V . A monomial hypergraph H with
support H is primitive if and only if H is connected and H contains no multiple edges.
Proof. Let H be a primitive monomial hypergraph and consider a primitive monomial walk W on the edges
of H with an appropriate associated bicoloring. Any walk is connected, so suppose for contradiction that
edge e ∈ E has multiplicity k in W. By construction of the supporting hypergraph H, there exist exactly
two distinct edges in H, say e and f , containing any vertex v. We may assume that all copies of e in W are
red, as two copies of e in W that belong to a different color partition would create a trivial subwalk. By the
degree condition (?) there must be k copies of f in W, all colored blue. Edges e and f are distinct so there
exists a vertex u in f and a unique edge g in H such that g contains u and has multiplicity k in W. But H
is connected, so we may repeat this process for each vertex in W to conclude that all edges in E appear in
W in k copies of the same color, contradicting the primitivity of W.
For sufficiency, we need only produce a bicoloring for the edges of H, taken with no multiplicity, such that
the associated walk is primitive. We construct the required bicoloring by coloring edges in Mr red and edges
in Mb blue. Assume by way of contradiction that there exists a smaller walk W in H that is also a monomial
walk. Let VW and EW be the vertex and edge sets induced by the walk W, and let HW = (VW , EW ). It is
clear that every vertex in any monomial walk, and so specifically in HW must have degree at least 2 (the
sum of the blue degree and the red degree). Since W is a subwalk, there must be some edge or vertex of H

8

SONJA PETROVIĆ AND DESPINA STASI

that W does not contain. But every vertex in HW has degree 2 so there can be no more edges in H \ HW
containing any vertex from HW . Then H is disconnected.

Figures 2(A) and 2(B) are primitive matchings. The former is also commonly called a tight cycle.
4.2. Monomial Sunflower. As pairs of matchings have the property that each vertex has degree 2, they
generalize even cycles on graphs. In contrast, the next case in Theorem 2.3 has a distinguished vertex of
higher degree. Its natural generalization in hypergraphs, which we will call a monomial sunflower, is the
topic of this subsection, and is based on a very useful, highly structured hypergraph, the sunflower, which,
incidentally, is guaranteed to occur in hypergraphs with large enough edge sets, independently of the size of
the vertex set. (See e.g. [Juk01].)
Definition 4.3. A d-uniform hypergraph H = (V, E) is a sunflower if ei ∩ ej = C for all edges ei 6= ej ∈ E,
and C ⊂ V . The set of vertices C is called the core of the sunflower, and each ei is called a petal.
In general, one may allow the core to be empty, in which case you simply get a matching. In this paper, we
will explicitly use the name matching instead of allowing for empty cores.
For the remainder of the paper, fix the following notation.
Notation 4.4. For a subset C ⊂ V (H), define H − C to be the hypergraph with vertex set (V r C) and
edges {ei r C : ei ⊂ E(H)}. Similarly, for a subset C ⊂ V (H), define H − C to be the multihypergraph with
vertex set (V r C) and edges {ei r C : ei ⊂ E(H)}. The hypergraphs H − C and H − C are not necessarily
uniform and may include empty edges, or multiple copies of an edge. See Figures 3, 4 and 9 for examples.
Clearly, there is no nontrivial monomial walk on a sunflower: since the degree of any non-core vertex is 1,
every petal needs to be both blue and red, resulting in the zero binomial. Thus, a sunflower alone cannot be
a support of a monomial hypergraph. The non-core petal vertices could, however, be balanced by a perfect
matching. To that end, consider H to be a sunflower with a perfect matching on its non-core vertices. In
Proposition 4.5, we show that a primitive monomial hypergraph with support H can be characterized by
counting petals.
Consider the set of connected components
H −C =

[

Gj .

j∈I

S
For convenience, define GJ := j∈J Gj , for any index set J ⊆ I. By abuse of notation we will write |Gj |
for the number of edges in the multiset {e ∈ H : e ∩ C 6= ∅ and e r C ∈ Gj }.
The next proposition is based on the idea that counting petals detects balanced walks on H.
Proposition 4.5 (Sunflower). Let H be a hypergraph consisting of a sunflower and a perfect matching on
the non-core vertices of the sunflower. The hypergraph H is the support of a monomial hypergraph H if and
only if there exists a partition (GJ , GK ) of the connected components of H − C such that
X
X
mj |Gj | =
mk |Gk |, where mj , mk are integers.
j∈J

k∈K

In addition, H is primitive if and only if the partition (GJ , GK ) also satisfies the following two conditions:
P
P
i. no two subsets J 0 ( J and K0 ( K satisfy j∈J 0 m0j |Gj | = k∈K0 m0k |Gk | for some integers m0j ≤ mj ,
m0k ≤ mk and
0
ii. there are P
no integers m0j , m
that the partition (GJ , GK ) of the connected components of H − C
Pk ∈ Z such
0
0
0
0
satisfies
j∈J mj |Gj | =
k∈K mk |Gk |, where mj ≤ mj , mk ≤ mk and for at least one integer the
inequality is strict.
Proof. For the easy directionP
of the first statement,
suppose (GJ , GK ) is a partition of the connected comP
ponents of H − C such that j∈J mj |Gj | = k∈K mk |Gk | for some mj , mk ∈ Z. Construct the monomial
walk W as follows: for every edge e having a nonempty intersection with Gj , j ∈ J (respectively Gk , k ∈ K),
include in W, mj (respectively mk ) copies of edge e. Color the matching edges red for J and blue for K, and

TORIC ALGEBRA OF HYPERGRAPHS

9

use the opposite colors for the petal edges. This immediately ensures
satisfy the dePthat the non-core vertices P
gree condition (?). The degrees of a core vertex v are degblue (v) = j∈J mj |Gj | and degred = k∈K mk |Gk |
respectively.
For the other direction of the first statement, suppose H is a monomial hypergraph over H and consider the
monomial walk W consisting of the edges of H. For every vertex v in a component Gi of H, there are exactly
two distinct edges containing v: a petal edge e and a matching edge f . Suppose e appears with multiplicity
mi in W. Without loss of generality, we may assume that all mi copies of e must belong to the same color
partition, say red. By the degree condition (?), edge f must also appear in W with multiplicity mi , and all
mi copies must belong to the blue color partition. Now there exists a vertex u ∈ f ∩ e0 (u 6= v) where e0
(e0 6= e) is the unique petal edge containing u. To ensure u is balanced, by the degree condition, e0 must also
appear in W with multiplicity mi . Repeating this argument over all vertices in the connected component
Gi we conclude that each matching edge in Gi and each petal edge whose non-core vertices fall in Gi , must
appear in W with multiplicity mi . Then we may construct the partition (GJ , GK ) so that Gi ∈ GJ if the
matching edges
colored red, and Gi ∈ GK otherwise. Since the core vertices are also balanced,
P it contains areP
the equation j∈J mj |Gj | = k∈K mk |Gk | holds, where the sum on the left hand side counts the blue degree
of a core vertex and the right hand side its red degree.
The second statement in the proposition (primitivity) follows from the first statement and the definition
of primitivity. Condition i. describes all subwalks not using all edges of the supporting hypergraph H and
condition ii. describes all subwalks using all edges of H with smaller multiplicity then in H.

We may now make the following definition.
Definition 4.6. A monomial sunflower is a monomial hypergraph with support set consisting of a sunflower
and a perfect matching on the non-core vertices.
The partition (GJ , GK ) corresponds to a bicoloring of the petals of the sunflower, as illustrated in the
following example.
Example 4.7. Figure 3 demonstrates that H1 is the support of a simple non-primitive monomial sunflower
and its components. Each edge appears exactly once in H1 , and it is easy to see that for any two components
in H − C, there is a bicoloring of H1 such that the two components form a subwalk.

Figure 3. A walk on the non-primitive monomial sunflower H1 (left) and the components
of H1 − C with appropriate coloring and multiplicity (right).
Figure 4 demonstrates a bicoloring of the monomial sunflower H2 that makes it primitive. The appropriate
multiplicities for each component are m1 = 1 and m2 = 2.
4.3. Independent Petal Bouquets. To produce more general monomial hypergraphs and characterize
primitivity on them, we may generalize the monomial sunflower by considering a hypergraph H formed by
a collection of sunflowers and a perfect matching on the subset of vertices that are not in the core of any
sunflower. Let us, first, assume that the sunflowers are entirely disjoint.

10

SONJA PETROVIĆ AND DESPINA STASI

Figure 4. A walk on the primitive monomial sunflower H2 (left) and the components of
H1 − C with appropriate bicoloring and multiplicity (right).
Let H be a hypergraph consisting of
S a collection of vertex-disjoint sunflowers S1 , S2 , . . . , S` and a perfect
matching on the non-core vertices of i Si . We will call such an H a matched-petal partitioned-core sunflower.
As we saw in Proposition 4.5, when H contains a single sunflower, the components of H − C and their
multiplicities determine the degrees of the vertices of H and ensure that the core is balanced. In a matchedpetal partitioned-core sunflower, not all the components contribute to every sunflower Si . So, one needs to
keep track of the components of H − C that contain vertices of Si , for each Si . We employ the following
notation.
Notation 4.8. Let H be a matched-petal partitioned-core sunflower. Given a fixed partition (GJ , GK ) of the
connected components of H − C, and a fixed sunflower Si of H, define J (Si ) ⊂ J (respectively K(Si ) ⊂ K)
to include every j ∈ J (respectively j ∈ K), such that Gj contains a vertex of Si . In symbols, J (Si ) is the
set of indices defined as J (Si ) := {j ∈ J (Si ) : j ∈ J and e ∩ Gj 6= ∅ for some edge e ∈ Si }.
Proposition 4.9 (Partitioned Core Sunflower). Let H be a matched-petal partitioned-core sunflower, and
adopt notation 4.8.
The hypergraph H is the support of a monomial hypergraph H if and only if there exists a partition (GJ , GK )
of the connected components of H − C such that for each 1 ≤ i ≤ `:
X
X
mj |Gj | =
mk |Gk |, where mj , mk are integers.
j∈J (Si )

k∈K(Si )

In addition, H is primitive if and only if the partition (GJ , GK ) also satisfies the following two conditions:
i. no two subsets J 0 ( J and K0 ( K satisfy for each 1 ≤ i ≤ `,
X
X
m0j |Gj | =
m0k |Gk |,
j∈J (Si )∩J 0

k∈K(Si )∩K0

for some integers m0j ≤ mj , m0k ≤ mk , and
ii. there are no integers m0j , m0k ∈ Z such that the partition (GJ , GK ) of the connected components of H − C
satisfies for each 1 ≤ i ≤ `,
X
X
m0j |Gj | =
m0k |Gk |,
j∈J (Si )

k∈K(Si )

where m0j ≤ mj , m0k ≤ mk and for at least one integer the inequality is strict.
Proof. The first statement follows with the same argument as Proposition 4.5 for the non-core
P vertices. For
a core vertex, given a partition (GJ , GK ) of the connected components of H − C, the sum j∈J (Si ) mj |Gj |
P
(respectively k∈K(Si ) mk |Gk |) counts the number of petals of sunflower Si whose remnants fall in components GJ (Si ) (respectively GK(Si ) ), and as such completely determines the quantity that each part of the

TORIC ALGEBRA OF HYPERGRAPHS

11

bipartition contributes to the degree of a core vertex v ∈ Si . As before, the second statement describes two
types of subwalks.

Example 4.10. Figure 5 demonstrates a primitive partitioned core monomial sunflower H. Note that all of
the multiplicities are equal to one.

Figure 5. Primitive partitioned-core monomial sunflower H3 , with an appropriate bicoloring.
We relax the disjointness property of the sunflowers above, and allow the sunflowers to intersect on core
vertices. Let H be a hypergraph consisting of a collection of sunflowers S1 , S2 , . . . , S` , which may only intersect
at their cores (known as a relaxed core sunflower), and a perfect matching on the non-core vertices of the
sunflowers. We will call such an H a matched-petal relaxed-core sunflower.
In the partitioned core case, the degree of each core vertex depends on exactly one sunflower. In contrast,
allowing intersections in the cores causes the degree of a core vertex to depend on several sunflowers. This
prompts the following notation.
Notation 4.11. For a matched-petal relaxed-core sunflower, define I(v) to consist of the set of indices i
such that vertex v is in the core of sunflower Si . In symbols I(v) := {i ∈ I(v) : v ∈ Si }.
In addition, notation 4.8 extends to H.
Theorem 4.12 (Relaxed Core Sunflower). Let H be a matched-petal relaxed-core sunflower, and adopt
notation 4.8 and 4.11.
The hypergraph H is the support of a monomial hypergraph H if and only if there exists a partition (GJ , GK )
of the connected components of H − C such that for each vertex v in the core of a sunflower:
X X
X X
mj |Gj | =
mk |Gk |, where mj , mk are integers.
i∈I(v) j∈J (Si )

i∈I(v) k∈K(Si )

In addition, H is primitive if and only if the partition (GJ , GK ) also satisfies the following two conditions:
i. no two subsets J 0 ( J and K0 ( K satisfy for each vertex v in the core of the sunflower,
X
X
X
X
m0j |Gj | =
m0k |Gk |,
i∈I(v) j∈J (Si )∩J 0

for some integers m0j ≤ mj , m0k ≤ mk , and

s∈I(v) k∈K(Si )∩K0

12

SONJA PETROVIĆ AND DESPINA STASI

ii. there are no integers m0j ≤ mj , m0k ≤ mk ∈ Z, where the inequality is strict for at least one integer, such
that the partition (GJ , GK ) of the connected components of H − C satisfies for each vertex v in the core
of a sunflower,
X X
X X
m0j |Gj | =
m0k |Gk |.
i∈I(v) j∈J (Si )

i∈I(v) k∈K(Si )

Proof. Follow the proof of Proposition 4.9 with one important exception. The degree of a core vertex may
now depend on several sunflowers,
P
P and so the quantity necessary to calculate the degree of a core vertex v in
part J , for example, is i∈I(v) j∈J (Si ) m0j |Gj |.

Proposition 4.9 can be obtained as a corollary of Theorem 4.12.
Example 4.13. Figure 6 demonstrates a simple primitive relaxed core monomial sunflower H4 with four
sunflowers. Each multiplicity equals one.

Figure 6. Primitive relaxed core monomial sunflower H4 , with an appropriate bicoloring.

5. Bouquet Complexity
The types of Graver elements studied in Propositions 4.2, 4.5 and 4.9 are, in fact, the simplest ones that may
occur beyond the graphs case. They are the natural direct generalization of the three types of monomial walks
on graphs from Theorem 2.3 (see also Figure 1), each of which is an example of a sparse bouquet. By allowing
the edges to contain more than two vertices, we inadvertently and significantly increase the complexity of
the primitive walks. This already occurs on 3-uniform hypergraphs and on sparse bouquets. We summarize
some of the different ways in which the complexity has increased through the following examples.
In the case of graphs, it is known (see [Vil00, Proposition 8.1.6]) that the largest degree of a vertex in the
support of a primitive walk is 4, and that the edges in the support of the walk can be traversed at most
twice. None of these restrictions extend to d-uniform hypergraphs (d > 2), where a primitive walk can contain
vertices with arbitrarily large degree; can contain arbitrarily many vertices of large degree; and a supporting
edge can be used arbitrarily many times in a primitive walk.
It is not hard to see that there exists exactly one primitive d-uniform monomial sunflower with core of size
d − 1: the one containing exactly 2d + 2 hyperedges. On the other hand, figure 7 demonstrates a family of
primitive 3-uniform bouquets on n vertices with number of edges of the order of n and containing a vertex
with degree of the order of n. Figure 8 demonstrates a family of 3-uniform bouquets in which the number of
cores, vertex degrees, and edge multiplicities can be arbitrarily high.

TORIC ALGEBRA OF HYPERGRAPHS

13

Figure 7. A primitive monomial hypergraph containing a vertex with arbitrarily large degree.

Figure 8. A primitive monomial hypergraph with arbitrarily many cores.
6. Conclusion and open problems
Using the sparse hypergraphs as a starting point, one should consider the problem of classifying supports
of more general monomial hypergraphs. However, this problem is highly nontrivial. For example, Figure 9
represents a simplest example of a non primitive monomial walk that is not of the form covered in Section 4.
The hypergraph consists of two overlapped walks. It is tempting to mimic the constructions for sparse
bouquets and express this hypergraph as a union of, say, four sunflowers S1 , . . . , S4 with two petals each:
S1 = {e1 , e3 }, S2 = {e2 , e4 }, S3 = {e5 , e7 }, S4 = {e6 , e8 }. Then, removing the cores from these sunflowers
and counting the petal remnants in the connected components, with multiplicity 1, as suggested by a direct
generalization of Theorem 4.12, would reveal that S3 ∪ S4 is a balanced set of edges. In this way, one could
detect that the monomial hypergraph S1 ∪ · · · ∪ S4 is not primitive.
In general, however, an arbitrary monomial hypergraph consists of sunflowers that overlap in unrestricted
ways, and thus it is not guaranteed that removing the cores will disconnect and detect a subwalk. In particular,
a direct generalization of the results from Section 4 does not hold without further assumptions.
Problem 6.1. Find a criterion to detect primitivity of a given monomial hypergraph H based on a subset
of the edges in H.

14

SONJA PETROVIĆ AND DESPINA STASI

Figure 9. A non-primitive monomial bouquet
At the moment, the best result in this direction is Theorem 2.8. For “sparse” collections of sunflowers and
matchings, Section 4 offers more efficient criteria. But if the hypergraph is more dense, an arbitrary sunflower
decomposition alone does not seem to suffice.
More generally, it would be interesting, although difficult, to solve the following specific instance of the general
problem of characterizing primitive walks.
Problem 6.2. Characterize (combinatorially) the supports of primitive monomial hypergraphs over an
arbitrary 3-uniform hypergraph.
We remind the reader that even for 3-uniform hypergraphs, any of the types of bouquets that we describe can
appear in the Graver basis, as demonstrated throughout the paper. Thus Problem 6.2 is highly non-trivial;
however, we expect it to have a nice answer for a subclass of 3-uniform hypergraphs, for example, where it
is possible to partition a vertex set in a way that restricts the types of bouquets that may appear. On the
other hand, recall the ultimate goal of interest to statistical applications: we are looking for characterizations
of the structure of monomial walks for a family of hypergraphs specified by conditions that are significantly
more restrictive than uniformity. The family will come from a statistical model with a prescribed edge size,
or edge types. Such conditions will necessarily restrict the ways in which edges of H can intersect, and thus
may imply the sparsity of walks supported on H.
Furthermore, one can quickly derive the entire Graver basis for the following two classes of hypergraphs.
For any 2-regular hypergraph, it consists only of pairs of matchings as in Proposition 4.2. In particular,
the Graver basis of a connected 2-regular hypergraph contains F
exactly one element. Secondly, consider the
d-uniform hypergraph Crd = (V, E), produced by letting V = 1≤i≤r Vi , with each Vi having size d/2 (d
even), and edge set E = {Vi ∪ Vj : for 1 ≤ i < j ≤ r}. A (primitive) monomial walk on Crd corresponds
to a (primitive) even closed walk in the complete graph Kr , as each hyperedge in Crd is in a one-to-one
correspondence with an edge in Kr .
Our next problem concerns generating primitive monomial hypergraphs. It is possible to generate such hypergraphs by contraction or “gluing” operations using known monomial hypergraphs (and sparse bouquets in
particular) as building blocks. For example, one may produce d-uniform monomial sunflowers from a d-uniform
pair of perfect matchings by identifying selected sets of independent vertices. This operation preserves primitivity. The converse is only true if vertex-identification takes place within connected components. In general,
one may also glue two hypergraphs H1 , H2 along the vertices of an edge to produce a new hypergraph H,
introducing new primitive elements in IH constructed from binomials from IH1 and IH2 . The support of the
monomial hypergraph in Figure 10 was partially constructed from the support of four monomial sunflowers
with this gluing operation. It is not hard to see that B is a monomial hypergraph.
A general gluing operation for graphs, based on a toric fiber product, is described in [EKS]. It preserves many
properties of toric ideals.
Problem 6.3. Find a gluing operation on hypergraphs that preserves primitivity of monomial walks. Is it
possible to generate all primitive monomial hypergraphs starting from sparse bouquets?

TORIC ALGEBRA OF HYPERGRAPHS

15

Figure 10. A primitive bouquet B partially produced by gluing four sparse bouquets.
The primitive walks in hypergraphs are clearly much more general than in the case of graphs, as Section 5
shows. Nevertheless, we expect many of the other properties of the coordinate ring of IH to have combinatorial
interpretations. For example, the first author studies the degree bounds on the minimal generators of IH in
[GP], generalizing the theorems known for graphs.
Finally, the problems of finding nice term orders and reduced Gröbner bases of IH , characterizing CohenMaculayness and normality of the coordinate ring and the corresponding polytope, and relating known
coloring-inspired properties of hypergraphs to various invariants of the toric ideal IH are wide open.
Acknowledgements
The authors thank György Turán for inspiring discussions, at the start of this project, about the fundamental problem of walks in hypergraphs; and also Elizabeth Gross for suggesting the name “bouquet”, and
proofreading an early version of the manuscript. The second author is grateful to Amitava Bhattacharya for
introducing her to combinatorial discrepancy. Finally, we are grateful to the anonymous referee for thoughtful
and thorough comments that helped improve this work.
The authors acknowledge support by grant FA9550-12-1-0392 from the U.S. Air Force Office of Scientific
Research (AFOSR) and the Defense Advanced Research Projects Agency (DARPA). The AMS Simons Travel
Grant has helped the first author tremendously during the first year of the project.
References
[AHT12] Satoshi Aoki, Hisayuki Hara, and Akimichi Takemura, Markov bases in algebraic statistics, Springer Series in Statistics,
Springer New York, 2012.
[Cha02] Bernard Chazelle, The discrepancy method: Randomness and complexity, Cambridge University Press, 2002.
[CN09] Alberto Corso and Uwe Nagel, Monomial and toric ideals associated to Ferrers graphs, Trans. Amer. Math. Soc. 361
(2009), no. 1371–1395.
[CNN11] Moses Charikar, Alantha Newman, and Aleksandar Nikolov, Tight hardness results for minimizing discrepancy, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, 2011, pp. 1607–
1614.
[DSS09] Mathias Drton, Bernd Sturmfels, and Seth Sullivant, Lectures on algebraic statistics, Oberwolfach Seminars, vol. 39,
Birkhäuser, 2009.
[DV11] Luis A. Dupont and Rafael H. Villarreal, Algebraic and combinatorial properties of ideals and algebras of uniform
clutters of TDI systems, Journal of Combinatorial Optimization 21 (2011), no. 3, 269–292.
[EKS]
Alexander Engstrom, Thomas Kahle, and Seth Sullivant, Multigraded commutative algebra of graph decompositions,
arXiv:1102.2601.
[GP]
Elizabeth Gross and Sonja Petrović, Combinatorial degree bound for toric ideals of hypergraphs, arXiv:1206.2512.
[HT08] Huy Tài Hà and Adam Tuyl, Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers, Journal
of Algebraic Combinatorics: An International Journal 27 (2008), no. 2, 215–245.
[Juk01] Stasys Jukna, Extremal combinatorics - with applications in computer science, Texts in theoretical computer science,
Springer, 2001.
[Mat10] Jiri Matoušek, Geometric discrepancy: An illustrated guide, Springer Verlag, 2010.

16

[Mor13]
[OH99]
[OH00]
[OHT13]
[PRF10]

[RPF]
[RTT12]
[Stu96]
[SVV94]
[SW12]
[Vil95]
[Vil00]

SONJA PETROVIĆ AND DESPINA STASI

Jason Morton, Relations among conditional probabilities, Journal of Symbolic Computation 50 (2013), 478–492.
Hidefumi Ohsugi and Takayuki Hibi, Toric ideals generated by quadratic binomials, Journal of Algebra 218 (1999),
no. 2, 509–527.
, Compressed polytopes, initial ideals and complete multipartite graphs, Illinois J of Mathematics 44 (2000),
no. 2, 391–406.
Mitsunori Ogawa, Hisayuki Hara, and Akimichi Takemura, Graver basis for an undirected graph and its application
to testing the beta model of random graphs, Annals of Institute of Statistical Mathematics. 65 (2013), 191–212.
Sonja Petrović, Alessandro Rinaldo, and Stephen E. Fienberg, Algebraic statistics for a directed random graph model
with reciprocation, Algebraic Methods in Statistics and Probability II (M. Viana and H. Wynn, eds.), Contemporary
Mathematics, vol. 516, American Mathematical Society, Providence RI, 2010, pp. 261–283.
Alessandro Rinaldo, Sonja Petrović, and Stephen E. Fienberg, Maximum likelihood estimation in the β model, Annals
of Statistics. To appear. Preprint available at arXiv:1105.6145.
Enrique Reyes, Christos Tatakis, and Apostolos Thoma, Minimal generators of toric ideals of graphs, Advances in
Applied Mathematics 48 (2012), no. 1, 64–78.
Bernd Sturmfels, Gröbner bases and convex polytopes, University Lecture Series, no. 8, American Mathematical Society,
1996.
Aron Simis, Wolmer V. Vasconcelos, and Rafael H. Villarreal, On the ideal theory of graphs, Journal of Algebra 167
(1994), no. 2, 389–416.
Bernd Sturmfels and Volkmar Welker, Commutative algebra of statistical ranking, Journal of Algebra 361 (2012),
264–286.
Rafael H. Villarreal, Rees algebras of edge ideals, Communications in Algebra 23 (1995), no. 9, 3513–3524.
Rafael H. Villarreal, Monomial algebras, CRC Press, 2000.

Sonja Petrović is with the Department of Statistics, The Pennsylvania State University, University Park PA 16802
E-mail address: petrovic@psu.edu
Despina Stasi was with the Department of Mathematics, Statistics and Computer Science, University of Illinois at
Chicago, Chicago IL 60607; and is currently at the Department of Statistics, The Pennsylvania State University,
University Park PA 16802
E-mail address: despina@psu.edu

