arXiv:1711.04354v1 [math.AC] 12 Nov 2017

HYPERGRAPH ENCODINGS OF ARBITRARY TORIC IDEALS
SONJA PETROVIĆ, APOSTOLOS THOMA, MARIUS VLADOIU
Abstract. Relying on the combinatorial classification of toric ideals using their
bouquet structure, we focus on toric ideals of hypergraphs and study how they
relate to general toric ideals. We show that hypergraphs exhibit a surprisingly
general behavior: the toric ideal associated to any general matrix can be encoded
by that of a 0/1 matrix, while preserving the essential combinatorics of the original ideal. We provide two universality results about the unboundedness of degrees
of various generating sets: minimal, Graver, universal Gröbner bases, and indispensable binomials. Finally, we provide a polarization-type operation for arbitrary
positively graded toric ideals, which preserves all the combinatorial signatures and
the homological properties of the original toric ideal.

Introduction
Toric ideals associated to 0/1 matrices occupy a special place in the world of
toric ideals due to their applications to biology [23], algebraic statistics [21], integer
programming [8], matroid theory [14], combinatorics [18]. They are, by definition,
incidence matrices of hypergraphs, and in the special case when there are only two
nonzero entries in each column they are the incidence matrices of graphs. There is
an abundant literature for toric ideals of graphs, including [16, 20, 25, 26], and the
book [27], while toric ideals of hypergraphs were recently studied in [11] and [18].
Over the last decades, the rich combinatorial structure of toric ideals has been
an anchor for many investigations of their properties. With this literature in mind
in [19] we defined and studied the bouquet ideal of an integer matrix A and its
relationship to the combinatorial and algebraic structure of the toric ideal encoded
by A. Bouquets of a matrix naturally arise from an oriented matroid that records
the dependencies from the Gale transform of A. Specifically, in [19] we showed that
the bouquets of a matrix capture the essential combinatorics of the corresponding
toric ideal, leading to a classification of toric ideals with respect to the bouquet
structure. In addition, the bouquet construction represented the key step for a
combinatorial classification of strongly robust toric ideals and provides a technique
for constructing infinitely many examples of the prominent classes of toric ideals
with rich combinatorics, due to equality of various bases, that include unimodular
([2]), generic ([17]) and robust ideals ([3]).
In light of these results, here we focus on toric ideals of 0/1 matrices and study
their relationship to general toric ideals. Similarly to how the usual reference to
2010 Mathematics Subject Classification. 14M25, 13P10, 05C65, 13D02.
Key words and phrases. Toric ideals, Graver basis, universal Gröbner basis, hypergraphs, minimal generating sets, resolutions.
1

(Markov, Gröbner, Graver) bases of matrices refers to bases of corresponding toric
ideals, throughout the paper we refer to bases of hypergraphs when we think of bases
of toric ideals of incidence matrices of those hypergraphs. We refer the reader to
[22, 19] for general definitions of the above-mentioned bases together with the circuits
and indispensable binomials, to [22, 6] for some equivalent algebraic descriptions,
and to [22, 7] for the general hierarchy among them. As in [19], we will denote the
Graver basis of the matrix A by Gr(A), its set of circuits by C(A), and we recall
that since any element of KerZ (A) can be written as a (conformal) sum of elements
from Gr(A) then one can say that the essential combinatorial information of the
toric ideal of A is provided by Gr(A). For the remainder of the introduction, we
summarize and put into perspective our two main results.
The first main result says, roughly speaking, that the essential combinatorics of
arbitrary toric ideals is encoded by almost 3-uniform hypergraphs, that is, hypergraphs with edges of cardinality at most 3 and having at least one such edge:
Theorem 1 [Theorem 3.2: Hypergraph encodings of arbitrary toric ideals]. Given
any integer matrix A, there exists an almost 3-uniform hypergraph H = (V, E) such
that the toric ideal of the hypergraph IH is strongly robust and there is a bijective
correspondence between the elements of KerZ (A), Gr(A), and C(A) and KerZ (H),
Gr(H), and C(H), respectively.
Thus toric ideals of almost 3-uniform hypergraphs, that is toric ideals of 0/1matrices with at most three 1’s on each column are “as complicated” as any arbitrary
toric ideals with respect to its essential combinatorics, the Graver basis. Recall that
if H is a 0/1 matrix, the toric ideal IH is positively graded, that is, KerZ (H) ∩ Nn =
{0}. In interpreting this result, one has to take into account that by ‘arbitrary toric
ideals’ we do not mean arbitrarily positively graded toric ideals, but arbitrary in the
complete sense. In general, a non-positively graded toric ideal has infinitely many
minimal generating sets of different cardinalities and no indispensable binomials,
see [5, Theorems 4.18, 4.19], and its Graver basis represents the best combinatorial
information one could have on such a toric ideal. However, the fact that Graver
basis of any toric ideal is in a (precise defined way) one-to-one correspondence to
the Graver basis of a hypergraph shouldn’t mislead the reader that the latter one is
easy to describe. Here, it is important to note that while the Graver bases of toric
ideals of graphs have very special form and support structure and are completely
understood, see [20, 25], those of hypergraphs can be quite complicated ([18]) and not
so many things are known. Under these circumstances, “controlling” the essential
combinatorics of an arbitrary toric ideal by toric ideals of hypergraphs, Theorem 1
is the best one could hope for.
Theorem 1 has some interesting consequences, two of which we single out as
universality results for almost 3-uniform hypergraphs. These are also presented in
Section 3 (Corollaries 3.3 and 3.4) along with comments relating them to [9].
The second main result provides a polarization-type operation, saying that if IA
is positively graded then there exists a stable toric ideal of a hypergraph H of same
combinatorial complexity as IA . Stable toric ideals, also introduced and extensively
studied in [19], are those whose all of the bouquets are non-mixed, or in other words
2

for which passing to the bouquet ideal preserves all combinatorial information and,
in the positively graded case, even the homological information.
Theorem 2 [Theorem 4.2: Stable hypergraphs and positively graded toric ideals].
Let IA be an arbitrary positively graded nonzero toric ideal. Then there exists a
hypergraph H such that there is a bijective correspondence between the Graver bases,
all minimal Markov bases, all reduced Gröbner bases, circuits, and indispensable
binomials of IA and IH . Moreover the minimal graded free resolution of IA can be
obtained from the corresponding minimal graded free resolution of IH and viceversa,
and thus all homological data of IA is inherited from IH .
Note by comparison to Theorem 1 that since the toric ideal is positively graded
all of the combinatorics, that is all the distinguished special sets, of the toric ideal is
encoded by the toric ideal of hypergraph. The great bonus offered by this construction is that one can pass from an arbitrary matrix A with KerZ (A) ∩ Nn = {0} to a
0/1 matrix AH by preserving all the homological data, thus this theorem might be
also regarded as a polarization-type operation, see Remark 4.3. Theorem 2 also has
some interesting consequences: in particular, it implies that any classification problem about arbitrary positively graded toric ideals involving equality of bases can be
reduced to a problem about a toric ideal of a hypergraph defined by a 0/1-matrix.
For example, see the conjecture of Boocher et al. [4, Question 6.1] discussed at the
end of Section 4 in Remark 4.4.
The technical backbone of our results are special types of bouquets for 0/1 matrices, called bouquets with bases, that encode the basic building blocks of Graver
bases elements for hypergraphs. Section 2 offers a more technical motivation for this
construction and studies bouquets of 0/1 matrices in detail. Two main definitions
are those of a bouquet with basis and a monomial walk (Definitions 2.1 and 2.7).
We classify such bouquets in Theorem 2.3. There are two technical applications,
which solve two problems for hypergraphs: Theorem 2.10 offers a structural result
generalizing [18], while Proposition 2.13 generalizes a result from [10] and [25] from
graphs to uniform hypergraphs. In particular, Theorem 2.10 and Corollary 2.5 represent the key ingredients in the construction of the hypergraph H from Theorem 1.
For the convenience of the reader, we begin by revisiting the bouquet constructions
and the basic terminology from [19] next.
1. Revisiting the bouquet construction
Let K be a field and A = [a1 , . . . , an ] ∈ Zm×n be an integer matrix of rank r with
the set of column vectors {a1 , . . . , an }. We recall that the toric ideal of A is the
ideal IA ⊂ K[x1 , . . . , xn ] given by
+

−

IA = (xu − xu : u ∈ KerZ (A)),
where u = u+ − u− is the unique expression of an integral vector u as a difference
of two non-negative integral vectors with disjoint support, see [22, Section 4]. To
every integer matrix A one can associate its Gale transform G(A), which is the
n × (n − r) matrix whose columns span the lattice KerZ (A). We will denote the set
of ordered row vectors of the matrix G(A) by {G(a1 ), . . . , G(an )}. The vector ai is
3

called free if its Gale transform G(ai ) is equal to the zero vector, which means that
i is not contained in the support of any minimal generator of the toric ideal IA , or
any element in the Graver basis. A vector which is not free will be called non-free.
Definition 1.1 ([19, Definition 1.1]). The bouquet graph GA of IA is the graph on
vertices {a1 , . . . , an } whose edge set EA consists of those {ai , aj } for which G(ai ) is
a rational multiple of G(aj ) and vice versa. The connected components of the graph
GA are called bouquets.
It follows from the definition that the free vectors of A form one bouquet, which
we call the free bouquet of GA . A bouquet B which is not free is called non-free.
The non-free bouquets are of two types: mixed and non-mixed. A non-free bouquet
is mixed if contains an edge {ai , aj } such that G(ai ) = λG(aj ) for some λ < 0, and
is non-mixed if it is either an isolated vertex or for all of its edges {ai , aj } we have
G(ai ) = λG(aj ) with λ > 0, see [19, Lemma 1.2]. By slight abuse of notation, we
identify vertices of GA with their labels; that is, ai will be used to denote vectors in
the context of A and MA , and vertices in the context of GA .
Example 1.2. Let A be the matrix

3 0
 1 1

 3 0

 7 1
6 0

0
0
1
2
2

4
4
0
4
0

5
5
0
3
0

0
0
0
1
0

1
2
0
1
1





.



A basis for KerZ (A) is given by (1, 2, −3, 3, −3, −6, 0) and (1, 2, −3, −2, 1, 2, 0). Thus
G(a1 ) = (1, 1), G(a2 ) = (2, 2), G(a3 ) = (−3, −3), G(a4 ) = (3, −2), G(a5 ) = (−3, 1),
G(a6 ) = (−6, 2) and G(a7 ) = (0, 0). Therefore the bouquet graph GA with the
vertex set {a1 , . . . , a7 } consists of the four bouquets B1 , . . . , B4 depicted below.
−
•
a1

a3
•
−

+ •a
2
B1

a6
•
•
a4

+
•
a5
B3

B2

•
a7
B4

Here, B1 is mixed, B3 is non-mixed, B2 is non-mixed (since G(a4 ) 6= (0, 0)) and
B4 is the free bouquet (since G(a7 ) = (0, 0)).
For each bouquet B there exist some bouquet-index-encoding vectors cB and
aB which record the bouquet’s types and linear dependencies. For the complete
technical definition of cB we refer the reader to page 9 of [19]; here we simply
summarize how to compute these vectors and offer an example below. If the bouquet
B is free then we set cB ∈ Zn to be any nonzero vector such that supp(cB ) = {i :
ai ∈ B} and with the property that the first nonzero coordinate is positive. For a
non-free bouquet B of A, consider the Gale transforms of the elements in B. All
the elements are nonzero and pairwise linearly dependent, therefore there exists a
4

nonzero coordinate j in all of them. Let gj = gcd(G(ai )j | ai ∈ B) and fix the
smallest integer i0 such that ai0 ∈ B. Then cB is the vector in Zn whose i-th
coordinate is 0 if ai ∈
/ B, and is εi0 j G(ai )j /gj if ai ∈ B, where εi0 j represents the
sign of the integer G(ai0 )jP
. With cB introduced the vector aB (see [19, Definition
1.7]), is defined as aB = ni=1 (cB )i ai ∈ Zm , where (cB )i is the i-th component of
the vector cB .
Detecting the type of a non-free bouquet B is important for our further considerations and we can read this information from the corresponding cB . Indeed, if B is a
non-free bouquet of A, then B is a mixed bouquet if and only if the vector cB has a
negative and a positive coordinate, see [19, Lemma 1.6]. Hence the non-free bouquet
is non-mixed if and only if the vector cB has all nonzero coordinates positive, taking
into account that by definition the first nonzero coordinate of cB is positive.
The matrix AB whose column vectors are the vectors aB corresponding to the
bouquets of A is called the bouquet matrix of A. There is a surprising general
connection between the matrix A and its bouquet matrix AB summarized in the
following theorem.
Theorem 1.3 ([19, Theorem A]). Let A = [a1 , . . . , an ] ∈ Zm×n and its bouquet
matrix AB = [aB1 , . . . , aBs ]. There is a bijective correspondence between the elements of KerZ (A) in general, and Gr(A) and C(A) in particular, and the elements
of KerZ (AB ), and Gr(AB ) and C(AB ), respectively. More precisely, this correspondence is defined as follows: for u = (u1 , . . . , us ) ∈ KerZ (AB ) then B(u) =
cB1 u1 + · · · + cBs us ∈ KerZ (A).
Example 1.4 (Example 1.2, continued). Let A be the matrix from Example 1.2. Let
us compute the bouquet-index-encoding vectors aBi s and cBi s. For cB1 we can choose
j to be either 1 or 2, while i0 = 1. Set j = 1, then g1 = gcd(G(a1 )1 , G(a2 )1 , G(a3 )1 )
and the nonzero coordinates of cB1 are
G(a1 )1
G(a2 )1
G(a3 )1
(cB1 )1 = ε11
= 1, (cB1 )2 = ε11
= 2, (cB1 )3 = ε11
= −3.
g1
g1
g1
Thus the corresponding bouquet vector is cB1 = (1, 2, −3, 0, 0, 0, 0) and consequently
aB1 = 1a1 + 2a2 − 3a3 = (3, 3, 0, 3, 0). Similarly one obtains cB2 = (0, 0, 0, 1, 0, 0, 0),
aB2 = a4 = (4, 4, 0, 4, 0), cB3 = (0, 0, 0, 0, 1, 2, 0), aB3 = 1a5 + 2a6 = (5, 5, 0, 5, 0),
cB4 = (0, 0, 0, 0, 0, 0, 1) and aB4 = a7 . Therefore we obtain the bouquet matrix
AB = [aB1 , aB2 , aB3 , aB4 ] ∈ Z5×4 . Now, the correspondence from Theorem 1.3 works
as follows. For example, to the vector (2, 1, −2, 0) ∈ KerZ (AB ) corresponds the
vector
B((2, 1, −2, 0)) = 2cB1 + 1cB2 − 2cB3 + 0cB4 = (2, 4, −6, 1, −2, −4, 0) ∈ KerZ (A).
Note that the bouquet ideal IAB is also defined by the matrix


3 4 5 0
,
0 0 0 1
and taking into account that aB4 is a free vector, IA is just the extension of the
defining ideal of the monomial curve parametrized by (t3 , t4 , t5 ) in the polynomial
ring in four indeterminates.
5

A subbouquet of GA is an induced subgraph of GA . One easily sees that subbouqets are cliques and maximal ones are the bouquets defined above. A is said to
have a subbouquet decomposition if there exists a family of subbouquets B1 , . . . , Bt
that is pairwise vertex-disjoint, the union of whose vertices equals {a1 , . . . , an }. A
subbouquet decomposition always exists if we consider, for example, the subbouquet decomposition induced by all of the bouquets. We define vectors cB and aB
for each subbouquet B as we did for the bouquets. The matrix associated to such a
subbouquet decomposition is called a subbouquet matrix. Crucially, Theorem 1.3 is
true even if we replace bouquets with proper subbouquets which form a subbouquet
decomposition of A.
Example 1.5 (Example 1.2, continued). The family of subbouquets B1′ , . . . , B5′
depicted below represents a subbouquet decomposition of A. Note that all of the
non-free bouquets B1′ , . . . , B4′ are non-mixed.
a6
•
•
a1

+ •a
2
′
B1

•
a3

•
a4

B′2

B′3

+
•
a5
B′4

•
a7
B′5

There is a natural question of whether there is an inverse construction to the one
described in Theorem 1.3: given a set of vectors a1 , . . . , as and c1 , . . . , cs that can
act as bouquet-index-encoding vectors can we construct a toric ideal IA whose s
(sub)bouquets are encoded by the given vectors? The answer is yes, comprised in
the next theorem, and will be often exploited in the next sections.
Theorem 1.6 ([19, Theorem B]). Let {a1 , . . . , as } ⊂ Zm be an arbitrary set of
vectors. Let c1 , . . . , cs be any set of primitive vectors, with ci ∈ Zmi for some
mi ≥ 1, each having full support and a positive first coordinate. Then, there exists a
matrix A with the subbouquet decomposition B1 , . . . , Bs , such that the ith subbouquet
is encoded by the following vectors: aBi = (ai , 0, . . . , 0) and cBi = (0, . . . , ci , . . . , 0),
where the support of cBi is precisely in the ith block, of size mi .
As a consequence of Definition 1.1 and the fact there are two types of non-free
bouquets, one has the following straightforward combinatorial classification of toric
ideals. A toric ideal may have: 1) all of its non-free bouquets non-mixed; 2) all of its
non-free bouquets mixed, or 3) the non-free bouquets are either mixed or non-mixed.
In the first case, the Theorem below says that all of the combinatorial information
is preserved when passing from IA to IAB . In addition, homological properties are
also preserved; see [19, Theorem 3.11].
Theorem 1.7 ([19, Theorem C]). Let IA be a stable toric ideal, that is all of the
non-free bouquets of A are non-mixed. Then the bijective correspondence between
the elements of KerZ (A) and KerZ (AB ) given by u 7→ B(u), is preserved when we
restrict to any of the following sets: Graver basis, circuits, indispensable binomials,
minimal Markov bases, reduced Gröbner bases (universal Gröbner basis).
6

This result holds in a more general setting, as explained in detail in [19, Section
3]. For example, even if IA is not stable, one cand find a (maximal) subbouquet decomposition such that all of its subbouquets are non-mixed, and whose subbouquet
matrix AB has the property that the bijective correspondence between KerZ (A) and
KerZ (AB ) from Theorem 1.7 is preserved. In particular, Example 1.5 gives such a
maximal subbouquet decomposition of the matrix A from Example 1.2.
The second class of toric ideals, described above, and whose bouquets are all
mixed have the following nice property.
Proposition 1.8 ([19, Corollary 4.4]). Suppose that every non-free bouquet of A is
mixed. Then IA is strongly robust, i.e. the following sets coincide:
• the Graver basis of A,
• the universal Gröbner basis of A,
• any reduced Gröbner basis of A,
• any minimal Markov basis of A.
However, despite the fact that almost all the examples of strongly robust ideals,
previously known in the literature, had all of the bouquets mixed, there are examples of strongly robust ideals which have both types of non-free bouquets, see [19,
Example 4.3. b)]. This lead us to raise the following question: Is it true that a
strongly robust ideal has at least one mixed bouquet?, see [19, Question 4.6]. Sullivant answered this question in the affirmative in [24] for the particular case of
codimension 2 strongly robust toric ideals.
2. Hypergraphs and bouquets with bases
As this section consists of three parts, we begin with a ‘roadmap’ to point out
the main definitions and results. As described in the Introduction, this section is
concerned with toric ideals of 0/1 matrices, which are, by definition, incidence matrices of hypergraphs. To understand this class of toric ideals, we need two main
definitions: a bouquet with basis in Definition 2.1, lacking in the previous literature and a monomial walk in Definition 2.7, recovering the meaning of monomial
walks on graphs from [20], [27]. The first two subsections are motivated by [18,
Problem 6.2], and they, essentially, partially solve its generalization. Theorem 2.3
classifies bouquets with bases, which are either free or mixed subbouquets, while the
running example shows its implications on identifying and constructing elements in
the Graver basis of a hypergraph. Proposition 2.10 shows that certain hypergraphs
based on a sunflower are bouquets with bases and, in particular, recovers the main
structural result of [18]. As another application of bouquets with bases, Proposition 2.13 generalizes a result by [10] and [25] for graphs to uniform hypergraphs and
showing that the universal Gröbner and Graver bases differ for complete uniform
hypergraphs with enough vertices. However, in general, there exist hypergraphs
that do not admit such a subbouquet structure. In this case, we provide general
constructions in Sections 3 and 4.
Let H = (V, E) be a finite hypergraph on the set of vertices V = {x1 , . . . , xm }
with edge set E = {E1 , . . . , En }, where each Ei is a subset of {x1 , . . . , xm }. When
7

|Ei | = 2 for all i and Ei 6= Ej for all i 6= j, we have a finite simple graph, and
we will specialize to this case to recall results about graphs. We denote by α E the
support (column) vector of an edge E, and thus the toric ideal IH is the toric ideal
α E1 , . . . , α En ]. Hereafter, for ease of notation, various bases of IH
of the matrix [α
will be referred to as bases of H; the reader may simply keep in mind that the
underlying toric matrix is the incidence matrix of the hypergraph H; for example,
Gr(H) := Gr(AH ) where AH is the vertex-edge incidence matrix of H.
2.1. Bouquets with bases. Let H = (V, E) be a hypergraph and U ⊂ V . We
define the multiset UE = {E ∩ U|E ∈ E, E ∩ U 6= ∅} and the set EU = {E ∈
E|E ∩ U 6= ∅}. Note that the multiset UE and the set EU have the same number
of elements: EU is the set of edges of H that intersect the vertex set U, while UE
consists of their restrictions to U.
Definition 2.1. The set of edges EU of H is called a bouquet with basis U ⊂ V if
the toric ideal of the multi-hypergraph (U, UE ) is principal, generated by an element
+
−
ec −ec with supp(c) = EU , and such that the first nonzero coordinate of c = c+ −c−
is positive. Here the toric ideal of (U, UE ) is contained in the polynomial ring with
variables indexed by the non-empty subsets ei := Ei ∩ U.
n
Moreover, for a bouquet with basis EU , we define the vector cEU ∈
PZ such that
(cEU )E = cE for any E ∈ EU and 0 otherwise, and the vector aEU = E∈EU cE α E ∈
Zm . Here cE denotes the coordinate of c corresponding to the edge E, and note
from the definition of c that cE 6= 0 for all E ∈ EU .
The following examples capture the subtleties of this definition and its similarity
to Definition 1.1.
Example 2.2. a) Consider the hypergraph H = (V, E) from Figure 1, with the set
of vertices V = {x, v1 , . . . , v22 } and whose set of edges E consists of the following 20
edges: E1 = {x, v1 , v2 }, E2 = {x, v3 , v4 }, E3 = {x, v5 , v6 }, E4 = {v1 , v3 , v5 }, E5 =
{v2 , v4 , v6 }, E6 = {x, v7 , v8 }, E7 = {x, v9 , v10 }, E8 = {x, v11 , v12 }, E9 = {x, v13 , v14 },
E10 = {v7 , v8 , v9 }, E11 = {v10 , v11 , v13 }, E12 = {v12 , v14 }, E13 = {x, v15 , v16 }, E14 =
{x, v17 , v18 }, E15 = {x, v19 , v20 }, E16 = {x, v21 , v22 }, E17 = {v16 , v18 , v20 }, E18 =
{v15 , v19 }, E19 = {v17 , v19 , v21 }, E20 = {v20 , v22 }.
The first bouquet with basis EU1 has five edges, the basis U1 is the set {v1 , . . . , v6 },
the vector c1 corresponds to the binomial generator e1 e2 e3 − e4 e5 of the toric ideal
of (U1 , U1E ), and thus cEU1 = (1, 1, 1, −1, −1, 0, . . . , 0) ∈ Z20 and
aEU1 = α E1 + α E2 + α E3 − α E4 − α E5 = (3, 0, . . . , 0) ∈ Z23 .
The second bouquet with basis EU2 has seven edges, the basis U2 is the set
{v7 , . . . , v14 }, the vector c2 corresponds to the binomial generator e6 e7 e8 e9 −e10 e11 e12
of the toric ideal of (U2 , U2E ), and thus the encoding vectors are
cEU2 = (0, 0, 0, 0, 0, 1, 1, 1, 1, −1, −1, −1, 0, . . . , 0) ∈ Z20
and
aEU2 =

9
X
i=6

α Ei −

12
X

α Ej = (4, 0, . . . , 0) ∈ Z23 .

j=10

8

The third bouquet with basis EU3 has eight edges, the basis U3 = {v15 , . . . , v22 },
the vector c3 corresponds to the binomial generator e13 e14 e215 e16 − e17 e18 e19 e20 of the
toric ideal of (U3 , U3E ), and thus cEU3 = (0, . . . , 0, 1, 1, 2, 1, −1, −1, −1, −1) ∈ Z20
and
20
X
αE15 + α E16 −
aEU3 = α E13 + α E14 + 2α
α Ej = (5, 0, . . . , 0) ∈ Z23 .
j=17

On the other hand, if A = AH is the incidence matrix of the hypergraph H with
columns α E1 , . . . , α E20 , then GA has three mixed non-free bouquets B1 , B2 , B3 . More
precisely, the first bouquet B1 corresponds to the vectors α E1 , . . . , α E5 , the second
bouquet B2 to the vectors α E6 , . . . , α E12 , and the third bouquet B3 to the vectors
α E13 , . . . , α E20 . Moreover, it turns out that cBi = cEUi and aBi = aEUi for all i.
v2

v4

•

v1

v8

•

•
•
•

v7

•

v3

v5

•

x

x

•
•
•

•
•
•

v10

v13

v11

•

v9

v16
v15

•

v12

•

v14

x

•
•
•

•
•
•

v17
v19

v21

•
•
•

v18
v20
v22

v6

Figure 1. Bouquets with bases EU1 , EU2 , EU3 .
(b) The tetrahedron is an example of a bouquet with basis, and the basis can be
chosen to be any facet. Let V = {v1 , v2 , v3 , v4 } and E = {E1 = {v2 , v3 , v4 }, E2 =
{v1 , v3 , v4 }, E3 = {v1 , v2 , v4 }, E4 = {v1 , v2 , v3 }}. If we consider as basis the set U1 =
{v1 , v2 , v3 } then U1E = {e1 = {v2 , v3 }, e2 = {v1 , v3 }, e3 = {v1 , v2 }, e4 = {v1 , v2 , v3 }}
+
−
and the toric ideal of (U1 , U1E ) is generated by the element ec − ec = e1 e2 e3 − e24 ,
with c = (1, 1, 1, −2). Therefore, cEU1 = (1, 1, 1, −2) and aEU1 = α E1 + α E2 +
αE4 = (0, 0, 0, 3). The same example has four different representations as a
α E3 − 2α
bouquet with basis U, each one of them having pairwise distinct vectors cEU and
aEU , respectively. More precisely, if U2 = {v1 , v2 , v4 } then cEU2 = (1, 1, −2, 1) and
aEU2 = (0, 0, 3, 0), if U3 = {v1 , v3 , v4 } then cEU3 = (1, −2, 1, 1) and aEU3 = (0, 3, 0, 0),
and if U4 = {v2 , v3 , v4 } then cEU4 = (2, −1, −1, −1) and aEU4 = (−3, 0, 0, 0). Note
αEi ) are zero vectors for all i.
that IH is the zero ideal and the Gale transforms G(α
Therefore, the bouquet graph of IH has only the free bouquet B consisting of all
vertices α E1 , . . . , α E4 . In particular, by definition of cB and aB we observe that we
can choose these vectors to be any of the 4 pairs of vectors obtained before as cEU
and aEU .
Given the apparent similarity with Definition 1.1 and in light of the two situations discussed in Example 2.2, one would expect a certain relationship between a
bouquet with basis of a hypergraph H and a bouquet of its incidence matrix. Even
more, one may ask whether cEU and aEU , the encoding vectors of a bouquet with
basis, are analogous to cB and aB as defined in Section 1. The following result
clarifies the ‘bouquet with basis’ terminology. As we will see, a bouquet with basis
corresponds to a subbouquet of the incidence matrix of the hypergraph, where the
9

correspondence is the natural one associating to a set of edges of a hypergraph the
set of corresponding support column vectors of its incidence matrix. Thus, from
now on, by abuse of notation, we will identify the bouquet with basis EU with the
corresponding subbouquet of the incidence matrix. Furthermore, we also note that
cEU matches the definition of cB from Section 1, and the same holds for aEU .
Theorem 2.3. A bouquet with basis of the hypergraph H = (V, E) is either a free
subbouquet or a mixed subbouquet of the incidence matrix of H.
Proof. Let EU be a bouquet with basis for some U ⊂ V , and set EU = {E1 , . . . , Es }.
Furthermore, denote by M ∈ Zm×n the incidence matrix of the hypergraph (V, E).
We may arrange M so that its rows are indexed first by vertices in U and then
vertices in V \U, while its columns are indexed first by the edges E1 , . . . , Es and next
by the remaining edges, if any. Note that the submatrix of M corresponding to the
rows indexed by U and the first s columns, denoted by MU , is the incidence matrix of
the multi-hypergraph (U, UE ), while the submatrix of M corresponding to the rows
indexed by U and the rest of the columns is 0. Finally, denote by G = (gij ) ∈ Zn×r
the Gale transform of M, and according to the labeling of the columns of M its first
αE1 ), . . . , G(α
α Es ). By definition of the Gale transform, column j of G
s rows are G(α
is in the kernel of M. Therefore (g1j , . . . , gsj ) ∈ Ker MU and since EU is a bouquet
with basis then (g1j , . . . , gsj ) is a multiple of c = (cE1 , . . . , cEs ). Thus gij = λj cEi for
αEi ) = cEi (λ1 , λ2 , . . . , λr ) for all i ∈ {1, . . . , s}.
all i, j and implicitly we obtain G(α
Then it follows at once that α E1 , . . . , α Es belong to the same subbouquet B of M.
In addition, since supp(c) = EU then cEi 6= 0 for all i ∈ {1, . . . , s}. Thus there are
α Ei ) = 0 for all i or G(α
αEi ) 6= 0 for all i. In the first case we
two possibilities: G(α
obtain that B is a free subbouquet, while in the second B is a non-free subbouquet.
Moreover, the toric ideal of (U, UE ) being positively graded implies that the vector
cEU has at least one positive and one negative coordinate, and by the description
of a non-free mixed bouquet B in terms of cB from Section 1, we obtain that B is
mixed.

Let us point out that a bouquet with basis can be a proper subbouquet of a
bouquet. Indeed, let A′ be the submatrix of the incidence matrix of the hypergraph
H from Example 2.2(a) corresponding to the first twelve columns. As it was already
noticed the first five edges form a bouquet with basis, and the other seven edges
form another bouquet with basis. In contrast, one can easily see that the bouquet
graph of A′ has one mixed bouquet - consisting of all column vectors of A′ , and thus
the two bouquets with bases are proper subbouquets.
The previous theorem shows that bouquets with bases are always subbouquets.
The natural converse question arises: Can there exist (sub)bouquets of the incidence
matrix of a hypergraph which are not bouquets with bases? The answer is yes, and
as an example consider the complete graph K4 on four vertices, whose incidence
matrix is the submatrix corresponding to the first 6 columns of A from [19, Example
1.4]. As it was shown there K4 has three non-mixed bouquets, each one being an
edge. On the other hand, K4 does not have any bouquets with bases, since by
10

Theorem 2.3 this would imply the existence either of a mixed non-free subbouquet
or a free subbouquet.
The main consequence of Theorem 2.3 is that if the edge set of a hypergraph
H can be partitioned into bouquets with bases, then the toric ideal IH is easier to
describe, via Theorem 1.3. The following example captures this remark.
Example 2.4 (Example 2.2(a), continued). The hypergraph H has three bouquets
with bases EU1 , EU2 , EU3 which partition E. Therefore, the subbouquet ideal of AH is
given by the toric ideal of the matrix whose columns are aEU1 = (3, 0, . . . , 0), aEU2 =
(4, 0, . . . , 0), aEU3 = (5, 0, . . . , 0) ∈ Z23 , which is the same as the toric ideal of the
monomial curve A = (3 4 5). Computing with [1] we obtain that the Graver basis of
IA consists of seven elements (4, −3, 0), (1, −2, 1), (3, −1, −1), (2, 1, −2), (5, 0, −3),
(1, 3, −3), (0, 5, −4). Therefore, by Theorem 1.3, the Graver basis of the toric ideal
of the hypergraph consists of seven elements. For example, (1, −2, 1) corresponds
to the following Graver basis element of IH :
cEU1 −2cEU2 + cEU3 = (1, 1, 1, −1, −1, −2, −2, −2, −2, 2, 2, 2, 1, 1, 2, 1, −1, −1, −1, −1)
and it encodes the binomial
2
2
2
2
E1 E2 E3 E10
E11
E12
E13 E14 E15
E16 − E4 E5 E62 E72 E82 E92 E17 E18 E19 E20 .

This binomial corresponds to the primitive monomial walk (see Definition 2.7) depicted in Figure 2, where the three copies of the vertex x should be identified, but
are shown separately for better visibility.
•
•

•
•
•

• x

•
•
x •

•
•
•
•

•

•

•
•
x •

•
•
•
•

•

•
•

Figure 2. A primitive monomial walk of H
In particular, combining Theorem 2.3 with Proposition 1.8 we obtain the following:
Corollary 2.5. If the set of edges of a hypergraph H can be partitioned into bouquets
with bases then IH is strongly robust.
Remark 2.6. As a second application of Proposition 1.8 we give a new class of
hypergraphs which satisfy the conclusion of Corollary 2.5, and whose building blocks
are not necessarily bouquets with bases. Let H = (V, E) be a hypergraph such that
there exists U ⊂ V with the property that U ∩ E 6= ∅ for all E ∈ E and every vertex
of U belongs to exactly two edges. Denote by U = {v1 , . . . , vt } ⊂ {v1 , . . . , vm } = V ,
E = {E1 , . . . , En } and let B be a non-free bouquet of AH (if such a B does not exist
then IH = 0 and we are done). This implies that there exists an i ∈ [n] such that
α Ei ∈ B. By definition of H there exists vj ∈ Ei ∩ Ek with j ≤ m and k 6= i. Then
11

the vector u ∈ Zm , whose only nonzero coordinate is 1 on the j-th position satisfies
the following equalities
u · α Ei = 1, u · α Ek = 1, u · α El = 0 for all l 6= i, k.
α Ei ) +
Therefore the vector cik := (u · α E1 , . . . , u · α En ) has support {i, k} and G(α
α Ek ) = 0, see [19, Remark 1.3]. Since B is non-free, G(α
α Ei ) = −G(α
α Ek ) 6= 0, and
G(α
thus B is mixed. Therefore by Proposition 1.8 we obtain the desired conclusion, and
in particular we recover [11, Proposition 4.5]. Imposing in the definition of H that
U = V , thus making H a 2-regular hypergraph, we also recover [11, Proposition
4.2].
Of course, general hypergraphs do not admit a partition of their edge sets into
bouquets with bases, let alone mixed subbouquets, as it was shown earlier for K4 .
Infinitely many such examples can be constructed; see Section 4 for details.
2.2. Sunflowers. In this subsection we identify some interesting examples of bouquets with bases, namely, the so-called ‘sparse bouquets’ from [18] (of which there
was no formal definition!). These hypergraphs are built on sunflowers. The sunflower is highly structured and useful in the hypergraph literature; for example, it
is guaranteed to occur in hypergraphs with large enough edge sets, independently
of the size of the vertex set (see e.g. [13].)
General properties of bouquets with bases studied in the previous subsection allow us to not only recover the theorems about existence of Graver basis elements,
but also to: 1) describe completely their Graver basis elements by identifying the
bouquet ideal, thus the aB ’s, 2) show that these sunflowers are actually strongly
robust, and 3) identify Graver basis elements of any hypergraphs which have sunflowers as subhypergraphs. In addition, unlike [18], we do not specialize to uniform
hypergraphs.
In Section 1 it was recalled in Theorem 1.3 that the bouquet graph of A encodes
the Graver basis of IA . On the other hand, [18] showed that the Graver basis of IH
is encoded by primitive monomial walks on the hypergraph. The two concepts are
consolidated in the following definition.
Definition 2.7. Let (Eblue , Ered ) be a multiset collection of edges of H = (V, E). We
denote by degblue (v) and degred (v) the number of edges of Eblue and Ered containing
the vertex v, respectively. We say that (Eblue , Ered ) are balanced on U ⊂ V if
degblue (v) = degred (v) for each vertex v ∈ U.
The vector aEblue ,Ered = (degblue (v) − degred (v))v∈V is called the vector of imbalances of (Eblue , Ered ) and its support is contained in the complement of U in V . If
aEblue ,Ered = 0 then we say that (Eblue , Ered) is a monomial walk 1.
Q
Q
Every monomial walk encodes a binomial fEB ,ER = E∈EB E − E∈ER E in IH .
A monomial walk (EB , ER ) is said to be primitive if there do not exist proper submultisets E ′ B ⊂ EB and E ′ R ⊂ ER such that (E ′ B , E ′ R ) is also a monomial walk. The
1For

completeness, note that the support of a monomial walk, considered as a multi-hypergraph,
was called a monomial hypergraph in [18], but this definition does not make an appearance in our
results. Instead, we focus on bouquets with bases and the corresponding UE and EU .
12

toric ideal IH is generated by binomials corresponding to primitive monomial walks,
see [18, Theorem 2.8].
Remark 2.8. Let H = (V, E) be a hypergraph, U ⊂ V such that EU is a bouquet
with basis. Since the toric ideal of the (multi)hypergraph (U, UE ) is principal gen+
−
erated by ec − ec with supp(c) = EU the primitive monomial walk (UEblue , UEred )
encoded by (U, UE ) is the following: UEblue is the multiset consisting of the edges
e1 , ei2 , . . . , eir with multiplicities c1 , ci2 , . . . , cir , respectively, while UEred is the multiset consisting of the edges eir+1 , . . . , eit with multiplicities −cir+1 , . . . , −cit , respectively. Here c1 , ci2 , . . . , cir are the positive coordinates of c, while cir+1 , . . . , cit are
the remaining coordinates of c, all negative. If we consider Eblue to be the multiset
collection of edges E1 , Ei2 , . . . , Eir with multiplicities c1 , ci2 , . . . , cir respectively, and
Ered the multiset collection of edges Eir+1 , . . . , Eit with multiplicities −cir+1 , . . . , −cit
respectively then (Eblue , Ered ) are balanced on U. Moreover, notice that the vector of
imbalances aEblue ,Ered equals aEU , and as explained before cEU determines (Eblue , Ered).
For example, considering the bouquet with basis EU3 from Example 2.2(a), the toric
ideal of (U3 , U3E ) was generated by e13 e14 e215 e16 − e17 e18 e19 e20 , and thus the corresponding Eblue and Ered are depicted with the corresponding colors in the rightmost
part of Figure 2.
Recall that a matching on a hypergraph H = (V, E) is a subset M ⊂ E of pairwise
disjoint edges. A matching is called perfect if it covers all the vertices of the hypergraph. A hypergraph is said to be connected if its primal graph is connected, where
the primal graph has the same vertex set as the hypergraph and an edge between
any two vertices contained in the same hyperedge.
A hypergraph H = (V, E) is a sunflower if, for some vertex set C, Ei ∩ Ej = C
for all edges Ei , Ej ∈ E, i 6= j and C ( E for all edges E ∈ E. The set of vertices of
C is called the core of the sunflower, and each Ei is called a petal. A matched-petal
sunflower2 is a hypergraph consisting of a sunflower and a perfect matching on the
non-core vertices. Note that the set of edges of a matched-petal sunflower partitions
into the edges of sunflower, i.e. petals, and the edges of the matching, while its set of
vertices is just the set of the vertices of the sunflower. A matched-petal sunflower H
is called connected if the (multi)hypergraph H − C is connected, where C represents
the core vertices. Here, H − C is the (multi)hypergraph consisting of the restricted
sunflower: (V \ C, E ′) where E ′ = {E \ C : E ∈ E}, and the edges of the perfect
matching of H.
A matched-petal partitioned-core sunflower is a hypergraph H consisting of a collection of vertex-disjoint sunflowers S1 , S2 , . . . , Sl and a perfect matching on the
union of non-core vertices, that is ∪i (Si \ Ci ). A matched-petal partitioned-core
sunflower is called connected if H − C is connected, where C = ∪i Ci . A matchedpetal relaxed-core sunflower is a hypergraph H consisting of a collection of sunflowers
2 Let us also relate this definition to [18], where the authors defined a monomial sunflower :
the multi-hypergraph with aEblue ,Ered = 0 whose support is a matched-petal sunflower. However,
there is an important distinction: not every matched-petal sunflower is the support of a monomial
sunflower. (As a monomial sunflower is an example of a monomial hypergraph, this definition also
isn’t used in this manuscript.)

13

S1 , S2 , . . . , Sl with cores C1 , . . . , Cl respectively, which may only intersect at their
cores, and a perfect matching on the union of the non-core vertices of the sunflowers.
A matched-petal relaxed-core sunflower is called connected if the (multi)hypergraph
H − C is connected, where C = ∪i Ci .
Remark 2.9. The definitions above resemble various monomial walks (based on
various types of sunflowers) introduced in [18]. In contrast, here we allow hypergraphs to be non-uniform and consider the supporting sunflowers as sets instead of
multisets.
As far as the standard terminology is concerned, note that a matched-petal sunflower is a particular case of matched-petal partitioned-core sunflower, which in turn
is a particular case of matched-petal relaxed-core sunflower. Each of the first two
subhypergraphs from Figure 1 are connected matched-petal sunflowers, while the
third one is not. If we identify the vertices x1 , x2 and x3 from Figure 3 then the
hypergraph consisting of the three depicted connected matched-petal sunflowers is
a non-connected matched-petal sunflower.
Theorem 2.10. Every connected matched-petal relaxed-core sunflower is a bouquet
with basis, where the basis consists of the non-core vertices.
Proof. Let H be a connected matched-petal relaxed-core sunflower consisting of l
sunflowers S1 , . . . , Sl with Ci being the core vertices of sunflower Si for all i, and
let U = ∪li=1 Si \ Ci . Note that by definition the set of edges E of H partitions into
the set of petals of the sunflowers S1 , . . . , Sl , labeled E1 , . . . , Et , and the edges of
the matching, labeled Et+1 , . . . , Ek . In order to prove that EU is a bouquet with
basis, we note first that the vector c = (1, 1, . . . , 1, −1, . . . , −1) ∈ Zk corresponds to
a binomial in the toric ideal of (U, UE ), where the number of 1’s equals the number
of petals, while the number of −1’s equals the number of edges of the matching.
Assume that u = (u1 , . . . , ut , ut+1 , . . . , uk ) is an arbitrary vector corresponding to a
binomial in the toric ideal of (U, UE ). It remains to prove that u1 = · · · = ut and
ut+1 = · · · = uk = −u1 . Let E, E ′ ∈ UE be two different edges, restrictions of two
petals and thus non-empty, and let v ∈ E, v ′ ∈ E ′ .
Since H is connected, there exists a path in the primal graph of (U, UE ) from v to
v ′ , that is v = v0 , v1 , . . . , vr = v ′ . We construct inductively a sequence of edges of UE :
let s1 be the largest number such that vs1 ∈ E := E1 . Since E, E ′ are restrictions
of petals then E ∩ E ′ = ∅, and thus s1 < r. By definition of s1 , there exists an
edge of UE , say E2 , such that vs1 ∈ E1 ∩ E2 . Let s2 be the largest number such that
vs2 ∈ E2 . If s2 = r then E ′ = E2 and we stop, otherwise we continue. In this way
we obtain a sequence of edges E = E1 , . . . , Ep = E ′ of UE for some p ≥ 2.
Denote by uij the coordinate of u corresponding to Ej for all j = 1, . . . , p (that is
|uij | is the exponent of Ej in the binomial). Since the binomial corresponding to u
is in the toric ideal of (U, UE ), every vertex of U is balanced. Moreover, since every
vertex of U belongs to exactly two edges, vsj being balanced implies that uij+1 = −uij
for all j < p. Thus we obtain uij = (−1)j+1 u1 for all j = 1, . . . , p, and in particular,
if Ej is the restriction of a petal then Ej+1 is an edge of a matching. Therefore,
we obtain that for any distinct edges E, E ′ of UE the corresponding coordinates of
14

u are either equal or negatives of each other, with equality holding if and only if
E, E ′ are simultaneously either restrictions of petals or edges of the matching M.
Hence we get that u = (u1 , . . . , u1 , −u1 , . . . , −u1 ), which implies that the toric ideal
+
−
of (U, UE ) is principal, and generated by ec − ec . Thus EU is a bouquet with basis,
as desired.

Since the connected components of a matched-petal relaxed-core sunflower are
connected matched-petal relaxed-core sunflowers, then by Theorem 2.10 and Corollary 2.5 we obtain the following:
Proposition 2.11. Let H be a matched-petal relaxed-core sunflower. Then IH is
strongly robust.
In particular, one recovers [18, Theorem 4.12] and implicitly [18, Proposition 4.5]
and [18, Proposition 4.9]. To see this, we first identify the subbouquets of a matchedpetal relaxed-core sunflower H and their corresponding a-vectors. If H1 , . . . , Ht are
the connected components of H, that is matched-petal relaxed-core sunflowers with
the sets of core vertices C1 , . . . , Ct , then denote by C = {v1 , . . . , vs } the union ∪i Ci
of core vertices of H. Moreover, we label the edges such that petals are labeled first,
while the edges of the matching are labeled last. By Theorem 2.10, H1 , . . . , Ht are
bouquets with bases, the bases are the sets of non-core vertices, and the vectors
aHi can be computed as vectors of imbalances induced by cHi , as explained in
Remark 2.8. Therefore, if we label the rows of the incidence matrix of H first
according to the vertices from C, then it follows from Remark 2.8 that for each j
the vector aHj has at most the first s components nonzero and for each i = 1, . . . , s
the i-th coordinate of aHj is equal to dij , where dij is the number of petals of Hj
containing the vertex vi . Now it is obvious via Theorem 1.3 that IH 6= 0 if and only
if ID 6= 0, where D is the matrix (dij ) ∈ Zs×t , and their Graver basis are in bijective
correspondence, and this is essentially the content of [18, Theorem 4.12].
Example 2.12. Consider H to be the matched-petal relaxed-core sunflower whose
three connected components H1 , H2 , H3 are depicted below, and with cores Ci =
{xi } for i = 1, 2, 3. Note that each Hi is a connected matched-petal sunflower, and
thus a bouquet with basis by Theorem 2.10. If xi 6= xj for all i 6= j then the union of
core vertices is C = {x1 , x2 , x3 } and the matrix (dij ) ∈ Z3×3 is the displayed matrix
D1 . We recall from the previous paragraph that dij is the number of petals of Hj
containing xi . Thus in this case IH = 0.




3 0 0

3 4 0


0 4 0
D1 =
D2 =
D3 = 3 4 5
0 0 5
0 0 5

If x1 = x2 6= x3 then the union of core vertices is C = {x1 , x3 } and we obtain the
corresponding matrix D2 ∈ Z2×3 . Therefore in this case IH 6= 0 is principal. Finally,
if x1 = x2 = x3 then C = {x1 } and the matrix D3 is given above.

Specializing the previous discussions to a matched-petal sunflower H with t ≥ 1
connected components one obtains the following classification. The toric ideal IH =
0 if and only if t = 1, that is H is a connected matched-petal sunflower. The toric
15

•
•

•
•
•

• x1

•
•
x2 •

•
•
•
•

•
•

•

•
•
x3 •
•
•

•
•
•
•

•
•

Figure 3. Matched-petal sunflowers
ideal IH 6= 0 if and only if t > 1, in which case the subbouquet ideal is just the toric
ideal of the monomial curve (d1 . . . dt ), where di represents the number of petals of
the i-th connected component, containing the core.
2.3. Graver basis elements of hypergraphs. In cases of interest, it may happen
that all (or almost all) bouquets are singletons, seemingly implying that the bouquet
construction does not offer anything. However, this is not the case since by [22,
Proposition 4.13] if we restrict to a submatrix C of A obtained by deleting some
of the columns of A then the Graver basis, universal Gröbner basis and circuits
of C are included in the corresponding ones of A. Based on this and the bouquet
techniques we construct in Proposition 2.13 an element in the Graver basis of the
uniform complete hypergraph with large enough number of vertices, which is not in
the universal Gröbner basis.
In [10, 25] it was shown that the universal Gröbner basis and the Graver basis of
the toric ideal of the complete graph Kn are identical for n ≤ 8 and differ for n ≥ 9.
As one application of the bouquet technique, we show that the universal Gröbner
basis and the Graver basis of the toric ideal of the complete d-uniform hypergraph
Knd differ for n ≥ (d+1)2 , by giving a non trivial example of an element in the Graver
basis which does not belong to the universal Gröbner basis. First note that all of
the bouquets of the complete d-uniform hypergraph Knd , for large n, are singletons.
Then, restricting to a subhypergraph H of Knd , as explained before, we can apply
the bouquet techniques to find an element from the Graver basis of H that belongs
also to the Graver basis of Knd .
We consider a hypergraph Hd+1 = (V, E) with (d + 1)2 vertices V = {vij |1 ≤ i, j ≤
d + 1} and (d + 2)(d + 1) edges: let Ej = {vk1 |1 ≤ k ≤ d + 1, k 6= j} for 1 ≤ j ≤ d + 1
and Eij = {vik |1 ≤ k ≤ d + 1, k 6= j} for 1 ≤ i, j ≤ d + 1. The hypergraph H4 , for
d = 3, is depicted in Figure 4.
Note that Hd+1 is a subhypergraph of Knd for n ≥ (d + 1)2 . In addition the set of
edges of Hd+1 partitions into d+1 bouquets with bases EU1 , . . . , EUd+1 and d+1 single
edges E1 , . . . , Ed+1 . Here EUi = {Eij |1 ≤ j ≤ d + 1} and Ui = {vij |2 ≤ j ≤ d + 1}
for all i = 1, . . . , d + 1, while the principal
generator of the toric ideal of the hyQ
pergraph (Ui , UiE ) is the binomial j6=1 eij − ed−1
i1 , see Definition 2.1. Moreover,
the incidence matrix of Hd+1 has the rows indexed by the vertices in the following
way: v11 , v21 , . . . , vd+1,1 , v12 , v22 , . . . , vd+1,d+1 and the columns indexed by the edges
in the following way E11 , E12 , . . . , E1,d+1 , E21 , E22 , . . . , Ed+1,d+1 , E1 , . . . , Ed+1 . With
16

respect to this labeling of the edges and similarly to the computations from Example 2.2(b) we obtain that cEU1 = (d − 1, −1, . . . , −1, 0, . . . , 0), cEU2 = (0, d −
1, −1, . . . , −1, 0, . . . , 0), and so on cEUd+1 = (0, . . . , 0, d − 1, −1, . . . , −1, 0) are vectors of Z(d+2)(d+1) , where 0 ∈ Zd+1 represents the vector with all coordinates zero.
2
By Remark 2.8 the vector aEUi ∈ Z(d+1) has all coordinates zero except the one
corresponding to the vertex vi1 , which equals −d. For the singleton subbouquets
E1 , . . . , Ed+1 , the encoding vectors are: cE1 = (0, . . . , 0, 1, 0, . . . , 0), . . . , cEd+1 =
(0, . . . , 0, 0, . . . , 0, 1), while aEi = α Ei for all i = 1, . . . , d + 1.
v13

v14

v12
v24

v44

v11
v21

v43

v23
v41
v31

v22
v32

v42
v34

v33

Figure 4. H4
For the rest of this subsection we use for simplicity the binomial representation
for an element in the toric ideal of a hypergraph instead of the vector representation.
It is easy to see that the following three types of binomials belong to the toric ideal
of the complete d-uniform hypergraph Knd : a) d + 1 binomials of the form
Y
Y
d−1
gi := Eid−1
Eij − Ei1
Ej ,
j6=1

j6=i

b) d + 1 binomials of the form
YY

hi :=

Eij − Eld

i6=l j6=1

and c) one binomial of the form
YY
i

Eij −

j6=1

Y

d−1
Ei1
,

i6=l

Y

Ei

i

Y

d−1
Ei1
.

i

Furthermore, it can be shown that they are all elements of the Graver basis of Knd ,
although we will prove next just for the last binomial.
Proposition 2.13. The universal Gröbner basis of the toric ideal of the complete
d-uniform hypergraph Knd differs from the Graver basis for n ≥ (d + 1)2 .
Proof. First we prove that the binomial
Y Y
YY
d−1
Eij −
Ei
Ei1
f=
i

j6=1

i

17

i

does not belong to the universal Gröbner basis of the toric ideal of the complete
d-uniform hypergraph Knd . We argue by contradiction. Assume that there exists a
monomial order > such that the binomial
f belongs to the reduced
basis
Q Gröbner
Q d−1
d−1 Q
with respect to the order >. Since Ei1
E
divides
properly
E
E
j6=i j
i i
i i1 , it
follows that
Y
Y
d−1
(1)
Eid−1
Eij > Ei1
Ej .
j6=1

j6=i

d−1 Q
Indeed, if this is not the case then in< (gi ) = Ei1
E . From the previous
Q
Q d−1j6=i j
divisibility it follows that: 1) if in< (f ) = Qi Q
Ei i Ei1 then we contradict that f
is in the Gröbner basis, or 2) if in< (f ) = i j6=1 Eij then we contradict that f is
reduced.QThus
(1).
Q we obtain the inequality
Q Q
Also i6=l j6=1 Eij divides i j6=1 Eij , and similarly to the proof of (1) it can
be shown that
Y
YY
d−1
(2)
Ei1
.
Eij < Eld
i6=l

i6=l j6=1

Taking the product of inequalities (1) when i runs from 1 to d + 1 and canceling
common terms we obtain
YY
Y Y
d−1
Eij >
Ei
Ei1
.
i

j6=1

i

i

Similarly, taking the product of inequalities (2) we obtain
Y Y
YY
d−1 d
Eij )d < ( Ei
Ei1
) ,
(
i

a contradiction.
In order to prove that
enough to prove via [22,
its subhypergraph Hd+1 .
with bases EU1 , . . . , EUd+1
2
AB ∈ Z(d+1) ×2(d+1)

j6=1

i

i

the binomial f belongs to the Graver basis of Knd it is
Proposition 4.13] that f belongs to the Graver basis of
The partition of the edges of Hd+1 into d + 1 bouquets
and d + 1 single edges E1 , . . . , Ed+1 induces the matrix


−d 0
 0 −d

AB = [aEU1 , . . . , aEUd+1 , aE1 , . . . , aEd+1 ] = 

 0
0
0

0

... 0 0
... 0 1
..
.
. . . −d 1
... 0 0

1 ...
0 ...
..
.
1 ...
0 ...


1
1 

 ,

0 

0

where aEi = α Ei for all i, the first d + 1 rows are indexed after the vertices
v11 , . . . , vd+1,1 and the last row represents block matrix 0 ∈ Zd(d+1)×2(d+1) . As it
was noticed in the comments prior to this proposition the binomial f corresponds
to the vector
v = (1 − d, 1, . . . , 1, 1 − d, 1, . . . , 1, . . . , 1 − d, 1, . . . , 1, −1, −1, . . . , −1) ∈ Ker(AHd+1 ).
18

Applying Theorem 1.3 we have a bijective correspondence between Ker(AB ) and
Ker(AHd+1 ) and given by
B(u1 , . . . , u2d+2 ) =

d+1
X

cEUi ui +

i=1

d+1
X

cEi ud+1+i .

i=1

Therefore replacing the formulas obtained before for cEUi and cEi , for all i =
1, . . . , d + 1, we obtain that v = B(u) where u = (1, . . . , 1, −1, . . . , −1) ∈ Z2d+2
with equally many 1’s and −1’s. By Theorem 1.3 it is enough to prove that u belongs to the Graver basis of AB to conclude that v (and thus f ) is in the Graver
basis of Hd+1 . Assume by contradiction u = u+ − u− is not in the Graver basis of
AB . Then there exists 0 6= w ∈ Ker(AB ) such that w+ ≤ u+ and w− ≤ u− , with at
least one inequality strict. In terms of coordinates this can be restated: wi ∈ {0, 1}
for all i = 1, . . . , d + 1 and wi ∈ {−1, 0} for all i = d + 2, . . . , 2d + 2, and with at
least one coordinate zero. If w+ = u+ then since w ∈ Ker(AB ) we obtain w− = u− ,
a contradiction. Otherwise there exists i ∈ {1, . . . , d + 1} such that wi = 0, and
without loss of generality we may assume that w1 = 0. Since w ∈ Ker(AB ) then
wd+3 + · · · + w2d+2 = 0, and thus wd+3 = . . . = w2d+2 = 0. If wd+2 = 0 then w = 0,
a contradiction, so we necessarily have wd+2 = −1. This leads to −dwi = 1 for all
i = 1, . . . , d + 1 a contradiction to w ∈ Z2d+2 . Therefore u belongs to the Graver
basis of AB , and we are done.

3. Complexity of hypergraphs
It is well-known that the elements of the Graver basis of a toric ideal of a graph
are of a rather special form: the exponents of each variable in an element of the
Graver basis is either one or two, see, for example, [20] and references therein, and
are completely determined by their support. In other words, one can not find two
elements in the Graver basis of a toric ideal of a graph with the same support. In
[18] it was shown that exponents in the elements of the Graver basis of a toric ideal
of a hypergraph can be arbitrarily high, and are not uniquely determined by their
supports, see Example 2.4. Thus the natural question is: how complicated are the
Graver basis, the universal Gröbner basis or a Markov basis of a hypergraph?
The bouquet ideal technique can be used to prove that toric ideals of hypergraphs
are as complicated as toric ideals in general. Namely, for any toric ideal, there
exists a toric ideal of a hypergraph with “worse” Graver basis, universal Gröbner
basis and Markov bases, as well as circuits. “Worse” means that the corresponding
set for the toric ideal of a hypergraph has at least the same cardinality and elements
of higher degrees than the corresponding elements of the toric ideal. In [9, Theorem
2.1] the authors show that for a particular matrix A, namely the one corresponding
to the no-three-way interaction model in statistics, elements in a minimal Markov
basis can be arbitrarily complicated as two of the three dimensions of the underlying
table grow to infinity. Such matrices are, in fact, incidence matrices of 3-uniform
hypergraphs. In contrast, Theorem 3.2 implies that the complexity of the whole
Graver basis (resp. minimal Markov or Universal Gröbner basis) of any matrix A
can be captured by an almost 3-uniform hypergraph, that is a hypergraph whose
19

edges have cardinality at most 3. In Section 4 there will be a stronger connection
but for matrices A defining positively graded toric ideals.
We start first with an example, which shows the details of the general construction.
Example 3.1. Let
A=



−1 −1 2 2
−2 2 −1 0



,

be the matrix whose columns are denoted by a1 , . . . , a4 . We construct a hypergraph H = (V, E) such that the bouquet graph of H has four bouquets with bases
EU1 , . . . , EU4 , and with the property that the corresponding subbouquet ideal (associated to the vectors aEU1 , . . . , aEU4 ) is IA . The latter will follow since the vectors aEU1 , . . . , aEU4 are “essentially” the vectors a1 , . . . , a4 , in the sense that each
aEUi ∈ Z|V | is just the natural embedding of ai in Z|V | with the other coordinates 0.
The construction of H is carried out in three steps.
Step 1. Every non-zero entry of the matrix A is used to construct a sunflower,
which will be the building blocks of the desired hypergraph. Precisely, for a positive
entry λ of the matrix A we consider a 3-uniform sunflower with one core vertex
and |λ| petals, while for a negative entry λ we consider the sunflower with one core
vertex and |λ| + 1 petals, which is almost 3-uniform, meaning that only one petal
has two vertices, the other have three. In the particular case of our example the
matrix A has three different nonzero entries −1, −2, 2, and thus we have two almost
3-uniform sunflowers and one 3-uniform sunflower pictured below, see Figure 5.
•

•
•

•

•

•

•

•
•

•

•
•

•

•
•

Figure 5. The sunflowers corresponding to matrix entries −1 (left),
2 (center), and −2 (right).
Step 2. Next we construct for each column aj a connected matched-petal
partitioned-core sunflower Hj . For this we use the sunflowers constructed in Step
1 in the following way: if aij > 0 we use the previously constructed sunflower,
otherwise the sunflower obtained by deleting the petal with two vertices from the
corresponding sunflower. Finally, Hj consists of these disjoint 3-uniform sunflowers,
and a perfect matching on the union of non-core vertices. Then we add to Hj the
deleted petals with two vertices to obtain Hj′ . For example, since a1 = (−1, −2) we
take the sunflowers corresponding to −1 and −2 from Step 1 (see the leftmost picture of Figure 6), then delete the petals with two vertices to construct the connected
matched-petal partition-core sunflower H1 (see the middle picture of Figure 6) and
finally, add the two petals of cardinality 2 to obtain H1′ (the rightmost picture of
Figure 6).
20

•

•

•

•

v2 (11) v1 (11) u(11)

v1

v2 (11) v1 (11) u(11)

•

+

v2 (21)

•

−→

v1 (21)

•

•

v2 (21)

•

−→

v1 (21)

•

•

•

v2

•

u(21)

•
•

v3 (21)

v4 (21)

•

•

•

u(21)

v1

v1 (21)

•

•

•

v2 (21)

•

•
•

v2 (11) v1 (11) u(11)

•

•
•

v3 (21)

v4 (21)

•

u(21)

v2

v3 (21)

v4 (21)

Figure 6. The bouquet with basis H1′
v2 (12) v1 (12) u(12)

•

•

•

v1

v2 (13)

•

•

•

v1 (14)

•
• v1

•
• v2

•
v4 (22)

•
• v1

v1 (22)

•
•

v2 (14)

v1 (13)

•

v2 (22)

v3 (22)

v4 (13)

•

•

v3 (13)

•
•

•

•

v2 (23) v1 (23) u(23)

•

v3 (14)

v4 (14)

v2

Figure 7. The other 3 bouquets with basis corresponding to a2 , a3 , a4 .
For sake of completeness, we have labeled the vertices of sunflowers from Figure 6
according to the general construction of Theorem 3.2, and we denote their edges by
e0 (11) = {u(11), v1}, e1 (11) = {u(11), v1(11), v2 (11)}, e0 (21) = {u(21), v2}, e1 (21) =
{u(21), v1(21), v2 (21)}, e2 (21) = {u(21), v3(21), v4(21)}, e1 = {v2 (11), v1 (21)}, e2 =
{v2 (21), v3(21)}, e3 = {v4 (21), v1 (11)}. One should note that there is not a unique
way to choose the blue edges (in the picture e2 , e3 , e4 ) such that they form a matching
of the non-core vertices of the connected matched-petal partitioned-core sunflower
H1 . Also, we see that the hypergraph H1′ constructed is a bouquet with basis the set
U1 of all vertices except v1 , v2 . Similarly one repeats the construction for each one
of the column vectors of A, that is a2 , a3 , a4 , obtaining the hypergraphs depicted in
Figure 7. Note that all four hypergraphs H1′ , . . . , H4′ obtained through the previous
construction are bouquets with basis U1 , . . . , U4 , where each Ui is just the set of
vertices of Hi′ except v1 , v2 .
Step 3 Finally, consider the hypergraph H = (V, E) with |V | = 28 and |E| = 26,
obtained from H1′ , . . . , H4′ by taking the vertex set to be the union of the set of
vertices of H1′ , . . . , H4′ , and the set of edges is the (disjoint) union of the set of edges
of H1′ , . . . , H4′ . Furthermore, we compute the subbouquet vectors of H1′ , . . . , H4′ . For
this, we analyze in detail only the first hypergraph H1′ which is a bouquet with basis
U1 , constructed in Figure 6, the others being computed similarly. We assume that
the column vectors of the incidence matrix of H are indexed such that the first eight
correspond, in this order, to the edges e1 (11), e0 (11), e1(21), e2 (21), e0 (21), e1 , e2 , e3 ,
while the first two rows are indexed by the vertices v1 and v2 . Then cH′1 =
21

(1, −1, 1, 1, −2, −1, −1, −1, 0) ∈ Z26 and
aH′1 = e1 (11) − e0 (11) + e1 (21) + e2 (21) − 2e0 (21) − e1 − e2 − e3 = (−1, −2, 0) ∈ Z28 .
Analogously, with respect to a similar order for the rest of the edges of the other
three bouquets, we obtain the following cH′2 = (0, 1, −1, 1, 1, −1, −1, −1, 0, 0), cH′3 =
(0, 0, 1, 1, 1, −1, −1, −1, −1, 0) and cH′4 = (0, 0, 0, 1, 1, −1, −1) ∈ Z26 . Therefore
the other three bouquet vectors are aH′2 = (−1, 2, 0), aH′3 = (2, −1, 0) and aH′4 =
(2, 0, 0) ∈ Z28 . Since the set of edges of H can be partitioned into four bouquets with
bases H1′ , . . . , H4′ , the ideal IH is strongly robust, by Corollary 2.5. By Theorem 1.3,
the bijective correspondence between the Graver basis of IA and the Graver basis of
IH applies in the following way: to the vector u = (1, 3, 4, −2) ∈ Gr(A) corresponds
the vector B(u)
(1, −1, 1, 1, −2, −1, −1, −1|3, −3, 3, 3, −3, −3, −3|4, 4, 4, −4, −4, −4, −4|2, 2, −2, −2).
There are seven elements in Gr(H).
For the next construction we may assume that the matrix A has no zero column
or row. Indeed, if, say, a1 = 0, then IA = (IA′ , 1 − x1 ), where IA′ ⊂ K[x2 , . . . , xn ],
and if, say, the first row is zero, then IA = IA′ , where A′ = [a′1 , . . . , a′n ], with
a′j = (a2j , . . . , amj ) ⊂ Zm−1 for all j.
Theorem 3.2. Given any integer matrix A without any zero row or zero column,
there exists an almost 3-uniform hypergraph H = (V, E) such that:
(1) There is a bijective correspondence, u 7→ B(u), between KerZ (A), Gr(A) and
C(A) and KerZ (H), Gr(H) and C(A), respectively.
P
(2) For every u ∈ Gr(A) we have |u|1 ≤ |B(u)|1 , where |u|1 = ni=1 |ui | represents the 1-norm of the vector u.
(3) The toric ideal IH is strongly robust.
Proof. Let A = [a1 , . . . , an ] ∈ Zm×n . We will construct a hypergraph H whose
subbouquet ideal is IA , and with the property that all its non-free subbouquets
are mixed. This will imply at once conditions (1) and (3), by Theorem 1.3 and
Corollary 2.5. To this end, let {v1 , . . . , vm } be a set of vertices, and for each nonzero
entry of the matrix aij we introduce the following new vertices:
(1) if aij > 0 the set {v1 (ij), v2 (ij), · · · , v2aij (ij)} of 2aij vertices,
(2) if aij < 0 the set {u(ij), v1(ij), v2 (ij), · · · , v−2aij (ij)} of −2aij + 1 vertices,
as well as the following edges:
(3) if aij > 0 the aij edges es (ij) = {vi , v2s−1 (ij), v2s (ij)}, where 1 ≤ s ≤ aij ,
(4) if aij < 0 the −aij + 1 edges es (ij) = {u(ij), v2s−1 (ij), v2s (ij)}, where 1 ≤
s ≤ −aij and e0 (ij) = {vi , u(ij)}.
Note that for each aij 6= 0 the hypergraph Sij , on the set of vertices defined in
item (1) (item (2), respectively) with the set of edges defined in item (3) (item
(4), respectively) is a sunflower with the core vi (u(ij), respectively). Furthermore, each sunflower Sij is either a 3-uniform sunflower if aij > 0 or an almost
3-uniform sunflower if aij < 0 (by almost we mean that all the edges have three
vertices except e0 (ij), which has only two vertices). In addition, for any fixed j the
22

sunflowers S1j , . . . , Smj are vertex disjoint by definition. For each nonzero column
aj = (a1j , . . . , amj ) we construct first a connected matched-petal partitioned-core
sunflower Hj = (Vj , Ej ) on the set of vertices
[
[
Vj =
{v1 (ij), v2 (ij), . . . , v2aij (ij), vi }∪
{v1 (ij), v2 (ij), . . . , v−2aij (ij), u(ij)},
i:aij >0

i:aij <0

with the core vertices
Cj =

[

{vi } ∪

i:aij >0

[

{u(ij)}.

i:aij <0

For this is enough to describe the construction of H1 = (V1 , E1 ), the others being
similar. Consider all nonzero entries of the column a1 = (a11 , . . . , am1 ). To each
nonzero ai1 we associate the sunflower Si1 if ai1 > 0, or the sunflower denoted by
Si1 \ {e0 (i1)} obtained from Si1 by removing the edge e0 (i1), if ai1 < 0. Note that
Si1 \ {e0 (i1)} is a 3-uniform sunflower with core the set {u(i1)}, and its vertex set is
obtained from the vertex set of Si1 by removing vi . The matched-petal partitionedcore sunflower H1 with vertex set V1 , consists of the vertex-disjoint sunflowers Si1
(for those i with ai1 > 0) and Si1 \ {e0 (i1)} (for those i with ai1 < 0), and with the
following perfect matching on the set Vj \ Cj , of non-core vertices:
{v2 (11), v3(11)}, . . . , {v2|a11 |−2(11), v2|a11 |−1 (11)}, {v2|a11 | (11), v1 (21)},
{v2 (21), v3 (21)}, . . . , {v2|am1 |−2 (m1), v2|am1 |−1 (m1)}, {v2|am1 | (m1), v1 (11)},
where for convenience of notation we assumed that all ai1 6= 0 (see for an example
the blue edges from Figures 6, 7). This perfect matching on the non-core vertices
ensures that Hj = (Vj , Ej ) is a connected matched-petal partitioned-core sunflower.
Then we “extend” the hypergraph Hj to the hypergraph Hj′ = (Vj′ , Ej′ ), where
Vj′ = Vj ∪ {vi : aij < 0} and Ej′ = Ej ∪ {e0 (ij) : aij < 0}, which turns out to be
a bouquet with basis the set Uj = Vj′ \ {vi : aij 6= 0}. Alternatively, we can write
Hj′ = EUj for all j = 1, . . . , n. Finally, the hypergraph
H = (V, E)Swe are looking for
Sn
′
′
′
is obtained from H1 , . . . , Hn as follows V = j=1 Vj , and E = nj=1 Ej′ . Note that
since A has no zero row, then {v1 , . . . , vm } ⊂ V . Since each Hj′ is a bouquet with
basis, then it follows immediately from construction that H has n bouquets with
bases. Moreover, the resulting bouquet vector of Hj′ = EUj is aEUj = (aj , 0) ∈ Z|V |
and thus we obtain that the subbouquet ideal of IH is IA , as desired.

The following two results were inspired by the universality results of [9]. In some
sense, the following two corollaries strengthen [9, Theorem 1.2] and [9, Corollaries
2.1,2.2]. There, the motivation from algebraic statistics was to show that, for a particular 0/1 matrix of a 3-uniform hypergraph encoding a model on three-dimensional
contingency tables, as two of the dimensions of the table grow, there cannot be a
universal upper bound on the degrees of minimal Markov bases. To show this, it
is enough for [9] to construct one element of given arbitrarily high degree. The results below differ in three ways: 1) the underlying incidence matrices of the almost
3-uniform hypergraphs are 0 − 1 matrices with at most three ones on each column;
2) our statement holds true for all binomials in any minimal Markov basis, and not
only for one binomial; 3) since the toric ideal constructed is strongly robust then the
23

statement is also valid for Graver basis, indispensable binomials, universal Gröbner
basis respectively. The reader should note that the two classes of matrices considered in [9] and considered here have in common only the fact that they are 0 − 1
matrices with at most three ones on each column.
Corollary 3.3. For any vectors d1 , . . . , dr ∈ Zm there exists an almost 3-uniform
hypergraph H with its toric ideal strongly robust such that all of the elements of
the minimal Markov basis of H restricted to some of its entries cover the whole set
{d1 , . . . , dr }.
α 1 , . . . , α r ] ∈ Zp×r be a unimodular matrix such that all of its
Proof. Let D = [α
bouquets are not free, and consider the vectors c′i = (1, di ) = (1, di1 , . . . , dim ) ∈ Zm+1
for all i = 1, . . . , r. By definition the vectors c′1 , . . . , c′r are primitive and thus
we can apply Theorem 1.6 in order to obtain a generalized Lawrence matrix A =
[a1 , . . . , an ] ∈ Zq×n such that its subbouquet ideal equals ID , and whose Graver basis
equals the set of circuits and implicitly the universal Gröbner basis. In addition,
α i , 0, . . . , 0) and
we know that the subbouquet Bi is encoded by the vectors aBi = (α
cBi = (0, . . . , c′i , . . . , 0), for all i = 1, . . . , r. Since D is unimodular applying [22,
Proposition 8.11] we have that the Graver basis elements of D are vectors with
coordinates only 0, 1, −1, which in turn implies via the one-to-one correspondence
of Theorem 1.3
r
X
′
′
B((u1 , . . . , ur )) =
cBi u′i = (u′1 , u′1d1 , . . . , u′r , u′r dr ) ∈ Zn
i=1

that the Graver basis elements of A are vectors whose coordinate nonzero blocks are
either c′i or −c′i .
Finally, we apply for the matrix A the construction of Theorem 3.2 to obtain the
hypergraph H which has n bouquets with bases H1′ , . . . , Hn′ , and whose toric ideal is
strongly robust. Note from the proof of Theorem 3.2 that the nonzero coordinates of
the vectors cH′i corresponding to the edges of the perfect matching on the non-core
vertices are equal either to 1 or −1. Since the subbouquet ideal of IH is equal to
IA it follows from the description of the Graver basis elements of A that via the
one-to-one correspondence
n
X
(u′1 , u′1d11 , . . . , u′1 d1m , . . . , u′r , u′r dr1 , . . . , u′r drm ) = (u1 , . . . , un ) 7→
cH′j uj
j=1

the Graver basis elements of H contain as subvectors at least one of ±d1 , . . . , ±dr .
Indeed, from the construction of A we have that u′i ∈ {−1, 0, 1} and we just substitute them in the previous displayed formula. Since IH is strongly robust then
the Graver basis equals the minimal Markov basis and thus we have the desired
conclusion.
For the final part of statement, that is all of the vectors d1 , . . . , dr appear as a
support of some elements from the minimal Markov basis of H we need to make
a choice on the unimodular matrix D to ensure that in the Graver basis of ID
appear all of the variables. For example, we may choose D to be the incidence
matrix of a complete bipartite graph Kp,ℓ with p, ℓ ≥ 2 if r equals its number of
24

edges. Otherwise, we consider a complete bipartite graph Kp,ℓ with the number
of edges q > r, let D ∈ Zp×q be its incidence matrix and consider the q vectors
c′1 , . . . , c′r , c′r , . . . , c′r with the vector c′r being repeated q − r + 1 times.

Taking d1 = · · · = dr = d in the previous corollary and switching from the vector
+
−
notation of an element v ∈ KerZ (H) to the binomial notation xv − xv ∈ IH we
obtain the following
Corollary 3.4. For any vector d ∈ Zn there exists an almost 3-uniform hypergraph
H with its toric ideal strongly robust such that all binomials in the minimal generating set of IH satisfy the following: one of its monomials restricted to a suitable
subset of variables has multi-degree d+ and its other monomial restricted to a suitable
subset of variables has multi-degree d− .
4. Hypergraphs encode all positively graded toric ideals
This section presents a correspondence between positively graded (general) toric
ideals and stable toric ideals of hypergraphs. Namely, given a positively graded IA ,
Theorem 4.2 constructs a stable toric ideal of a hypergraph H = H(A) that has
the same combinatorial complexity and whose homological properties are preserved.
In particular, the Graver bases of the ideals IA and IH have the same number of
elements, and the same holds for their universal Gröbner and Markov bases, as well
as indispensable binomials and circuits. Even more is true: if IA has ℓ different
minimal Markov bases then IH has also ℓ different minimal Markov bases, and the
same holds for the reduced Gröbner bases. Contrast this with Section 3, where an
arbitrary toric ideal may have infinitely many minimal Markov bases.
For the remainder of this section, fix the following notation:


0 1 ... ... 1
1 0
1 . . . 1
. .
.
n×n
.
.

Σn := 
 .. . . . . . . ..  ∈ Z
1 . . . 1
0 1
1 ... ... 1 0
and
εk,n := (1| {z
· · · 1} 0 · · · 0) ∈ Zn , where 1 ≤ k < n.
k times

The following example illustrates a general construction which is the basis for the
proof of Theorem 4.2.
Example 4.1. Given a non-negative integer matrix D, we seek a procedure to create
a 0/1 matrix A such that there is a bijective correspondence between distinguished
sets of binomials of ID and IA , namely, each of: Graver basis, circuits, indispensable
binomials, minimal Markov bases, reduced Gröbner bases (universal Gröbner basis).
Let


1 3 2 0 1
D = (dij ) =  3 2 1 3 2  ∈ N3×5 .
3 0 2 2 1
25

Let δi := maxl {dli } be the maximum entry in column i of D, and ji := min{l :
dli = δi } be the index of the first row where δi appears. For the given matrix
D, these values are as follows: δ1 = 3, δ2 = 3, δ3 = 2, δ4 = P
3 and δ5 = 2; and
5
j1 = 2, j2 = 1, j3 = 1, j4 = 2 and j5 = 2. Define δ :=
i=1 (δi + 1) = 18
and l = 3 − |{j1 , . . . , j5 }| = 1, the number of rows that do not contain any columnmaximum entry δi . We construct a 0-1 matrix A = MH of size 19 × 18, the incidence
matrix of a hypergraph H, such that its subbouquet ideal will be ID . Here, 19 = δ+l
and 18 = δ. The matrix A is constructed from D in two steps.
Step 1. Every column-maximum entry δi defined above will determine a set of
horizontal blocks of the matrix A as follows. For each row index k ∈ {ji }5i=1 , consider
the set of all δi ’s appearing on the k-th row of D. For each such δi , construct a
(δi + 1) × δ block matrix by concatenating (horizontally) the following 5 sub-blocks:
block i shall consist of the matrix Σδi +1 , while for each l 6= i, block l shall consist of
δi + 1 copies of εdkl ,δi +1 .
For example, the first row of D contains two column-maximum entries, δ2 and
δ3 . The first entry will generate a row-block of size (3 + 1) × 18 inside A, while the
second entry will generate a row-block of size (2 + 1) × 18. First, the entry δ2 = 3
requires concatenating five sub-blocks: the first one consisting of 4 = δ2 + 1 copies
of εd11 ,4 = (1 0 0 0); the second one, Σ4 ; the third one consisting of 4 copies of
εd13 ,4 = (1 1 0 0); the fourth one, 4 copies of εd14 ,4 = (0 0 0 0); and the fifth, 4
copies of εd15 ,4 = (1 0 0 0). This resulting row-block of A is displayed below, with
the distinguished sub-block corresponding to Σ4 colored in blue.


1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0
 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 


 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 .
1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0
Similarly, the second entry, δ3 = 2,

1 0 0 0 1 1 1
 1 0 0 0 1 1 1
1 0 0 0 1 1 1

will generate the following 3 × 18 row-block:

0 0 1 1 0 0 0 0 1 0 0
0 1 0 1 0 0 0 0 1 0 0 .
0 1 1 0 0 0 0 0 1 0 0

The remaining row indices are j1 = j4 = j5 = 2, thus we consider the second row
of D. It contains three δi values: δ1 , δ4 , δ5 , and thus gives rise to three row-blocks of
similar structure. These are the third, fourth and fifth row-blocks of the matrix A
in Equation (3).
Step 2. For each row k of D containing none of the column-maxima δi ’s, that
is, for all row indices k ∈ {1, 2, 3} \ {ji }5i=1 , we will create one additional row of
A. This row will be obtained by concatenating (in this order) the following vectors
εdk1 ,δ1 +1 , εdk2 ,δ2 +1 , εdk3 ,δ3 +1 , εdk4 ,δ4 +1 , εdk5 ,δ5 +1 . For example, the third row of D does
not contain any δi and thus the row of A obtained from concatenating the vectors
εd31 ,4 = (1 1 1 0), εd32 ,4 = (0 0 0 0), εd33 ,3 = (1 1 0), εd34 ,4 = (1 1 0 0) and
εd35 ,3 = (1 0 0) is

1 1 1 0 0 0 0 0 1 1 0 1 1 0 0 1 0 0 .
26

Finally, the matrix A = [a1 , . . . , a18 ] is obtained by concatenating (vertically) the
two row-blocks generated by the first row of D, the three row-blocks generated by
the second row of D, and the row generated by the third row of D; see Equation (3).
Note that the submatrix of A generated by the first row of D has 4 + 3 = 7 rows, the
one generated by the second row of D has 4 + 4 + 3 = 11 rows, and the one generated
by the third row of D has 1 row. The matrix A has 5 non-mixed bouquets such
that a1 , a2 , a3 , a4 belong to the first bouquet B1 , a5 , a6 , a7 , a8 to B2 , a9 , a10 , a11 to
B3 , a12 , a13 , a14 , a15 to B4 , and a16 , a17 , a18 to B5 . Moreover all nonzero components
of cB1 , . . . , cB5 ∈ Z18 are 1, and thus aB1 = a1 + · · · + a4 ∈ Z19 is the transposed
vector of

1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 ,

where the first block has 7 coordinates, the second one 11 coordinates, and the last
one 1 coordinate. Similarly, aB2 = a5 + · · · + a8 is the transposed vector of

3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 0 ,

and so on. Thus IAB = ID , and since IA is a stable toric ideal the desired bijective
correspondence follows from Theorem 1.7.


















(3) A = MH = 
















1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1

0
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
1

0
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
1
1
1

0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0

0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0

1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0

1
1
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0

1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1

1
1
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1

0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
1
1
1
1
0
1
1
1
1
1
1
1

0
0
0
0
0
0
0
1
1
1
1
1
0
1
1
1
1
1
1

0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
1
1
1
0

0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1

0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
1
0

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0



































Theorem 4.2. Let ID be an arbitrary positively graded nonzero toric ideal. Then
there exists a hypergraph H such that there is a bijective correspondence between the
Graver bases, all minimal Markov bases, all reduced Gröbner bases, circuits, and
indispensable binomials of ID and IH . Furthermore, all of the homological data of
IH is inherited by ID and viceversa.
27

Proof. Since ID is a positively graded toric ideal, we may assume by [15, Corollary
7.23] that D = (dij ) ∈ Nm×n . Furthermore, every column of D is nonzero, since,
otherwise, if the j-th column is 0, then xj − 1 ∈ ID , a contradiction to ID being
positively graded. We will construct the incidence matrix A of a hypergraph H, such
that its subbouquet ideal is equal to ID . For this define column-maximum
entries
P
δi := max{dji : j = 1, . . . , m} for all i = 1, . . . , n and set δ = n + ni=1 δi . Note
that δi > 0 for every i = 1, . . . , m. Moreover, denote by ji := min{k : dki = δi } for
all i = 1, . . . , n and denote by l = m − #{ji : 1 ≤ i ≤ n}.
Then the 0-1 matrix A ∈ N(δ+l)×δ consists of several blocks, concatenated vertically, of the following two types: 1) For each k ∈ {j1 , . . . , jn }, and for each columnmaximum entry δi located on the k-th row of D, construct δi + 1 rows of A by
concatenating (horizontally) n block matrices. Here, the i-th block is Σδi +1 , while
for each l 6= i the l-th block consists of δi + 1 copies of the row sub-vector εdkl ,δl +1 .
2) For each row index k ∈ [m] \ {j1 , . . . , jn } of D, that is, each row not containing
any column-maximum entry δi , construct a row of A by by concatenating (in this
order) the following vectors
(εdk1 ,δ1 +1 |εdk2 ,δ2 +1 | . . . |εdkn ,δn +1 ).
Assume now that the columns of A are labeled a1 , . . . , aδ . We prove that the first
δ1 + 1 column vectors of A belong to the same subbouquet B1 , the next δ2 + 1 belong
to the same subbouquet B2 , and so on, until the last δn + 1 column vectors belong to
the same subbouquet Bn . We will prove this only for the first δ1 + 1 columns of A,
the other cases being similar. By the definition of A we have that in the submatrix
of A determined by the columns a1 , . . . , aδ1 +1 there exist integers i1 , . . . , i1 + δ1 = i2
such that the matrix corresponding to these rows and the columns a1 , . . . , aδ1 +1 is
Σδ1 +1 . We consider the vectors ci,i+1 ∈ Zδ+l for every i = i1 , . . . , i1 + δ1 − 1, whose
only nonzero coordinates are 1 on position i, and −1 on position i + 1. Then the covector (ci1 ,i1 +1 · a1 , . . . , ci1 ,i1 +1 · aδ ) = (−1, 1, 0, . . . , 0) has support of cardinality two
and G(a1 ) = G(a2 ). Here, we used the fact that in the horizontal block containing
Σδ1 +1 (and corresponding to the rows i1 , . . . , i2 ) all the entries corresponding to the
rows i1 , i1 + 1 and columns 3, . . . , δ are identical, by definition. Similarly, using all
the vectors ci,i+1 for i = i1 , . . . , i2 − 1, we obtain G(a1 ) = · · · = G(aδ1 +1 ), and
thus they all belong to the same subbouquet B1 , which is either free or non-mixed.
In any case, the vector cB1 = (1, 0, . . . , 0) ∈ Zδ with 1 = (1, . . . , 1) ∈ Zδ1 +1 and
aB1 = a1 +· · ·+aδ1 +1 . Analogously, we have cB2 = (0, 1, . . . , 0) with 1 = (1, . . . , 1) ∈
Zδ2 +1 and aB2 = aδ1 +2 + · · · + aδ1 +δ2 +2 , and so on, until cB2 = (0, 0, . . . , 1) with
1 = (1, . . . , 1) ∈ Zδn +1 and aBn = aδ−δn + · · · + aδ . One can easily see from the
construction of A that IAB = ID . In addition, since ID 6= 0 then at least one
subbouquet is non-free, and therefore IH = IA is a stable toric ideal. Applying now
Theorem 1.7 and [19, Theorem 3.11] we obtain the desired conclusions.

Remark 4.3. In conclusion, the previous theorem can be regarded as a polarizationtype operation for positively graded toric ideals by comparison to the properties of
the classical polarization for monomial ideals, see [12, Corollary 1.6.3]. Indeed, if
ID ⊂ S = K[x1 , . . . , xn ] and IH ⊂ T = K[y1 , . . . , yδ ] are the ideals from the above
28

construction since ID is the subbouquet ideal of IH then height(ID ) = height(IH ).
Applying now [19, Theorem 3.11] we have pd(T /IH ) = pd(S/ID ), the ND-graded
Betti numbers of ID are obtained from the NAH -graded Betti numbers of IH and
viceversa, and thus S/ID is Cohen-Macaulay (respectively Gorenstein) if and only
if T /IH is Cohen-Macaulay (respectively Gorenstein).
Remark 4.4. Moreover, combinatorial classification problems of arbitrary positively graded toric ideals whose different sets of bases are equal can be reduced
to problems about toric ideals of hypergraphs. For example, in [4] Boocher et. al
proved that, for robust toric ideals of graphs, the Graver basis is a minimal generating set. In other words, robust toric ideals of graphs are strongly robust. They ask
if this property is true in general for any robust ideal. To prove such a statement,
it is enough to prove it only for toric ideals of hypergraphs. Indeed, if IA is any
robust toric ideal then Theorem 4.2 shows that IH is robust. Then if one can prove
that robust ideals of hypergraphs are strongly robust then it follows, again from
Theorem 4.2, that IA is also strongly robust.
References
[1] 4ti2 team, 4ti2 - a software package for algebraic, geometric and combinatorial problems on
linear spaces, available at www.4ti2.de (2007).
[2] D. Bayer, S. Popescu, B. Sturmfels, Syzygies of unimodular Lawrence ideals, J. Reine Angew.
Math. 534, 169–186 (2001).
[3] A. Boocher, E. Robeva, Robust toric ideals, J. Symbolic Computation, 68(1), 254–264 (2015).
[4] A. Boocher, B. C. Brown, T. Duff, L. Lyman, T. Murayama, A. Nesky and K. Schaefer,
Robust graph ideals, Annals of Combinatorics 19(4), 641–660 (2015).
[5] H. Charalambous, A. Thoma, M. Vladoiu, Minimal generating sets of lattice ideals, Collectanea Mathematica 68, 377–400 (2017).
[6] H. Charalambous, A. Thoma, M. Vladoiu, Markov complexity of monomial curves, Journal
of Algebra 417, 391–411 (2014).
[7] H. Charalambous, A. Thoma, M. Vladoiu, Markov bases and generalized Lawrence liftings,
Annals of Combinatorics 19(4), 661–669 (2015).
[8] J. De Loera, R. Hemmecke, S. Onn, R. Weismantel, N-fold integer programming, Discrete
Optimization 5, 231–241 (2008).
[9] J. De Loera, S. Onn, Markov bases of three-way tables are arbitrarily complicated, J. Symbolic
Computation 41, 173–181 (2006).
[10] J. De Loera, B. Sturmfels, R. Thomas, Gröbner bases and triangulations of the second hypersimplex, Combinatorica 15(3), 409–424 (1995).
[11] E. Gross, S. Petrović, Combinatorial degree bound for toric ideals of hypergraphs, Internat.
J. Algebra Comput. 23(6), 1503–1520 (2013).
[12] J. Herzog, T. Hibi, Monomial Ideals, GTM 260. Springer 2010.
[13] S. Jukna, Extremal Combinatorics-with Applications in Computer Science, Texts in Theoretical Computer Science. Springer, New York (2001).
[14] M. Lason, M. Michalek, On the toric ideal of a matroid, Adv. in Mathematics 259, 1–12
(2014).
[15] E. Miller, B. Sturmfels, Combinatorial Commutative Algebra, Grad. Texts in Math., vol. 227,
Springer-Verlag, New York, (2005).
[16] H. Ohsugi, T. Hibi, Toric ideals generated by quadratic binomials, J. Algebra 218, 509–527
(1999).
[17] I. Peeva, B. Sturmfels, Generic lattice ideals, J. Amer. Math. Soc., Vol. 11(2), 363–373 (1998).
29

[18] S. Petrović, D. Stasi, Toric algebra of hypergraphs, J. Algebraic Combinatorics, Volume 39,
Issue 1, pp 187-208 (2014).
[19] S. Petrović, A. Thoma, M. Vladoiu, Bouquet algebra of toric ideals, arXiv:1507.02740v3.
[20] E. Reyes, Ch. Tatakis, A. Thoma, Minimal generators of toric ideals of graphs, Adv. Appl.
Math. 48, 64–78 (2012).
[21] F. Santos, B. Sturmfels, Higher Lawrence configurations, J. Combin. Theory Ser. A 103,
151–164 (2003).
[22] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series, No 8, MAS,
R.I. (1995).
[23] B. Sturmfels, S. Sullivant, Toric ideals of phylogenetic invariants, Journal of Computational
Biology 12, 204–228 (2005).
[24] S. Sullivant, Strongly robust toric ideals in codimension 2, arXiv:1610.07476v1, 2016.
[25] Ch. Tatakis, A. Thoma, On the universal Gröbner bases of toric ideals of graphs, J. Combin.
Theory Ser. A 118, 1540–1548 (2011).
[26] R. Villarreal, Rees algebras of edge ideals, Comm. Algebra 23, 3513–3524 (1995).
[27] R. Villarreal, Monomial Algebras, Second Edition, Monographs and Research Notes in Mathematics, Chapman and Hall/CRC, 2015.
Sonja Petrović, Department of Applied Mathematics, Illinois Institute of Technology, Chicago 60616, USA
Apostolos Thoma, Department of Mathematics, University of Ioannina, Ioannina
45110, Greece
E-mail address: athoma@uoi.gr
Marius Vladoiu, Faculty of Mathematics and Computer Science, University of
Bucharest, Str. Academiei 14, Bucharest, RO-010014, Romania, and
Simion Stoilow Institute of Mathematics of Romanian Academy, Research group
of the project PN-II-RU-TE-2012-3-0161, P.O.Box 1–764, Bucharest 014700, Romania
E-mail address: vladoiu@fmi.unibuc.ro

30

