GENERALIZED BINOMIAL EDGE IDEALS

arXiv:1210.7960v1 [] 30 Oct 2012

JOHANNES RAUH
Abstract. This paper studies a class of binomial ideals associated to graphs with
finite vertex sets. They generalize the binomial edge ideals, and they arise in the study
of conditional independence ideals. A Gröbner basis can be computed by studying
paths in the graph. Since these Gröbner bases are square-free, generalized binomial
edge ideals are radical. To find the primary decomposition a combinatorial problem
involving the connected components of subgraphs has to be solved. The irreducible
components of the solution variety are all rational.

1. Introduction
Let X0 and Xin be finite sets, d0 = |X0 | > 1, and denote X = X0 × Xin . Let K be
a field, and consider the polynomial ring R = K[px : x ∈ X] with |X| unknowns px
indexed by X. For all i, j ∈ X0 and all x, y ∈ Xin let
ij

fxy = pix p jy − piy p jx .
ij

For any graph G on Xin the ideal IG in R generated by the binomials fxy for all i, j ∈ X0
and all edges (x, y) in G is called the d0 th binomial edge ideal of G over K. This is a
direct generalization of [3] and [4], where the same ideals have been considered in the
special case d0 = 2. For a comparison of the results of the present paper to previous
results see Remark 8.
One motivation to look at generalized binomial edge ideals comes from the study of
conditional independence ideals. Given n + 1 random variables X0 , X1 , . . . , Xn , generalized binomial edge ideals correspond to a collection of statements of the form (see [3]
for an explanation of the notation and further details)
X0 y XR | XS = xS ,
where R ∪ S = {1, . . . , n}. Such statements naturally occur in the study of robustness.
Implications of the algebraic study of generalized binomial edge ideals will be studied
in another paper [5], see also [3, Section 4]. Generalized binomial edge ideals also
cover the conditional independence ideals associated with the intersection axiom in [2].
A different generalization of the results in [2] was recently studied in [7]. The ideals
I h1i defined in [7] are special cases of binomial edge ideal.

Date: January 1, 2018.
Key words and phrases. binomial ideals, binomial edge ideals, graphs, primary decomposition, conditional independence ideals.
1

2

JOHANNES RAUH

2. The Gröbner basis
Choose a total order > on Xin (e.g. choose a bijection Xin  [N]). This induces a
lexicographic monomial order on R, also denoted by >, via



 either i > j,
pix > p jy
⇐⇒


 or
i = j and x > y.

To construct a Gröbner basis for IG with respect to this order the following definitions
are needed:

Definition 1. A path π : x = x0 , x1 , . . . , xr = y from x to y in G is called admissible if
(i) xs , xt for s , t, and x < y;
(ii) for each k = 1, . . . , r − 1 either xk < x or xk > y;
(iii) for any proper subset {y1 , . . . , ys } of {x1 , . . . , xr−1 }, the sequence x, y1 , . . . , ys , y
is not a path.
A function κ : {0, . . . , r} → [d] is called π-antitone if it satisfies
xs < xt =⇒ κ(s) ≥ κ(t), for all 0 ≤ s, t ≤ r.
κ is strictly π-antitone if it is π-antitone and satisfies κ(0) > κ(r).
The notion of π-antitonicity also applies to paths which are not necessarily admissible. However, since admissible paths are injective (i.e. they only pass at most once at
each vertex), in the admissible case it is possible to write κ(ℓ) instead of κ(s), if ℓ = xs .
To any x < y, any path π : x = x0 , x1 , . . . , xr = y from x to y and any function
κ : {0, . . . , r} → X0 associate the monomial
r−1
Y
uκπ =
pκ(k)xk .
k=1

Theorem 2. The set of binomials
[
κ(y)κ(x)
: x < y, π is an admissible path in G from x to y,
G=
uκπ fxy

i< j
κ is strictly π-antitone
is a reduced Gröbner basis of IG with respect to the monomial order introduced above.
Q
The role of π-antitonicity is the following: In smaller monomials rk=1 pik xk , smaller
κ(y)κ(x)
indices ik are associated to larger points xk . Hence the initial term of uκπ fxy
is
uκπ pκ(y)x pκ(x)y . This explains why in the definition of G the point x is associated to the
index κ(y), and vice versa. The main idea of the proof of Theorem 2 is that reduction modulo G changes the association of the indices {ik } and the points {xk } until the
resulting monomial is minimal. The following lemma is a first step:
Lemma 3. Let π : x0 , . . . , xr be a path in G, and let κ : {0, . . . , r} → [d] be an arbitrary
function. If κ is not π-antitone, then there exists g ∈ G such that ini< (g) divides the
κ(y)κ(x)
.
initial term of uκπ f xy
Proof. Let τ : y0 , . . . , ys be a minimal subpath of π with respect to the property that the
restriction of κ to τ is not τ-antitone. This means that κ is τ0 -antitone and τ s -antitone,
where τ0 = y1 , . . . , ys and τ s = y0 , . . . , ys−1 . Assume without loss of generality that
y0 < ys , otherwise reverse τ. The minimality implies that κ(y0 ) < κ(ys ). It follows that

GENERALIZED BINOMIAL EDGE IDEALS

3

τ is admissible: By minimality, if y0 < yk < ys , then κ(yk ) ≥ κ(ys ) > κ(y0 ) ≥ κ(yk ), a
contradiction. Define



κ(s), if k = 0,




κ̃(k) = 
κ(0), if k = s,




κ(k), if 0 < k < s.

κ̃(y)κ̃(x)
s )κ̃(y0 )
).
) divides ini< (uκ̃π fxy
Then κ̃ is τ-antitone, and ini< (uκ̃τ fyκ̃(y
0 ys



Proof of Theorem 2. The proof is organized in three steps.
Step 1: G is a subset of IG . Let π : x = x0 , x1 , . . . , xr−1 , xr = y be an admissible path
κ( j)κ(i)
in G. The proof that uκπ fxy
belongs to IG is by induction on r. Clearly the assertion
is true if r = 1, so assume r > 1. Let A = {xk : xk < x} and B = {xℓ : xℓ > y}. Then
either A , ∅ or B , ∅.
Suppose A , ∅ and set xk = max A. The two paths π1 : xk , xk−1 , . . . , x1 , x0 = x and
π2 : xk , xk+1 , . . . , xr−1 , xr = y in G are admissible. Let κ1 and κ2 be the restrictions of κ
to π1 and π2 . Let a = κ(r), b = κ(0) and c = κ(k). The calculation
(pby pax − pbx pay )pcxk
= (pbxk pcx − pbx pcxk )pay + (paxk pby − pay pbxk )pcx − (paxk pcx − pax pcxk )pby
ab lies in the ideal generated by uκ1 f bc , uκ2 f ab and uκ1 f ac . By inducimplies that uκπ fxy
π1 xk x
π1 xk x π2 xk y
tion it lies in IG . The case B , ∅ can be treated similarly.

Step 2: G is a Gröbner basis of IG . Let π : x0 , . . . , xr and σ : y0 , . . . , ys be admissible
paths in G with x0 < xr and y0 < ys , and let κ and µ be π- and σ-antitone. By
µ µ(s)µ(0
, uσ fy0 ys )
Buchberger’s criterion it suffices to show that the S -pairs S := S (uκπ f xκ(r)κ(0)
0 xr
reduces to zero.
If S , 0, then S is a binomial. Write S = S 1 − S 2 , where S 1 = ini< (S ). S is
homogeneous with respect to the multidegrees given by



1, if i = j,
deg(pix ) j = δi j = 
0, else,

and

deg(pix )y = δxy




1,
=

0,

if x = y,
else

(this is a multidegree with |X0 | + |Xin | components).
and
If π and σ are disjoint paths, then S trivially reduces to zero, since uκπ f xκ(r)κ(0)
0 xr
µ µ(s)µ(0)
uσ fy0 ys
contain different variables. So assume that π and σ meet and that S , 0.
Then S 1 and S 2 are monomials, and the unknowns pix occurring in S 1 and S 2 satisfy
x ∈ π∪σ. Assume that there are x < y such that D x := min{i ∈ X0 : pix | S 1 } < max{i ∈
X0 : piy | S 1 } =: Dy . Since π ∪ σ is connected there is an injective path τ : z0 , . . . , zs
from x = z0 to y = zs in π ∪ σ. Choose a map λ : {0, . . . , s} → X0 such that λ(0) = D x ,
λ(s) = Dy and pλ(a)a | S 1 for all 0 ≤ a ≤ s. Then uλτ divides S 1 , and λ is not τ-antitone.
So Lemma 3 applies, and S can be reduced to a smaller binomial.
Let S ′ be the reduction of S modulo G. If S ′ , 0, then let S 1′ = ini< (S ′ ). The
above argument shows that min{i ∈ X0 : pix | S 1′ } ≥ max{i ∈ X0 : piy | S 1′ } for all x < y.
This property characterizes S 1′ as the unique minimal monomial in R with multidegree

4

JOHANNES RAUH

deg(S 1′ ) = deg(S ). But since the reduction algorithm turns binomials into binomials,
S ′ − S 1′ is also a monomial of multidegree deg(S ), and smaller than deg(S 1′ ). This
contradiction shows S ′ = 0.
Step 3: G is reduced. Let π : x0 , . . . , xr and σ : y0 , . . . , ys be admissible paths in
G with x0 < xr and y0 < ys , and let κ and µ be π- and σ-antitone. Suppose that
µ
µ
uκπ pκ(r)x0 pκ(0)xr divides either uσ pµ(s)y0 pµ(0)ys or uσ pµ(s)ys pµ(0)y0 . Then {x0 , . . . , xr } is a
subset of {y0 , . . . , ys }, and κ(b) = µ(σ−1 (xb )) for 0 < b < r. From admissibility follows
x0 ≤ y0 < ys ≤ xr and κ(0) ≥ µ(0) > µ(s) ≥ κ(r).
µ
If x0 < y0 , then pκ(r)x0 divides uσ , and so x0 = yt for some t < s with µ(t) = u = κ(r).
On the other hand, since yt ≤ y0 , it follows that µ(t) ≥ µ(0) > κ(r), a contradiction.
Hence x0 = y0 . Similarly, by a symmetric argument, xr = ys . This means that π is a
µ µ(s)µ(0)
and uσ fy0 ys
have
sub-path of σ. By Definition 1, π equals σ. Therefore, uκπ fxκ(r)κ(0)
0 xr
the same (total) degree, and hence they agree.

Corollary 4. IG is a radical ideal.
Proof. The assertion follows from Theorem 2 and the following general fact: A homogeneous ideal that has a Gröbner basis with square-free initial terms is radical. See the
proof of [3, Corollary 2.2] for details.

3. The primary decomposition
Since IG is radical, in order to compute the primary decomposition of the ideal
it is enough to compute the minimal primes. From this it will be easy to deduce the
irreducible decomposition of the variety VG of IG in the case of characteristic zero. The
following definition is needed: Two vectors v, w (living in the same K-vector space)
are proportional whenever v = λw or w = λv for some λ ∈ K. A set of vectors is
proportional if each pair is proportional. Since λ = 0 is allowed, proportionality is not
transitive: If v and w are proportional and if u and v are proportional, then u and w
need not proportional, because v may vanish.
Let VG be the variety of IG , which is a subset of KX0 ×Xin . As usual, elements of
X
K 0 ×Xin will be denoted with the same symbol p = (pix )i∈X0 ,x∈Xin as the unknowns
in the polynomial ring R = K[pix : (i, x) ∈ X0 × Xin ]. Any p ∈ KX0 ×Xin can be
written as a d0 × |Xin |-matrix. Each binomial equation in IG imposes conditions on
this matrix saying that certain submatrices have rank 1. For a fixed edge (x, y) in G
ij
the equations fxy
= 0 for all i, j ∈ X0 require that the submatrix (pkz )k∈X0 ,z∈{x,y} has
rank one. More generally, if K ⊆ G is a clique (i.e. a complete subgraph), then the
submatrix (pkz )k∈X0 ,z∈K has rank one. This means that all columns of this submatrix
are proportional. The columns of p will be denoted by p̃x , x ∈ Xin . A point p lies in
VG if and only if p̃x and p̃y are proportional for all edges (x, y) of G.
Even if the graph G is connected, not all columns p̃x must be proportional to each
other, since proportionality is not a transitive relation. Instead, there are “blocks” of
columns such that all columns within one block are proportional. For any subset Y ⊆
Xin denote by GY the subgraph of G induced by Y. Then:
• A point p lies in VG if and only if p̃x and p̃y are proportional whenever x, y ∈ S
lie in the same connected component of GS , where S = {x ∈ Xin : p̃x , 0}.
Let VG,Y be the set of all p ∈ KX0 ×Xin for which p̃x = 0 for all x ∈ Xin \ Y and
for which p̃x and p̃y are proportional whenever x, y ∈ Xin lie in the same connected

GENERALIZED BINOMIAL EDGE IDEALS

5

component of GY . Then
(1)

VG =

[

VG,Y .

Y⊆Xin

The sets VG,Y are rational irreducible algebraic varieties:
Lemma 5. For any Y ⊆ Xin the set VG,Y is the variety of the ideal IG,Y generated by
the monomials
(2)

pix

for all x ∈ Xin \ Y and i ∈ X0 ,

ij
f xy

and the binomials
for all i, j ∈ X0 and all x, y ∈ Y that lie in the same connected
component of GY . The ideal IG,Y is prime, and the variety VG,Y is rational.
1
Proof. The first statement follows from the definition of VG,Y . Write IG,Y
for the ideal
2
generated by all monomials (2), and for any Z ⊆ Y write IZ for the ideal generated by
ij

1
the binomials f xy , with i, j ∈ X0 and x, y ∈ Z. Then IG,Y
is obviously prime. Each of
2
the IZ is a 2×2 determinantal ideal. It is a classical (but difficult) result that this ideal is
the defining ideal of a Segre embedding, and that it is prime (see [6] for a rather modern
1
2 are geometrically prime, i.e. they remain prime over
proof). In fact, both IG,Y
and IZ
any field extension. Hence the ideal IG,Y is the sum of the geometrically prime ideals
1
2 for all connected components Z of G , and since the defining equations of
IG,Y
and IZ
Y
all these ideals involve disjoint sets of unknowns, IG,Y itself is prime. VG,Y is rational,
1
2 are rational.

since the varieties of IG,Y
and IZ

The decomposition (1) is not the irreducible decomposition of VG , because the union
is redundant. The redundant components can be removed using Lemma 5:
Lemma 6. Let Y, Z ⊆ Xin . Then VG,Y is contained in VG,Z if and only if the following
two conditions are satisfied:
• Y ⊆ Z.
• If x, y ∈ Y are connected in GZ , then they are connected in GY .
Proof. Assume that VG,Y ⊆ VG,Z . Then IG,Y ⊇ IG,Z . For any x ∈ Xin \ Z and any
i ∈ X0 this implies pix ∈ IG,Y . On the other hand, Lemma 5 shows that the point with
coordinates



if y ∈ Y,
1,
piy = 

0,
else,

lies in VG,Y and hence in VG,Z. This implies x ∈ Xin \ Y; and so Y ⊆ Z.
Let x ∈ Y. Choose two linearly independent non-zero vectors v, w ∈ Kd0 . By
Lemma 5 the matrix with columns



v,
if y ∈ Y is connected to x in GY ,




p̃y = 
w,
if y ∈ Y is not connected to x in GY ,




0,
else,

is contained in VG,Y and hence in VG,Z . Therefore, if z is connected to x in GZ , then it
is connected to x in GY .
Conversely, if both conditions are satisfied, then all defining equations of IG,Z lie
in IG,Y .


6

JOHANNES RAUH

T
Theorem 7. The primary decomposition of VG is IG = Y IG,Y , where the intersection
is over all Y ⊆ Xin such that the following holds: For any x ∈ Xin \ Y there are edges
(x, y), (x, z) in G such that y, z ∈ Y are not connected in GY . Equivalently, for any
x ∈ Xin \ Y the induced subgraph GY∪{x} has fewer connected components than GY .
Proof. First, assume that K is algebraically closed. By (1) and Lemma 5 it suffices
to show that the condition on Y stated in the theorem characterizes the maximal sets
VG,Y in the union (1) (with respect to inclusion). This follows from Lemma 6.
If K is not algebraically closed, then one can argue as follows: By [1] a binomial ideal has a binomial primary decomposition over some algebraic extension field
K̂ = K[α1 , . . . , αk ]. The algebraic numbers α1 , . . . , αk are coefficients of the defining
equations of the primary components. Let K be the algebraic closure of K. Since the
ideals IG,Y are defined by pure differences and since the ideals K ⊗ IG,Y are the primary
components of K ⊗ IG,Y in K ⊗ R it follows that the ideals IG,Y are already the primary
components of IG (in other words, the primary decomposition is independent of the
base field).

Remark 8 (Comparison to [4, 3]). Both [4] and [3] discuss Gröbner bases and primary
decompositions of binomial edge ideals with d0 = 2. Theorem 2 generalizes Theorems 2.1 from [3] and Theorem 3.2 in [4]. While the proofs in [3] and [4] use a case
by case analysis, the proof of Theorem 2 is more conceptual.
The primary decomposition in Theorem 7 generalizes Theorem 3.2 from [3]. The
proof of Theorem 7 relied on the irreducible decomposition of the corresponding variety, while the proof in [3] directly shows the equality of the two ideals.
Instead of describing the primary decomposition explicitly, [4] presents an algorithm to compute the primary decomposition. Since the primary decomposition of a
binomial edge ideal is independent of d0 , the same algorithm applies for all d0 . A nice
feature of the algorithm is that it works graph-theoretically.
Acknowledgement. This work has been supported by the Volkswagen Foundation.
I thank Nihat Ay, Thomas Kahle, Seth Sullivant, Jürgen Herzog and Takayuki Hibi.
Further thanks goes to the reviewer for many helpful remarks.
References
[1] Eisenbud, D., and Sturmfels, B., “Binomial ideals,” Duke Mathematical Journal, vol. 84, no. 1, pp.
1–45, 1996.
[2] Fink, A., “The binomial ideal of the intersection axiom for conditional probabilities,” Journal of
Algebraic Combinatorics, vol. 33, no. 3, pp. 455–463, 2011.
[3] Herzog, J., Hibi, T., Hreinsdóttir, F., Kahle, T., and Rauh, J., “Binomial edge ideals and conditional
independence statements,” Advances in Applied Mathematics, vol. 45, no. 3, pp. 317 – 333, 2010.
[4] Ohtani, M., “Graphs and ideals generated by some 2-minors.” Commun. Algebra, vol. 39, no. 3, pp.
905–917, 2011.
[5] Rauh, J., and Ay, N., “Robustness, canalyzing functions and systems design,” submitted, 2012.
[6] Sturmfels, B., “Gröbner bases of toric varieties,” Tohoku Mathematical Journal, vol. 43, pp. 249 –
261, 1991.
[7] Swanson, I., and Taylor, A., “Minimal primes of ideals arising from conditional independence statements,” Preprint: arXiv:1107.5604v3, 2011.
E-mail address: jrauh@mis.mpg.de
Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, D-04103 Leipzig,Germany

