arXiv:1503.08080v2 [] 25 Jan 2016

ALGEBRAICALLY RIGID SIMPLICIAL COMPLEXES AND
GRAPHS
KLAUS ALTMANN, MINA BIGDELI, JÜRGEN HERZOG AND DANCHENG LU
Abstract. We call a simplicial complex algebraically rigid if its Stanley-Reisner
ring admits no nontrivial infinitesimal deformations, and call it inseparable if
it does not allow any deformation to other simplicial complexes. Algebraically
rigid simplicial complexes are inseparable. In this paper we study inseparability
and rigidity of Stanley-Reisner rings, and apply the general theory to letterplace
ideals as well as to edge ideals of graphs. Classes of algebraically rigid simplicial
complexes and graphs are identified.

Introduction
In the study of monomial ideals it is a popular technique to polarize in order to
obtain squarefree monomial ideals. Let S = K[x1 , . . . , xn ] be the polynomial ring
in n indeterminates over the field K. Given a monomial ideal I ⊆ S, the polarized
ideal I ℘ of I is a squarefree monomial ideal defined in a larger polynomial ring S ℘
and S/I is obtained from S ℘ /I ℘ by reduction modulo a regular sequence of linear
forms consisting of differences of variables, see [7, page 19] for details. In other
words, S ℘ /I ℘ may be viewed an unobstructed deformation of S/I over a suitable
affine space.
The natural question arises whether S ℘ /I ℘ or any other K-algebra defined by
a squarefree monomial ideal admits further unobstructed deformations, or at least
non-trivial infinitesimal deformations. This may be indeed the case as the third
author learned from Fløystad.
Separation. Let I ⊆ S be a squarefree monomial ideal, and let y be an indeterminate
over S. Fløystad (see [4]) calls a monomial ideal J ⊆ S[y] a separation of I for the
variable xi if the following conditions hold:
(i) the ideal I is the image of J under the K-algebra homomorphism S[y] → S
with y 7→ xi and xj 7→ xj for all 1 ≤ j ≤ n;
(ii) xi and y divide some minimal generators of J;
(iii) y − xi is a non-zero divisor of S[y]/J.
The ideal I is called separable if it admits a separation, otherwise it is called inseparable.
2010 Mathematics Subject Classification. Primary 13D10, 13C13; Secondary 05E40.
Key words and phrases. infinitesimal deformations, rigidity, Stanley-Reisner ideals, edge ideals.
The paper was written while the second and the fourth authors were visiting the Department of
Mathematics of University Duisburg-Essen. They want to express their thanks for the hospitality.
Corresponding author: Dancheng Lu.
1

If J ⊆ S[y] is a separation of I for the variable xi , then K[t] → S[y]/J, t 7→ y −xi ,
is a non-trivial unobstructed deformation of S/I over A1 = Spec K[t]. The simplest
example of a squarefree monomial ideal which admits a separation is the ideal I =
(x1 x2 , x1 x3 , x2 x3 ). One possible separation of I is the ideal J = (x1 y, x1x3 , x2 x3 ).
Infinitesimal deformations. But even if I ⊆ S is inseparable, it still may admit
infinitesimal deformations. We denote by ε a non-zero term with ε2 = 0. Let
J ⊆ S[ε] be an ideal. Then S[ε]/J is called an infinitisimal deformation of S/I if
the canonical K-algebra homomorphism K[ε] → S[ε]/J is flat and if S/I is obtained
from S[ε]/J by reduction modulo ε. Thus if I = (f1 , . . . , fm ), then J = (f1 +
g1 ε, . . . , fm + gm ε) and K[ε] → S[ε]/J is flat if and only if ϕ : I → S/I with fi 7→
gi + I is a well-defined S-module homomorphism. In other words, the infinitesimal
deformations of S/I are in bijection to the elements of I ∗ = HomS (I, S/I).
Cotangent functors. Recall that a K-linear map ∂ : S → S is called a K-derivation
if ∂f g = f ∂g + g∂f . The set of K-derivations has a natural structure as an Smodule, and is denoted DerK (S). In fact, DerK (S) is a free S-module whose basis
consists of the partial derivatives ∂/∂xi . The infinitesimal deformation S[ε]/J of
S/I is called trivial if there exists a K-algebra automorphism S[ε] → S[ε] which
maps J to IS[ε]. This is the case, if and only if there exists ∂ ∈ DerK (S) such that
J = (f1 +∂f1 ε, . . . , fm +∂fm ε). Thus if we consider the natural map δ ∗ : DerK (S) →
I ∗ which assigns to ∂ ∈ DerK (S) the element δ ∗ (∂) with δ ∗ (∂)(fi ) = ∂fi + I, then
the non-zero elements of Coker δ ∗ are in bijection to the isomorphism classes of
non-trivial infinitesimal deformations of S/I, see for example [6, Lemma 2.4]. This
cokernel is denoted by T 1 (S/I) and is called the first cotangent functor of S/I. The
cotangent functors have been first introduced by Lichtenbaum and Schlessinger [9].
The K-algebra S/I is called rigid if it does not admit any non-trivial infinitesimal
deformations. Hence S/I is rigid if and only if T 1 (S/I) = 0. For simplicity we call
I rigid if S/I is rigid. The simplest example of a squarefree monomial ideal which is
inseparable but not rigid, is the ideal I = (x1 x2 , x2 x3 , x3 x4 ), see Proposition 3.7(a)
and Theorem 3.10. We recommend the reader to consult [10, Section 3] for general
basic facts about deformation theory.
Rigidity of simplicial complexes. In the case that I ⊆ S is a monomial ideal, T 1 (S/I)
is a Zn -graded S-module. If moreover I is a squarefree monomial ideal, then the
Zn -graded components of T 1 (S/I) have a combinatorial interpretation as was shown
by the first author and Christophersen in [2] and [1]. We recall some of these results
in Section 1 of this paper because they are crucial for later applications.
Recall that a simplicial complex ∆ on the vertex set V is a collection of subset of
V such that whenever F ∈ ∆ and G ⊂ F , then G ∈ ∆. Frequently we denote the
vertex set of ∆ by V (∆).
Since I is a squarefree monomial ideal, there exists a unique simplicial complex
∆ such that I = I∆ , where I∆ is the Stanley–Reisner ideal of ∆. As usual, S/I∆ is
denoted by K[∆] and is called the Stanley–Reisner ring of ∆. For simplicity we will
write T 1 (∆) for T 1 (K[∆]). We say that ∆ is algebraically rigid (with respect to K)
if K[∆] is rigid. Actually it is shown in Section 1 that algebraic rigidity of simplicial
2

complexes does not depend on K. There is the concept of rigid simplicial complexes,
meaning that the simplicial complex does not admit any non-trivial automorphism.
In this paper rigidity means algebraic rigidity, and will simply say that ∆ is rigid if
it is algebraically rigid.
Description of contents. The aim of this paper is to characterize rigid simplicial
complexes in combinatorial terms and exhibit classes of them. By what we said
before, it follows that ∆ is rigid if and only if T 1 (∆)c = 0 for all c ∈ Zn . The
important facts, shown in [2], regarding the graded components of T 1 (∆) that will
be used throughout the paper, are the following: write c = a − b with a, b ∈ Nn
and supp a ∩ supp b = ∅. Here for a vector a, supp a is defined to be the set
{i ∈ [n] : ai 6= 0} where the ai are the components of a. Then
(i) T 1 (∆)a−b = 0 if b 6∈ {0, 1}n, and if b ∈ {0, 1}n , then T 1 (∆)a−b depends
only on supp a and supp b;
(ii) T 1 (∆)a−b = T 1 (link∆ supp a)−b .
We say that ∆ is ∅-rigid if T 1 (∆)−b = 0 for all b ∈ {0, 1}n. Thus, by (ii), ∆
is rigid, if and only if all its links are ∅-rigid. These and other facts are recalled
in Section 1. We close the section by applying the general theory to characterize
inseparable simplicial complexes. Say, ∆ is a simplicial complex on the vertex set
[n]. To each vertex i of ∆ one attaches a graph G{i} (∆) whose vertices are those
faces F ∈ ∆ for which F ∪ {i} 6∈ ∆. The edges of G{i} (∆) are those {F, G} for
which F ( G or G ( F . In Theorem 1.8 we show that ∆ is inseparable if and only
if G{i} (∆) is connected for i = 1, . . . , n, and that this is equivalent to the condition
that T 1 (∆)−ei = 0 for i = 1, . . . , n. Here ei denotes the ith canonical basis vector
of Zn .
Let dimK T 1 (∆)−ei = k. Iterating simple separation steps one can construct a
e on the vertex set ([n] \ {i}) ∪ {v0 , v1 , . . . , vk } defined as ksimplicial complex ∆
e −b = 0 for all b with
separation of ∆ for the vertex i having the property that T 1 (∆)
e by cutting down
supp b ⊆ {v0 , . . . , vk }, and such that K[∆] is obtained from K[∆]
by a regular sequence consisting of differences of variables.
In Section 2 we consider various operations on simplicial complexes and study
their behaviour with respect to rigidity. In Proposition 2.3 it is shown that the join
∆1 ∗ ∆2 of the simplicial complexes ∆1 and ∆2 is rigid if and only if this is the case
for ∆1 and ∆2 .
More complicated is the situation for the disjoint union of two simplicial complexes
∆1 and ∆2 . Here we assume that none of the two simplicial complexes is the empty
set and that their 0-dimensional faces correspond to their vertex set, a condition
that we do not require in general. Under these (very weak) assumptions it is shown
in Theorem 2.5 that ∆1 ∪ ∆2 is inseparable if and only if ∆1 and ∆2 are simplices,
and that ∆1 ∪ ∆2 is rigid if and only in addition one of the simplices has positive
dimension. As a consequence we see that a disconnected simplicial complex of
positive dimension is never rigid, unless all its components are simplices.
Finally in Theorem 2.10 we consider what we call the circ of two simplicial
complexes, denoted by ∆1 ◦ ∆2 . Suppose that Vi is the vertex set of ∆i and
3

that V1 ∩ V2 = ∅. Then, by definition, F ⊆ V1 ∪ V2 is a face of ∆1 ◦ ∆2 if
and only if either F ∩ V1 is a face of ∆1 or F ∩ V2 is a face of ∆2 . Note that
∆1 ◦ ∆2 = (∆1 ∗ hV2 i) ∪ (hV1 i ∗ ∆2 ) and that I∆1 ◦∆2 = (I∆1 I∆2 ). It turns out that
∆1 and ∆2 are rigid if ∆1 ◦ ∆2 is rigid and I∆1 , I∆2 6= 0. The converse is true only
under some additional assumptions.
A motivation for us to study the circ-operation resulted from the desire to classify
the rigid letterplace ideals, see [4]. Given two finite posets P and Q, one assigns a
monomial ideal L(P, Q), which in the case P = [n] or Q = [n] is called a letterplace
ideal or a co-letterplace ideal, respectively. Letterplace and co-letterplace ideals have
been considered before in [3]. In the paper [4] it is shown that all letterplace ideals
are inseparable. Here we show that L(P, Q) is rigid if and only if no two elements of
P are comparable, see Theorem 2.12. In the proof of one direction of this theorem
we need the circ-construction.
The last section of this paper is concerned with the rigidity of edge ideals. Given a
finite simple graph on the vertex set [n] one assigns to it the so-called edge ideal I(G)
generated by the monomials xi xj with {i, j} an edge of G. Obviously I(G) = I∆(G)
for some simplicial complex ∆(G). This simplicial complex is called the independence
complex of G. Indeed, its faces are the independent sets of G, that is, the subsets
of [n] which do not contain any edge of G. We say that G is rigid if ∆(G) is
rigid. Again there exist already various concepts of rigid graphs which should not
be confused with the definition of rigidity used in this paper. Similarly, we say that
G is inseparable if I(G) is inseparable. The ultimate goal would be to classify all
rigid and inseparable graphs. It is not clear whether a nice description of these
classes of graphs is possible. However with some additional assumptions on the
graphs, inseparable or rigid graphs can be characterized combinatorially. Recall
that a vertex i of G is called a free vertex if it belongs to only one edge, and an edge
is called a leaf if it has a free vertex. Finally an edge e of G is called a branch, if
there exists a leaf e′ with e′ 6= e such that e ∩ e′ 6= ∅. Our main result on rigidity of
graphs is formulated in Theorem 3.10: Let G be a graph on the vertex set [n] such
that G does not contain any induced cycle of length 4, 5 or 6. Then G is rigid if
and only if each edge of G is a branch and each vertex of a 3-cycle of G belongs to
a leaf. Theorem 3.10 has several consequences. In Corollary 3.11 it is shown that a
chordal graph G is rigid if and only if each edge of G is a branch and each vertex
of a 3-cycle of G belongs to a leaf. Another consequence is the fact that a graph
with the property that all cycles have length ≥ 7 is rigid if and only if each of its
edges is a branch, see Corollary 3.12. This result implies in particular that a forest
consisting only of branches is rigid. Finally we notice in Corollary 3.13 that a cycle
is rigid if and only if it is a 4- or 6-cycle.
1. The cotangent functor T 1 and rigid and inseparable
Stanley–Reisner rings
The cotangent functor T 1 . Let ∆ be a simplicial complex on the vertex set V (∆) =
[n] where [n] = {1, . . . , n}. We denote by [∆] the set of elements i ∈ [n] with
{i} ∈ ∆. Let F1 , . . . , Fm ⊆ [n]. We denote by hF1 , . . . , Fm i the smallest simplicial
4

complex ∆ with Fi ∈ ∆ for i = 1, . . . , m. The elements of ∆ are called faces. A
facet of ∆ is a face of ∆ which is maximal with respect to inclusion. The set of
facets of ∆ will be denoted by F (∆).
We fix a field K. The ideal I∆ denotes the Stanley-Reisner ideal in S = K[x1 , . . . , xn ],
that is,Qthe ideal generated by the monomial xN with N ⊆ [n] a non-face of ∆. Here
xN = i∈N xi . The K-algebra K[∆] = S/I∆ is called the Stanley-Reisner ring of
∆.
The cotangent cohomology modules T i (K[∆]) which we denote by T i (∆) are Zn graded. We quote several facts about the Zn -graded components of T i (∆) which
were shown in [2].
We write c ∈ Zn as a − b with a, b ∈ Nn and supp a ∩ supp b = ∅, and set
A = supp a and B = supp b. Here N denotes the set of non-negative integers,
and as in the introduction the support of a vector a ∈ Nn is defined to be the set
supp a = {i ∈ [n] : ai 6= 0}.
Theorem 1.1 ([2], Theorem 9). (a) T i (∆)a−b = 0 if b 6∈ {0, 1}n .
(b) Assuming b ∈ {0, 1}n , T i (∆)a−b depends only on A and B.
Recall that for a subset A of [n], the link of A is defined to be
link∆ A = {F ∈ ∆ : F ∩ A = ∅, F ∪ A ∈ ∆}
with vertex set V (link∆ A) = [n] \ A.
We will also need the following result:
Proposition 1.2 ([2], Proposition 11). (a) T i (∆)a−b = 0, unless
A∈∆

and

∅=
6 B ⊆ [link∆ A].

(b) T i (∆)a−b = T i (link∆ A)−b .
In the present paper, we are only interested in T 1 . Because of Proposition 1.2(b)
it is important to know how to compute T 1 (∆)−b for B ⊆ [∆]. For this purpose we
introduce some notation.
Let Y be a collection of subsets of [n]. We set K0 (Y) = {λ : Y → K} and

K1 (Y) = λ : {(Y0 , Y1 ) ∈ Y 2 : Y0 ∪ Y1 ∈ Y} → K

and define the K-linear map d : K0 (Y) → K1 (Y) by (dλ)(Y0, Y1 ) = λ(Y1 ) − λ(Y0 ).
Next given B ⊆ [n] and ∆, we define
NB (∆) = {F ∈ ∆ : F ∩ B = ∅, F ∪ B ∈
/ ∆},
′
eB (∆) = {F ∈ NB (∆) : there exists B ( B with F ∪ B ′ ∈
N
/ ∆}.

With the notation introduced one has

Proposition 1.3 ([2], Corollary 6). (a) Suppose |B| ≥ 2. Then

(d,r)
eB (∆)) ,
T 1 (∆)−b = Ker K0 (NB (∆)) −→ K1 (NB (∆)) ⊕ K0 (N

where d : K0 (NB (∆)) → K1 (NB (∆)) is the map as defined above and r : K0 (NB (∆)) →
eB (∆)) is the restriction map.
K 0 (N
5

(b) For |B| = 1, the K-dimension of T 1 (∆)−b is one less than the K-dimension
of the kernel given in (a).
Rigidity. The simplicial complex ∆ is called ∅-rigid if T 1 (∆)−b = 0 for all b ∈
{0, 1}n . For ∅-rigidity it is enough to check the vanishing of T 1 (∆)−b for b ∈ {0, 1}n
with supp b ⊆ [∆]. It follows from Proposition 1.2 that ∆ is rigid if and only if
link∆ A is ∅-rigid for all A ∈ ∆. Thus we will assume a = 0 from now on.
As an immediate consequence of Proposition 1.3 one obtains
Corollary 1.4. (a) Suppose that |B| ≥ 2. Then T 1 (∆)−b = ΛB (∆), where
ΛB (∆) = {λ : NB (∆) → K : λ|NeB (∆) = 0 and λ(F ) = λ(G) whenever F ⊆ G}.
(b) dimK T 1 (∆)−b = dimK ΛB (∆) − 1 if |B| = 1.
Let B be a subset of [n]. We define GB (∆) to be the graph whose vertex set is
NB (∆) and for which {F, G} is an edge of GB (∆) if and only if F ( G or G ( F . It
follows that λ ∈ ΛB (∆) is constant on the connected components of GB (∆). Note
eB (∆) = ∅. We see that if |B| ≥ 2, then
that if |B| = 1, then N

(1)

dimK T 1 (∆)−b = number of connected components of GB (∆)
eB (∆),
which contain no element of N

and if B = {i}, then
(2)

dimK T 1 (∆)−ei = number of connected components of G{i} (∆) − 1

Hence the rigidity of a simplicial complex is independent of the field K.
Examples 1.5. (a) Let 2[n] = h[n]i be the simplex on the vertex set [n]. For each
eB (2[n] ) = ∅. This implies that 2[n] is ∅-rigid. Moreover, for each
B ⊆ [n] we have N
[n]
A ∈ 2 , its link is a simplex, too. Thus, 2[n] is rigid. Of course, this is known before
because K[2[n] ] = K[x1 , . . . , xn ].
(b) Fix n ≥ 2, and let Γ = 2[n] \{[n]} be the boundary of 2[n] . Then N[n] (Γ) = {∅},
e[n] (Γ) = ∅. In particular, dimK T 1 (Γ)−b = 1 for b = (1, . . . , 1). Again this
but N
follows also directly from the fact that K[Γ] = K[x1 , . . . , xn ]/(x1 x2 · · · xn ).
(c) let ∆ = h{1}, . . . , {n}i. Then ∆ is 0-dimensional. The set B = {1} yields
eB (∆) = ∅. Hence, T 1 (∆)−b 6= 0 for n ≥ 3, and so ∆
NB (∆) = {{2}, . . . , {n}} and N
is not rigid. Note that K[∆] = K[x1 , . . . , xn ]/(xi xj : i 6= j).
The ideal (xi xj : i 6= j) may be interpreted as the edge ideal of the complete
graph on the vertex set [n]. Rigidity of edge ideals will be discussed in details in
Section 3.
The following lemma tells us when T 1 (∆)−b vanishes if supp b 6∈ ∆. We denote
by 2B the simplex on the vertex set B.
Lemma 1.6. Let ∆ be a simplicial complex on the vertex set [n], and let b ∈ {0, 1}n .
Let B = supp b and assume that B 6∈ ∆.
6

eB (∆) 6= ∅.
(a) Suppose that |B| ≥ 2. Then T 1 (∆)−b = 0 if and only if N
1
B
B
Moreover, T (∆)−b 6= 0 implies that the boundary 2 \{B} of 2 is contained
in ∆.
(b) Suppose that |B| = 1. Then T 1 (∆)−b = 0.
Proof. Since B 6∈ ∆ it follows that ∅ ∈ NB (∆). Therefore, λ(F ) = λ(∅) for all
λ ∈ ΛB (∆). Thus the K-vector space ΛB (∆) is generated by one element λ0 which
eB (∆) 6= ∅ and which may be chosen to be the
is forced to be the 0-element if N
constant map with λ0 (∅) = 1, otherwise. This proves (a). Also (b) follows from
this considerations keeping in mind Corollary 1.4(b). Alternatively, statement (b)
follows from Lemma 1.2(a).

Separation. Let, as before, ∆ be a simplicial complex on the vertex set [n]. We say
that ∆ is separable, if for some i, I∆ admits a separation for xi . Otherwise, we say
that ∆ is inseparable. In the further discussions we refer to the conditions (i), (ii)
and (iii) for separation, as given in the introduction.
Let I = I∆ be minimally generated by the monomials u1 , . . . , um . We first observe:
Lemma 1.7. If J is a separation of I for the variable xi , then T 1 (∆)−ei 6= 0.
Proof. By condition (iii), S/I is obtained from S[y]/J by reduction modulo a linear
form which is a regular element on S[y]/J. This implies that I and J are minimally
generated by the same number of generators. Let J be minimally generated by
v1 , . . . , vm . We may assume that y divides v1 , . . . , vk but does not divide the other
generators of J. We may furthermore assume that for all i, vi is mapped to ui under
the K-algebra homomorphism (i). Then we may write
J = (u1 + (u1 /xi )(y − xi ), . . . , uk + (uk /xi )(y − xi ), uk+1, . . . , um ).
From this presentation and by (iii) it follows that S[y]/J is an unobstructed deformation of S/I induced by the element [ϕ] ∈ T 1 (S/I)−ei , where ϕ ∈ I ∗ is the
S-module homomorphism with ϕ(uj ) = uj /xi + I for j = 1, . . . , k and ϕ(uj ) = 0,
otherwise.
Condition (ii) makes sure that S[y]/J is a non-trivial deformation of S/I. Indeed,
suppose [ϕ] = 0. Observe, that deg ϕ = −ei . Therefore, ϕ ∈ (Im δ ∗ )−ei , which is the
K-vector space spanned by ϕi = δ ∗ (∂/∂xi ). Here δ ∗ : DerK (S) → I ∗ is the map as
defined in the introduction with δ ∗ (∂)(f ) = ∂f + I for ∂ ∈ DerK (S) and f ∈ I. It
follows that ϕ = λϕi for some λ ∈ K. Since ϕ(u1) = u1 /xi + I = λϕi (u1 ) it follows
that λ = 1. On the other hand, by condition (ii), there exists j > k such that xi |uj
and ϕ(uj ) = I 6= uj /xi + I = ϕi (uj ). This is a contradiction.

It follows from the above result that ∆ is inseparable if T 1 (∆)−ei = 0 for i =
1, . . . , n. Moreover the deformation K[y] → S[y]/J induces an infinitesimal deformation K[ε] → S[ε]/J¯ by reduction modulo y 2. As explained in the introduction,
this infinitesimal deformation yields an element in T 1 (∆). This assignment is called
the Kodaira-Spencer map. The arguments given above, even show that the image of the deformation K[y] → S[y]/J in T 1 (∆) via the Kodaira-Spencer map is
non-trivial.
7

Finally we obtain
Theorem 1.8. The following conditions are equivalent:
(a) ∆ is inseparable.
(b) G{i} (∆) is connected for i = 1, . . . , n.
(c) T 1 (∆)−ei = 0 for i = 1, . . . , n.
Proof. (c) ⇒ (a) follows from Lemma 1.7, and (b) ⇐⇒ (c) follows from the equality
(2) in the preceding subsection.
(a) ⇒ (b): Suppose G{i} (∆) is not connected for some i. Then the vertex set of
G{i} (∆) can be written as a disjoint union V (G{i} (∆)) = A ∪ B such that for all
F ∈ A and all G ∈ B, neither F ( G nor G ( F .
Let I = I∆ , I(A) = (xF : F ∈ A) and I(B) = (xG : G ∈ B). Then
I = (xi I(A), xi I(B), u1 , u2, . . . , ut ),
where none of the uj is divisible by xi .
Note that if {xF1 , . . . , xFr } is the minimal set of monomial generators of I(A) and
{xG1 , . . . , xGs } is the minimal set of monomial generators of I(B), then
{xi xF1 , . . . , xi xFr , xi xG1 , . . . , xi xGs }
is the set of monomials of the minimal monomial set of generators of I which are
divisible by xi . Thus, the ideal J = (yI(A), xiI(B), u1 , u2 , . . . , ut) ⊆ S[y] satisfies
the conditions (i) and (ii) of a separation of I. We will show that y − xi is a
non zero-divisor of S[y]/J. This will then imply that ∆ is separable, yielding a
contradiction.
Indeed, suppose y−xi is a zero-divisor of S[y]/J. Then y−xi belongs to a minimal
prime ideal P of J. Since P is a monomial prime ideal it follows that y, xi ∈ P .
Now let F ∈ A and G ∈ B and suppose that F ∪ G ∈ ∆. Then F ∪ G ∈ N{i} (∆),
and hence F ∪ G ∈ A since F ( F ∪ G, and similarly F ∪ G ∈ B since G ( F ∪ G.
This is a contradiction. Therefore, F ∪G 6∈ ∆ for all F ∈ A and G ∈ B. This implies
that I(A)I(B) ⊆ I. It follows that I(A)I(B) ⊆ J, since xi does not divide any of
the generators of I(A)I(B). Now since I(A)I(B) ⊆ P we conclude that I(A) ⊆ P
or I(B) ⊆ P . As P is a minimal prime ideal of J, we see that y 6∈ P if I(A) ⊆ P
and xi 6∈ P if I(B) ⊆ P . In any case we obtain a contradiction.

k-Separation. Let A and B be two finite collections of sets with F ∩ G = ∅ for all
F ∈ A and G ∈ B. As it is common, we denote by A ∗ B the join of A and B,
where A ∗ B = {F ∪ G : F ∈ A, G ∈ B}. If Γ and Σ are simplicial complexes,
then the join Γ ∗ Σ is again a simplicial complex. The vertex set of Γ ∗ Σ is the set
1
V (Γ) ∪ V (Σ). In [1, Lemma 4.3], it was shown that all T−e
(X) vanish whenever X
i
is a combinatorial manifold without boundary. Now we will show that beyond this
special case the deformations in degree −ei are unobstructed. More precisely, we
prove the following statement:
Proposition 1.9. Assume that V (∆) = [n] and dimK T 1 (∆)−ei = k. Then there
e on the vertex set ([n]\{i})∪{v0 , . . . , vk } such that I e is
exists a simplicial complex ∆
∆
8

e −b = 0
obtained from I∆ by k times separations for the variable xi . Moreover T 1 (∆)
for any b whose support supp b ⊆ {v0 , . . . , vk }.
Proof. We may decompose ∆ as a disjoint union
{∅, {i}} ∗ link∆ {i} ∪ N{i} (∆).
Since dimK T 1 (∆)−ei = k, we have N{i} (∆) splits into k + 1 connected components
N{i} (∆) = A0 ∪ A1 ∪ . . . ∪ Ak .
As in the proof of Theorem 1.8, we can express I∆ as
I∆ = ({xi xF : F ∈

k
[

Aℓ }, u1 , . . . , ut ),

ℓ=0

where the generators uj are not divisible by xi .
e on the vertex set ([n]\{i})∪{v0 , v1 , . . . , vk }
We define a new simplicial complex ∆
by
k
[
e = Ω ∗ link∆ {i} ∪ (Ωℓ ∗ Aℓ ).
∆
ℓ=0

Here Ω = h{v0 , . . . , vk }i, and Ωℓ = h{v0 , . . . , vk } \ {vℓ }i for ℓ = 0, . . . , k.
Set T = K[x1 , . . . , xi−1 , xi+1 , . . . , xn , y0 , . . . , yk ]. Then I∆e is an ideal of T and
I∆e = ({yℓ xF : ℓ = 0, . . . , k, F ∈ Aℓ }, u1 , . . . , ut).

Theorem 1.7 provides the induction step of proving the k-separability. Thus applying induction it can be shown that S/I is isomorphic to T /I∆e modulo the regular
e −b = 0 for any b whose
sequence y1 − y0 , . . . , yk − yk−1 , and furthermore T 1 (∆)
support supp b ⊆ {v0 , . . . , vk }.

We call I∆e a k-separation of I∆ .
2. Joins, disjoint unions and circs of simplicial complexes
In this section we consider simplicial complexes arising from pairs of simplicial
complexes and study their behaviour with respect to rigidity. Part of the results
will be applied to classify rigid algebras defined by letterplace ideals.
Monomial localization. In the following localization will be one of the tools in the
proofs. Let K be a field, S = K[x1 , . . . , xn ] the polynomial ring over K, I ⊆ S a
monomial ideal and P ⊆ S a monomial prime ideal. Then P = PF where F ⊆ [n]
and PF = (xi : i ∈ F ).
We observe that if (S/I)P denotes ordinary localization of S/I with respect to the
prime ideal P , then (S/I)P = SP /I(P )SP , where I(P ) ⊆ S(P ) := K[xi : i ∈ F ] is
the monomial ideal which is obtained from I by the substitution xi 7→ 1 for i 6∈ F .
The ideal I(P ) is called the monomial localization of I with respect to P .
Lemma 2.1. Let I ⊆ S be a monomial ideal, P ⊆ S a monomial prime ideal, and
F ⊆ [n].
9

(a) T 1 (S/I)P ∼
= (T 1 (S(P )/I(P ))[xi : i 6∈ P ])P .
(b) Suppose that T 1 (S(P )/I(P )) 6= 0. Then T 1 (S/I) 6= 0.
(c) Let I be a squarefree monomial ideal. Let ∆ be the simplicial complex on
the vertex set [n] with I∆ = I. Then S(PF )/I∆ (PF ) = S(PF )/IΓ , where
F = [n] \ F and Γ = link∆ (F ). In particular, Γ is rigid if ∆ is rigid.
Proof. (a) Note that DerK (S) = HomS (ΩS/K , S), where ΩS/K is module of differentials of S/K, see [5, Definition, p. 384]. Since ΩS/K localizes (see [5, Proposition
16.6], the same holds true for DerK (S). In other words, DerK (S)P = DerK (SP ).
From this fact one easily deduces that T 1 (S/I) localizes, that is T 1 (S/I)P = T 1 ((S/I)P ).
Therefore,
/ P ])P
T 1 (S/I)P ∼
= T 1 ((S(P )/I(P ))[xi : xi ∈
= T 1 ((S/I(P )S)P ) ∼
= T 1 ((S/I)P ) ∼
1
∼
= (T (S(P )/I(P ))[xi : i 6∈ P ])P .
The last isomorphism follows from the fact that T 1 (R[y]) ∼
= T 1 (R) ⊗R R[y] =
1
T (R)[y] for a polynomial extension R → R[y].
(b) Suppose that T 1 (S(P )/I(P )) 6= 0 and let mP be the graded maximal ideal of
S(P ) . Then T 1 (S(P )/I(P ))mP 6= 0 because mP ∈ Supp(T 1 (S(P )/I(P ))). It follows
that (T 1 (S(P )/I(P ))[xi : i 6∈ P ])P 6= 0, since mP S = P . Hence the assertion follows
from part (a).
(c) Since F (Γ) = {G \ F : G ∈ F (∆), F ⊆ G}, we obtain that IΓ ⊆ S(PF ) is
given by
\
\
PG .
IΓ =
PF \(G\F ) =
G∈F (∆),F ⊆G

G∈F (∆),F ⊆G

On the other hand,
I∆ (PF ) =

\

PG (PF ) =

\

PG .

G∈F (∆),F ⊆G

G∈F (∆)

Hence IΓ = I∆ (PF ).



Note that the fact stated in Lemma 2.1(c) which says that each link of a rigid
simplicial complex is again rigid can also be deduced from Proposition 1.2(b).
Example 2.2. Let I be a squarefree monomial ideal of K[x1 , . . . , xn ] generated in
degree (n − 1).
(a) If n = 3, then I is rigid if and only if I is generated by two monomials.
(b) If n ≥ 4, then I is not rigid.
Proof. In the following we may assume that I is not a principal ideal, because in
this case I is a complete intersection generated in degree ≥ 2, and hence I is not
rigid.
(a) For n = 3, I is an edge ideal of a nonempty simple graph with 3 vertices.
Edge ideals will be treated in detail on Section 3. A nonempty simple graph with
3 vertices is an isolated edge or a path of length 2 or a triangle. It follows from
Theorem 3.10 that in those graph, only the second is rigid. This proves our result.
10

(b) We proceed by induction on n. Assume n = 4. If I is generated by 4
monomials, then the monomial localization I(P ) of I with respect to P = (x1 , x2 , x3 )
is the edge ideal of a triangle, and so I(P ) is not rigid because of Theorem 3.10. By
Lemma 2.1(b) it follows that I is not rigid. If I is generated by 3 monomials, then I
is the product of a variable, say x1 , and the edge ideal (x2 x3 , x2 x4 , x3 x4 ) of a triangle,
and so it is not rigid. Indeed, this follows again from Lemma 2.1(b) by monomial
localization with respect to P = (x2 , x3 , x4 ). If I is generated by 2 monomials, then
it is the product of a monomial of degree 2 and an ideal generated by variables, and
again I is not rigid. Assume n > 4. If I is generated by n monomials, then the
monomial localization I(P ) of I with respect to P = (x1 , x2 , x3 ) is the edge ideal of
a triangle, and so I is not rigid. If I is generated by less than n monomials, then I
is the product of a variable and an ideal J which is generated in degree n − 2 in the
remaining n − 1 variables. It follows from the induction hypothesis that J is not
rigid and so I is not rigid.

Joins. Note that the notation “join” has been defined in the first section. Thus, if
∆1 and ∆2 are simplicial complexes on disjoint vertex sets, then the join ∆1 ∗ ∆2 is
a simplicial complex on the vertex set V (∆1 ) ∪ V (∆2 ).
In the remaining part of this subsection we always assume that ∆1 and ∆2 are
simplicial complexes with disjoint vertex sets.
Proposition 2.3. Let I∆1 ⊆ K[x1 , . . . , xn ] and I∆2 ⊆ K[y1 , . . . , ym ]. Then
T 1 (∆1 ∗ ∆2 ) = T 1 (∆1 )[y1 , . . . , ym ] ⊕ T 1 (∆2 )[x1 , . . . , xn ].
In particular ∆1 ∗ ∆2 is rigid if and only if ∆1 and ∆2 are rigid.
Proof. Set I = I∆1 ∗∆2 . Then I = I1 + I2 , where I1 = I∆1 S, I2 = I∆2 S and where
S = K[x1 , . . . , xn , y1 , . . . , ym]. We set R = S/I.
Furthermore let
α

· · · −→ F2 −→ F1 −→ S −→ S/I1 −→ 0
be the a resolution of I1 and let
β

· · · −→ G2 −→ G1 −→ S −→ S/I2 −→ 0
be the a resolution of I2 . Then, since TorSi (S/I1 , S/I2 ) = 0 for i > 0, the tensor
product of the two above resolutions produces the following free S-resolution of S/I:
γ

· · · −→ F2 ⊕ (F1 ⊗ G1 ) ⊕ G2 −→ F1 ⊕ G1 −→ I −→ 0
Let f ⊗ g ∈ F1 ⊗ G1 . Then γ(f ⊗ g) = β(g)f − α(f )g ∈ I(F1 ⊕ G1 ). It follows that
(F1 ⊗ G1 → F1 ⊕ G1 ) ⊗S R = 0. This implies that
(3)

I ∗ = Ker(F1∗ ⊕ G∗1 −→ F2∗ ⊕ G∗2 ) = I1∗ ⊕ I2∗ .

Here M ∗ = HomS (M, S/I) for any graded S-module M.
Assume that I1 is minimally generated by u1 , . . . , ur and I2 is minimally generated
by v1 , . . . , vs . Let f1 , . . . , fr be the basis of F1 , where fi is mapped to ui in I1 for
1 ≤ i ≤ r and let g1 , . . . , gs be the basis of G1 , where gj is mapped to vj in I2 for
1 ≤ j ≤ s. Also we denote by f1∗ , . . . , fr∗ the basis F1∗ dual to f1 , . . . , fr . In other
11

words, fi∗ (fj ) = 1 ∈ S if i = j and fi∗ (fj ) = 0 if i 6= j. Similarly, we denote by
g1∗ , . . . , gs∗ the dual basis of g1 , . . . , gs .
Then Im δ ∗ ⊆ F1∗ ⊕ G∗1 is generated by the elements
r
s
r
X
∂uk ∗ X ∂vl ∗ X ∂uk ∗
(4)
fk +
gl =
fk
∂x
∂x
∂x
i
i
i
k=1
l=1
k=1
for i = 1, . . . , n, and
(5)

r
X
∂uk
k=1

∂yj

fk∗

s
s
X
∂vl ∗ X ∂vl ∗
+
g =
g
∂yj l
∂yj l
l=1
l=1

for j = 1, . . . , m.
Here we use that ∂vl /∂xi = 0 for l = 1, . . . , s and ∂uk /∂yj = 0 for k = 1, . . . , r.
Since T 1 (∆1 ∗ ∆2 ) ∼
= I ∗ / Im δ ∗ , (3), (4) and (5) imply that T 1 (∆1 ∗ ∆2 ) =
T 1 (S/I1 ) ⊕ T 1 (S/I2 ). This yields the desired isomorphism because
S/I1 ∼
= (K[x1 , . . . , xn ]/I∆ )[y1 , . . . , ym ] and S/I2 ∼
= (K[y1 , . . . , ym ]/I∆ )[x1 , . . . , xn ].
1

2


Corollary 2.4. For all a − b ∈ Zn+m , we have
T 1 (∆1 ∗ ∆2 )a−b ∼
= (T 1 (∆1 )[y1 , . . . , ym ])a−b ⊕ (T 1 (∆2 )[x1 , . . . , xn ])a−b .
Proof. The assertion follows immediately from Proposition 2.3. However we give an
alternative and more direct proof for this isomorphism:
(i) Observing that links commute with joins, it is enough to prove that
T 1 (∆1 ∗ ∆2 )−(b1 +b2 ) = (T 1 (∆1 )[y1 , . . . , ym])−(b1 +b2 ) ⊕ (T 1 (∆2 )[x1 , . . . , xn ])−(b1 +b2 ) ,
where Bi := supp bi ⊆ V (∆i ) for i = 1, 2.
(ii) First we show that
NB1 ∪B2 (∆1 ∗ ∆2 ) = [NB1 (∆1 ) ∗ (∆2 \ B2 )] ∪ [(∆1 \ B1 ) ∗ NB2 (∆2 )],
where ∆i \ Bi = {F ∈ ∆i : F ∩ Bi = ∅} for i = 1, 2.
Let F1 ∪ F2 ∈ NB1 ∪B2 (∆1 ∗ ∆2 ) with Fi ∈ ∆i for i = 1, 2. Then Fi ∈ ∆i \ Bi for
i = 1, 2 and (F1 ∪ F2 ) ∪ (B1 ∪ B2 ) ∈
/ ∆1 ∗ ∆2 by definition. It follows that for at
least one i ∈ {1, 2}, Fi ∪ Bi ∈
/ ∆i , namely, Fi ∈ NBi (∆i ). This actually proves the
containment ⊆. The other containment can be proved similarly.
(iii) Suppose that Bi 6= ∅ for i = 1, 2. We will show that both sides of the identity
in step (i) vanishes.
Let F1 ∪ F2 ∈ NB1 ∪B2 (∆1 ∗ ∆2 ) with Fi ∈ ∆i for i = 1, 2. Then Fi ∈ NBi (∆i ),
for at least one i ∈ {1, 2} by the proof of (ii), say i = 1. It follows that (F1 ∪ F2 ) ∪
eB ∪B (∆1 ∗ ∆2 ). Hence
B1 ∈
/ ∆1 ∗ ∆2 . Since B1 ( B1 ∪ B2 , we have F1 ∪ F2 ∈ N
1
2
eB1 ∪B2 (∆1 ∗ ∆2 ). This implies that the left side of the identity
NB1 ∪B2 (∆1 ∗ ∆2 ) = N
in step (i) vanishes.
To see that the right side also vanishes, we note that a multi-homogeneous eleam
ment in T 1 (∆1 )[y1 , . . . , ym ] has the form ty1a1 · · · ym
, where t is a multi-homogeneous
12

am
has the multielement in T 1 (∆1 ) and ai ≥ 0 for i = 1, . . . , m. But y1a1 · · · ym
homogeneous degree for which each coordinate is greater or equal than zero. Hence
(T 1 (∆1 )[y1 , . . . , ym ])−(b1 +b2 ) = 0. Similarly (T 1 (∆2 )[x1 , . . . , xn ])−(b1 +b2 ) = 0.

(iv) If one of the Bi is the empty set, say B2 = ∅, then (ii) implies that
eB1 (∆1 ∗ ∆2 ) = N
eB1 (∆1 ) ∗ ∆2 .
NB1 (∆1 ∗ ∆2 ) = NB1 (∆1 ) ∗ ∆2 and N

This yields T 1 (∆1 ∗ ∆2 )−b1 = T 1 (∆1 )−b1 = (T 1 (∆1 )[y1 , . . . , ym ])−b1 , as desired.

Disjoint unions. Next we consider the simplicial complex ∆1 ∪ ∆2 which is the
disjoint union of ∆1 and ∆2 . The vertex set of ∆1 ∪ ∆2 is V (∆1 ) ∪ V (∆2 ) and
F ∈ ∆1 ∪ ∆2 if and only if F ∈ ∆1 or F ∈ ∆2 .
Theorem 2.5. Let ∆1 6= {∅} and ∆2 6= {∅} be simplicial complexes with disjoint
vertex sets. Assume that for i = 1, 2, V (∆i ) = [∆i ], that is, {j} ∈ ∆i for all
j ∈ V (∆i ).
(a) The following conditions are equivalent:
(1) ∆1 ∪ ∆2 is inseparable;
(2) ∆1 and ∆2 are simplices.
(b) The following conditions are equivalent:
(1) ∆1 ∪ ∆2 is rigid;
(2) ∆1 ∪ ∆2 is ∅-rigid;
(3) ∆1 and ∆2 are simplices with dim ∆1 + dim ∆2 > 0.
Proof. Let ∆ = ∆1 ∪ ∆2 .
(a) (1) ⇒ (2): Since ∆ is inseparable, Theorem 1.8 implies that the graph G{i} (∆)
is connected for all i ∈ V (∆1 ) ∪ V (∆2 ). Let i ∈ V (∆1 ). By assumption we have
{i} ∈ ∆. It follows that N{i} (∆) = N{i} (∆1 ) ∪ ∆2 \ {∅}. Since N{i} (∆1 ) and ∆2 \ {∅}
belong to different connected components of G{i} (∆) and since G{i} (∆) is connected,
it follows that either N{i} (∆1 ) = ∅ or ∆2 \ {∅} = ∅. The second case is ruled out
by assumption. Hence, N{i} (∆1 ) = ∅. This implies that i ∈ F for all F ∈ F (∆1 ).
Since i is an arbitrary element in V (∆1 ) we see that F (∆1 ) = {V (∆1 )}. Starting
with i ∈ V (∆2 ), the same argument proves that ∆2 is also a simplex.
(2) ⇒ (1): By Theorem 1.8, it is enough to show that G{i} (∆) is connected for
all i ∈ V (∆1 ) ∪ V (∆2 ). Let i ∈ V (∆1 ). As mentioned above we have N{i} (∆) =
N{i} (∆1 )∪∆2 \{∅}. Since ∆1 is a simplex and {i} ∈ ∆1 it follows that N{i} (∆1 ) = ∅.
Thus N{i} (∆) = ∆2 \ {∅}. Therefore G{i} (∆) is connected because ∆2 is a simplex.
A similar argument shows that G{i} (∆) is also connected for all i ∈ V (∆2 ).
(b) (1) ⇒ (2) is obvious.
(2) ⇒ (3): Since ∆ is ∅-rigid we have T 1 (∆)−b = 0 for all b ∈ {0, 1}V (∆1 )∪V (∆2 ) .
In particular, T 1 (∆)−ei = 0 for all i ∈ V (∆1 ) ∪ V (∆2 ). So by Theorem 1.8, ∆ is
inseparable. Thus using part (a) we have that ∆1 and ∆2 are simplices. Suppose
that dim ∆1 + dim ∆2 = 0. Then dim ∆1 = dim ∆2 = 0, and hence I∆ is of the form
(xy). It follows that T 1 (∆)−(1,1) 6= 0, a contradiction.
13

(3) ⇒ (1): The assumptions imply that I∆ is of the form (xi yj : i = 1, . . . , n, j =
1, . . . , m) with n ≥ 2 or m ≥ 2. Corollary 2.11 implies that ∆ is rigid.

Corollary 2.6. Let ∆ be simplicial complex. Then ∆ is separable if ∆ has more
than two connected components.
Circs. For i = 1, 2, let ∆i be a simplicial complex on the vertex set Vi and assume
that V1 ∩ V2 = ∅. Then the circ of ∆1 and ∆2 is the simplicial complex ∆1 ◦ ∆2 with
vertex set V1 ∪ V2 whose faces are those subsets F of V1 ∪ V2 for which either F ∩ V1
is a face of ∆1 or F ∩ V2 is a face of ∆2 .
It is worthwhile to note that if I∆1 ⊆ S1 = K[x1 , . . . , xn ] and I∆2 ⊆ S2 =
K[y1 , . . . , ym ] then I∆1 ◦∆2 = I∆1 I∆2 S, where S = K[x1 , . . . , xn , y1 . . . , ym ].
In the following we set MB (∆) = {F ⊆ V (∆) : F ∈
/ ∆ and F ∩ B = ∅} for any
B ⊆ V (∆). For later use we list a few obvious facts in the next lemmata.
Lemma 2.7. Let B = B1 ∪ B2 with ∅ =
6 Bi ⊆ Vi for i = 1, 2. Then
(a) NB (∆1 ◦ ∆2 ) = NB1 (∆1 ) ∗ NB2 (∆2 ) ∪ NB1 (∆1 ) ∗ MB2 (∆2 )
∪ MB1 (∆1 ) ∗ NB2 (∆2 ).
(b) NB1 (∆1 ◦ ∆2 ) = NB1 (∆1 ) ∗ M∅ (∆2 ) and NB2 (∆1 ◦ ∆2 ) = M∅ (∆1 ) ∗ NB2 (∆2 ).
Lemma 2.8. Let B = B1 ∪ B2 with ∅ =
6 Bi ⊆ Vi for i = 1, 2. Then
eB (∆1 ◦ ∆2 ) = NB1 (∆1 ) ∗ N
eB2 (∆2 ) ∪ N
eB1 (∆1 ) ∗ NB2 (∆2 )
(a) N
∪ NB1 (∆1 ) ∗ MB2 (∆2 ) ∪ MB1 (∆1 ) ∗ NB2 (∆2 ).

eB1 (∆1 ◦ ∆2 ) = N
eB1 (∆1 ) ∗ M∅ (∆2 ) and N
eB2 (∆1 ◦ ∆2 ) = M∅ (∆1 ) ∗ N
eB2 (∆2 ).
(b) N

We use these lemmata to prove

Proposition 2.9. Let ∆1 and ∆2 be two simplicial complexes on the vertex sets V1
and V2 , respectively, and let bi ∈ {0, 1}Vi , Bi = supp bi for i = 1, 2. Assume that
I∆i 6= 0 for i = 1, 2.
(a) Suppose that b1 , b2 6= 0. Then

eB ∪B (∆1 ◦ ∆2 ) = ∅ and NB ∪B (∆1 ◦ ∆2 ) 6= ∅,
K, if N
1
∼
1
2
1
2
T (∆1 ◦ ∆2 )−(b1 +b2 ) =
0, otherwise.
(b) dimK T 1 (∆1 ◦ ∆2 )−bi = dimK T 1 (∆i )−bi for i = 1, 2.

Proof. First we observe that for each i = 1, 2, I∆i 6= 0 if and only if Vi ∈
/ ∆i , which
is equivalent to Mφ (∆i ) 6= ∅.
eB1 ∪B2 (∆1 ◦∆2 ) = ∅ and NB1 ∪B2 (∆1 ◦∆2 ) 6= ∅. Lemma 2.7(a) to(a) Assume that N
gether with Lemma 2.8(a) imply that NB1 (∆1 ) ∗ NB2 (∆2 ) 6= ∅. Therefore NBi (∆i ) 6=
eB1 ∪B2 (∆1 ◦ ∆2 ) = ∅ it follows from Lemma 2.8(a) that
∅ for i = 1, 2. Since N
eB (∆i ) = ∅ for
eB1 (∆1 ) ∗ NB2 (∆2 ) = ∅, and so N
eB2 (∆2 ) = ∅ and N
NB1 (∆1 ) ∗ N
i
i = 1, 2. The same argument shows that MBi (∆i ) = ∅ for i = 1, 2.
14

Since MBi (∆i ) = ∅ for i = 1, 2, we have Vi \Bi ∈ ∆i and hence Vi \Bi ∈ NBi (∆i ) for
i = 1, 2. It follows that any λ ∈ T 1 (∆1 ◦ ∆2 )−(b1 +b2 ) is constant on NB1 ∪B2 (∆1 ◦ ∆2 ),
because for any F1 ∪ F2 ∈ NB1 ∪B2 (∆1 ◦ ∆2 ) with Fi ⊆ Vi for i = 1, 2 we have
F1 ∪ F2 ⊆ (V1 \ B1 ) ∪ (V2 \ B2 ). Hence T 1 (∆1 ◦ ∆2 )−(b1 +b2 ) ∼
= K.
1
If NB1 ∪B2 (∆1 ◦ ∆2 ) = ∅, then T (∆1 ◦ ∆2 )−(b1 +b2 ) = 0. Assume now that
e
NB1 ∪B2 (∆1 ◦ ∆2 ) 6= ∅. Let λ ∈ Λ1 (∆1 ◦ ∆2 )−(b1 +b2 ) (see its definition in CoroleB1 ∪B2 (∆1 ◦ ∆2 ) with Fi ⊆ Vi , i = 1, 2. It
lary 1.4) and F1 ∪ F2 ∈ NB1 ∪B2 (∆1 ◦ ∆2 ) \ N
eB (∆i ) for i = 1, 2. By
follows from Lemmata 2.7(a) and 2.8(a) that Fi ∈ NBi (∆i )\ N
i
eB (∆i ), i = 1, 2 and MB (∆i ), i = 1, 2 is nonempty.
Lemma 2.8(a), at least one of N
i
i
First suppose that MB1 (∆1 ) 6= ∅. Then we take G1 ∈ MB1 (∆1 ). Note that
eB1 ∪B2 (∆1 ◦ ∆2 ) and (G1 ∪ F2 ) ∪ (F1 ∪ F2 ) ∈ ∆1 ◦ ∆2 . Therefore
G1 ∪ F2 ∈ N
λ(F1 ∪ F2 ) = 0. Similarly, we can conclude that λ(F1 ∪ F2 ) = 0 if MB2 (∆2 ) 6= ∅ or
eB (∆i ) 6= ∅ for i = 1 or i = 2. So we have proved that λ = 0 in any case. Thus
N
i
T 1 (∆1 ◦ ∆2 )−(b1 +b2 ) = 0.
(b) We prove the statement for i = 1. The same argument holds for i = 2.
Since M∅ (∆2 ) 6= ∅, we have NB1 ∪B2 (∆1 ◦ ∆2 ) = ∅ if and only if NB1 (∆1 ) = ∅ by
Lemma 2.7(b). Hence we only need to consider the case when NB1 ∪B2 (∆1 ◦ ∆2 ) 6= ∅.
We define a homomorphism ϕ from Λ1 (∆1 )−b1 to Λ1 (∆1 ◦ ∆2 )−b1 as follows:
for λ1 ∈ Λ1 (∆1 )−b1 , ϕ(λ1 ) is given by ϕ(λ1 )(F1 ∪ G1 ) = λ1 (F1 ) for any F1 ∈
NB1 (∆1 ) and G1 ∈ M∅ (∆2 ). One can check that ϕ(λ1 ) belongs to Λ1 (∆1 ◦ ∆2 )−b1
and that ϕ is injective. To see that ϕ is surjective, one only need to notice that
for any λ ∈ Λ1 (∆1 ◦ ∆2 )−b1 , λ(F1 ∪ G1 ) = λ(F1 ∪ G2 ) for any F1 ∈ NB1 (∆1 ) and
G1 , G2 ∈ M∅ (∆2 ). Hence ϕ is an isomorphism of K-vector spaces. This implies that
dimK T 1 (∆1 ◦ ∆2 )−b1 = dimK T 1 (∆1 )−b1 , using Corollary 1.4.

For simplicity we say that a simplicial complex ∆ on the vertex set [n] is special
if either ∆ has a unique facet, which is a maximal proper subset of [n], or ∆ has
exactly two facets, one of which contains a unique element say i and the other one
of which is [n] \ {i}. We see that ∆ is special if and only if I∆ is of the form zP ,
where z is a variable in S with z 6∈ P , and P is either a monomial prime ideal of S
or P = S.
Theorem 2.10. (a) Suppose that ∆1 ◦ ∆2 is rigid, and that I∆i 6= 0 for i = 1, 2.
Then ∆1 and ∆2 are rigid.
(b) Conversely, suppose that ∆1 and ∆2 are rigid simplicial complexes with disjoint vertex sets V1 and V2 , respectively. Then ∆1 ◦ ∆2 is rigid if and only if for
either j = 1 or j = 2, link∆j F is not special for all F ∈ ∆j . In algebraic terms, for
j = 1 or j = 2, none of the monomial localizations of I∆j is of the form zP , where
z is a variable in Sj with z 6∈ P , and P ⊆ Sj is either a monomial prime ideal or
P = Sj .
Proof. Let S1 = K[x1 , . . . , xn ], S2 = K[y1 , . . . , ym ] and S = K[x1 , . . . , xn , y1 , . . . , yn ].
We may assume that I∆1 ⊆ S1 and I∆2 ⊆ S2 .
(a) Let P1 = (x1 , . . . , xn ) and P2 = (y1 , . . . , ym ). Since
I∆1 ◦∆2 (Pi ) = (I∆1 I∆2 S)(Pi ) = I∆i
15

for i = 1, 2, we see that
T 1 (K[∆1 ◦ ∆2 ](Pi )) ∼
= T 1 (K[∆i ]).
Thus the assertion follows from Lemma 2.1(b).
(b) First suppose that ∆1 ◦ ∆2 is rigid, and suppose that there exist F1 ∈ ∆1 and
F2 ∈ ∆2 such that the Stanley–Reisner ideal Ilink∆j Fj is of the form zj Pj where zj is
a variable in Sj with zj 6∈ Pj , Pj ⊆ Sj is either a monomial prime ideal or Pj = Sj .
Since link∆1 ◦∆2 F1 ∪ F2 = link∆1 F1 ◦ link∆2 F2 , it follows that
(Ilink∆1 ◦∆2 F1 ∪F2 )S = Ilink∆1 F1 Ilink∆2 F2 S = (z1 z2 )P1 P2 S
is not rigid because the ideal (z1 z2 ) is not rigid, a contradiction (see Proposition 1.2(b) or Lemma 2.1(c)).
Suppose that ∆1 ◦ ∆2 is not rigid. Then there exist a, b ∈ {0, 1}V1 ∪V2 with
supp a ∩ supp b = ∅ such that T 1 (∆1 ◦ ∆2 )a−b 6= 0. Let a = a1 + a2 and b = b1 + b2
with a1 , b1 ∈ {0, 1}V1 and a2 , b2 ∈ {0, 1}V2 . We set B = supp b, Bi = supp bi for
i = 1, 2, and denote by Γi the simplicial complex link∆i (supp ai ) for i = 1, 2. Since
link∆1 ◦∆2 (supp a) = Γ1 ◦ Γ2 , we have T 1 (Γ1 ◦ Γ2 )−b 6= 0 by using Proposition 1.2(b).
Note that Γi is rigid for i = 1, 2 by Lemma 2.1(c).
Since T 1 (Γ1 ◦ Γ2 )−b 6= 0 we have (IΓ1 IΓ2 ) = IΓ1 ◦Γ2 6= 0. This implies that IΓi 6= 0
for i = 1, 2. Suppose b1 = 0. Since T 1 (Γ1 ◦ Γ2 )−b2 = T 1 (Γ2 )−b2 (see Proposition 2.9(b)), we have T 1 (Γ1 ◦ Γ2 )−b2 = 0, because Γ2 is rigid. This is a contradiction. Therefore b1 6= 0, and similarly b2 6= 0. Now Proposition 2.9(a) implies
eB ∪B (Γ1 ◦ Γ2 ) = ∅. By a similar argument used
that NB1 ∪B2 (Γ1 ◦ Γ2 ) 6= ∅ and N
1
2
eB (Γi ) = ∅ for i = 1, 2.
in Proposition 2.9, we have NBi (Γi ) 6= ∅ and MBi (Γi ) = N
i
Therefore, for i = 1, 2 the map λi : NBi (Γi ) → K, which maps each element of
NBi (Γi ) to 1, defines a nonzero element in Λ(Γi )−bi . Since Γi is rigid it follows from
Corollary 1.4(a) that |Bi | = 1 for i = 1, 2. Without loss of generality we may assume
that B1 = {x1 } and B2 = {y1 }. Then V (Γ1 ) \ {x1 } ∈ Γ1 and V (Γ2 ) \ {y1} ∈ Γ2 since
MBi (Γi ) = ∅ for i = 1, 2. Now we consider the following cases:
Case 1: |V (Γ1 )| = 1. Since IΓ1 is not zero we have IΓ1 = (x1 ) and so Γ1 is special.
Case 2: |V (Γ1 )| = 2. Assume V (Γ1 ) = {x1 , x2 }. Then {x2 } ∈ Γ1 . Since IΓ1 6= 0,
we have {x1 , x2 } ∈
/ Γ1 and since IΓ1 is rigid we have Γ1 6= h{x1 }, {x2 }i. Hence
Γ1 = h{x2 }i and IΓ1 = (x1 ). This implies that Γ1 is special again.
Case 3: |V (Γ1 )| ≥ 3. Since V (Γ1 ) \ {x1 } ∈ Γ1 , we have either Γ1 = hV (Γ1 ) \ {x1 }i
or Γ1 = hV (Γ1 ) \ {x1 }, F1 , . . . , Fk i, where k ≥ 1 and x1 ∈ Fj for j = 1, . . . , k. In the
first case we have IΓ1 = (x1 ) and we are done. In the second one, we set G = F1 \{x1 }.
Then linkΓ1 G = hV (Γ1 ) \ F1 , {x1 }i and V (linkΓ1 G) = (V (Γ1 ) \ F1 ) ∪ {x1 }. Write
V (Γ1 ) \ F1 = {x2 , . . . , xs }. Since linkΓ1 G is rigid, we have s ≥ 3 and so IlinkΓ1 G =
(x1 )(x2 , . . . , xs ) = x1 P . This also implies that Γ1 is special.
The similar argument is applied to Γ2 .

Corollary 2.11. (a) Let I be a squarefree monomial ideal and let P be a nonprincipal monomial prime ideal in a disjoint set of variables. Then IP is rigid if
and only if I is rigid.
16

(b) Let P1 , . . . Q
, Pt be monomial prime ideals generated by pairwise disjoint sets of
variables. Then ti=1 Pi is rigid if and only if at most one Pi is a principal ideal.

Proof. (a) Let ∆1 and ∆2 be two simplicial complexes with I∆1 = I and I∆2 = P .
Suppose IP is rigid. It follows from Theorem 2.10(a) that I is rigid. Conversely,
suppose that I is rigid. Note that the links of ∆2 correspond to monomial localizations of P by Lemma 2.1(c). Since monomial localization of P with respect to
any monomial prime ideal is never of the form (z) or zQ with Q a monomial prime
ideal, Theorem 2.10(b) yields the desired conclusion.
(b) follows immediately from (a).

Letterplace ideals. We conclude this section with applications to letterplace ideals.
In [4], letterplace and co-letterplace ideals are introduced and it is shown that these
are all inseparable monomial ideals. In this section we consider rigidity of this class
of ideals.
More generally, let P and Q be two partially ordered sets. A map ϕ : P → Q is
called isotone or order preserving, if p ≤ p′ implies ϕ(p) ≤ ϕ(p′ ). The set of isotone
maps is denoted by Hom(P, Q). Note that Hom(P, Q) is again a partially ordered
set with φ ≤ ψ if φ(p) ≤ ψ(p) for all p ∈ P.
We fix a field K and consider the polynomial ring S over K in the variables
xp,q with p ∈ P and q ∈ Q. Attached to P and Q we define the monomial ideal
L(P, Q) ⊆ S generated by the monomials
Y
uϕ =
xp,ϕ(p) , ϕ ∈ Hom(P, Q).
p∈P

Theorem 2.12. Let P and Q be finite posets. The following conditions are equivalent:
(a) L(P, Q) is rigid.
(b) No two distinct elements of P are comparable.
Proof. (a) ⇒ (b): Assume there exist a, b ∈ P with a < b. We consider the
monomial prime ideal P = (xp,q : p ∈ {a, b}, q ∈ Q), and claim that L(P, Q)(P ) =
L({a, b}, Q), where {a, b} is the poset with a < b. In fact, for any minimal generator
u ∈ L(P, Q)(P ), there exists ϕ ∈ Hom(P, Q) such that u is obtained from uϕ by
setting xp,ϕ(p) = 1 if p ∈
/ {a, b}, that is, u = xa,ϕ(a) xb,ϕ(b) . This proves L(P, Q)(P ) ⊆
L({a, b}, Q).
Conversely, let u = xa,c xb,d ∈ L({a, b}, Q), where c, d ∈ Q and c ≤ d. Let n = |P|.
Since any finite partial order can be extended to a total order, there exists an isotone
bijective map from P to [n], which we denote by f . We now define a map ϕ : P → Q
as follows:

c, if f (p) < f (b),
ϕ(p) =
d, otherwise.
Then ϕ ∈ Hom(P, Q) and ϕ(a) = c, ϕ(b) = d, and hence u ∈ L(P, Q)(P ). Thus our
claim follows.
It follows from Corollary 3.6 and its proof that S(P )/L({a, b}, Q) is not rigid.
Therefore, Lemma 2.1(b) implies that S/L(P, Q) is not rigid.
17

(b) ⇒ (a): Let P = {p1 , . . . , pm } with pi and pj incomparable for all i 6= j and
let Q = {q1 , . . . , qn }. Then
m
Y
L(P, Q) =
(xpi ,q1 , xpi ,q2 , . . . , xpi ,qn ).
i=1

Thus the assertion follows from Corollary 2.11(b).



For an integer n ∈ N we denote by [n] the totally ordered set {1 < 2 < · · · < n}.
The ideal L([n], P) is called the nth letterplace ideal, while L(P, [n]) is called the nth
co-letterplace ideal. They are Alexander dual to each other if we identify xi,p with
xp,i for any i ∈ [n] and p ∈ P. In particular, the facets of the simplicial complex
associated with L([n], P) are in bijection with the generators of L(P, [n]), and vice
versa.
Corollary 2.13. Let P a finite poset.
(a) L([n], P) is rigid if and only if n = 1.
(b) L(P, [n]) is rigid if and only if no two distinct elements of P are comparable.
3. Rigidity of graphs
In this section we apply the results of Section 1 to study the rigidity of edge ideals
of a graph.
Inseparable graphs. Let G be a finite simple graph with vertex set [n]. The edge
set of G will be denoted by E(G). Let K be a field and S = K[x1 , . . . , xn ] the
polynomial ring over K in n indeterminates x1 , . . . , xn . The edge ideal I(G) ⊆ S of
G is defined to be the ideal generated by all products xi xj with {i, j} ∈ E(G). Let
∆(G) be the simplicial complex with I(G) = I∆(G) Then
∆(G) = {F ⊆ [n] : F does not contain any edges of G},
The simplicial complex ∆(G) is called the independence complex of G. The faces of
∆(G) are called the independent sets of G.
We call G inseparable if I(G) is inseparable. Let i ∈ [n]. Then N(i) = {j : {j, i} ∈
E(G)} is called the neighborhood of i. We denote by G(i) the complementary graph
of the restriction GN (i) of G to N(i). In other words, V (G(i) ) = N(i) and E(G(i) ) =
{{j, k} : j 6= k, j, k ∈ N(i) and {j, k} 6∈ E(G)}. Note that G(i) is disconnected if
and only if N(i) = A ∪ B, where A, B 6= ∅, A ∩ B = ∅ and all vertices of A are
adjacent to those of B.
Theorem 3.1. The following conditions are equivalent:
(a) The graph G is inseparable;
(b) G(i) is connected for all i;
(c) T 1 (S/I(G))−ei = 0 for all i.
18

Proof. We set ∆ = ∆(G). By Theorem 1.8, it suffices to prove that G{i} (∆) is
connected if and only if G(i) is connected for each i. First we note that V (G(i) ) ⊆ [n]
and
V (G{i} (∆)) = {F ⊆ [n] : F is an independent set of G and F ∩ V (G(i) ) 6= ∅}.
Assume G(i) is connected. Given F1 , F2 ∈ V (G{i} (∆)), there exist k1 , k2 ∈ V (G(i) )
with ki ∈ Fi for i = 1, 2. Suppose that k1 = k2 . Then F1 , {k1}, F2 is a path in
G{i} (∆), and thus F1 is connected to F2 . Next suppose that k1 6= k2 . Since G(i)
is connected, there is a path k1 = j0 , j1 , . . . , js = k2 in G(i) . Note that {jℓ , jℓ+1 } ∈
V (G{i} (∆)) for all ℓ = 0, . . . , s − 1. Therefore,
F1 , {k1}, {j0 , j1 }, {j1 }, {j1 , j2 }, {j2 }, . . . , {js−1 , js }, {k2}, F2
is a path in G{i} (∆), and so F1 is connected to F2 . It follows that G{i} (∆) is
connected.
Conversely, assume that G{i} (∆) is connected. Given k1 , k2 ∈ V (G(i) ), there is a
path {k1 }, F1 , F2 , . . . , F2t−1 , {k2 } in G{i} (∆). Hence
{k1 } ⊆ F1 ⊇ F2 ⊆ F3 ⊇ . . . ⊆ F2t−1 ⊇ {k2 }.
We use the induction on t to show that there is a path from k1 to k2 in G(i) . If
t = 1 then {k1 , k2 } ⊆ F1 and so k1 is adjacent to k2 (in G(i) ). For t > 1, let
k0 ∈ F2 ∩ V (G(i) ). Then k1 is adjacent to k0 , and by induction hypothesis there is a
path in G(i) from k0 to k2 . Hence there is a path in G(i) from k1 to k2 and it follows
that G(i) is connected.

Considering the proof of Theorem 3.1 one even shows that the graphs G{i} (∆)
and G(i) have the same number of connected components.
Corollary 3.2. If G contains no triangle, then G is inseparable.
The conditions (α) and (β). Let G be a finite graph on the vertex set [n] and
∆(G) be the independence complex of G. Let A be a subset of [n]. Then link A of
∆(G) can be interpreted as the independence complex of a suitable graph if A is an
independent subset of G. In order to show this we introduce some notation.
The set
[
N(A) =
N(i)
i∈A

is called the neighborhood of A (in G), and the set
N[A] = A ∪ N(A)
is called the closed neighborhood of A (in G).
Let B ⊂ [n]. The induced subgraph of G with vertex set B, is the graph GB with
edges {i, j} ∈ E(G) and such that i, j ∈ B. An induced cycle of G is a cycle of G
which is of the form GB . By G \ A we denote the induced subgraph of G on the
vertex set [n] \ A.
Lemma 3.3. Let A ⊆ [n] be an independent subset of G. Then link∆(G) A is the
independence complex of the graph G \ N[A].
19

Proof. Note that F ∈ link∆(G) A if and only if F ⊆ [n] \ A and F ∪ A ∈ ∆(G). The
last condition is equivalent to saying that F ∪ A does not contain any edge of G.
Thus F ∈ link∆(G) A if and only if F ⊆ [n] \ N[A] and F does not contain any edge
of G. Since the set of edges of G in [n] \ N(A) is the same as the set of edges of G
in G \ N(A), the desired conclusion follows.

For a given subset B ⊆ [n], we may easily express the sets
eB (∆(G)) ⊆ NB (∆(G)) ⊆ [n]
N

in terms of G:

NB (∆(G)) = {F ⊆ [n] : F ∩ B = ∅, F contains no edges of G, but F ∪ B does},
eB (∆(G)) =
and N
{F ∈ NB (∆(G)) : there exists B ′ ( B such that F ∪ B ′ contains an edge of G}.
The following lemma lists some obvious properties of these sets.
Lemma 3.4. Let B ⊆ [n]. Then the following statements hold:
eB (∆(G)).
(a) If |B| ≥ 3 or |B| = 2 and B is not an edge of G, then NB (∆(G)) = N
eB (∆(G)) = ∅ if and only B is an
(b) If B is an edge, then ∅ ∈ NB (∆(G)), and N
isolated edge of G, i.e. it does not have a common vertex with any other edge of G.
Combining this lemma with Corollary 1.4 we obtain

Corollary 3.5. Let b ∈ {0, 1}n and let B = supp b. Suppose that |B| ≥ 2. Then
T 1 (∆(G))−b = 0 unless B is an isolated edge in G. On the other hand, if B is an
isolated edge in G, then T 1 (∆(G))−b is one-dimensional.
Let G be a graph on the vertex set [n]. Based on Theorem 3.1 and Corollary 3.5
we see that ∆(G) is ∅-rigid, (i.e., T 1 (∆(G))−b = 0 for every b ∈ {0, 1}n ) if and only
if G(i) is connected for all i ∈ [n] and G contains no isolated edge. Combining this
fact with Proposition 1.2 and Lemma 3.3 we obtain the following combinatorial conditions for a graph to be rigid: the graph G is rigid if and only if for all independent
sets A ⊆ V (G) one has:
(α) (G \ N[A])(i) is connected for all i ∈ [n] \ N[A];
(β) G \ N[A] contains no isolated edge.
It is obvious from Corollary 3.2 that any bipartite graph is inseparable and so
it satisfies the condition (α), since any induced graph of a bipartite graph is again
bipartite. But, by far, not all bipartite graphs are rigid. For example we have
Corollary 3.6. Let G be a Cohen–Macaulay bipartite graph (i.e., S/I(G) is Cohen–
Macaulay). Then G is not rigid.
Proof. By Proposition 2.3 we may assume that G is connected. By [8, Theorem
3.4] the graph G, after a suitable relabeling of its vertices, arises from a finite
poset P = {p1 , . . . , pn } as follows: V (G) = {p1 , . . . , pn , q1 , . . . , qn } and E(G) =
{{pi , qj } : pi ≤ pj }. We may assume that p1 is a minimal element in P . Let
A = {p2 , . . . , pn }. Then N[A] = {p2 , . . . , pn , q2 , . . . , qn }, and G \ N[A] = {p1 , q1 }. It
follows from (β) that G is not rigid.

20

Recall that a vertex v is called a free vertex if deg v = 1, and an edge e is called
a leaf if it has a free vertex. An edge e of G is called branch, if there exists a leaf e′
with e′ 6= e such that e ∩ e′ 6= ∅.
Let e = {i, j} ∈ E(G). We denote by N0 (e) the set (N(i) ∪ N(j)) \ {i, j}.
In the next proposition we present sufficient conditions for graph to satisfy (α) or
(β).
Proposition 3.7. Let G be a finite graph on the vertex set [n].
(a) Suppose that each vertex of a 3-cycle in G belongs to a leaf. Then G satisfies
(α), and hence G is inseparable. In particular, if G does not contain any
3-cycle, then G is inseparable.
(b) Suppose that each edge of G is a branch. Then G satisfies (β).
(c) Suppose that each edge of G is a branch and each vertex of a 3-cycle of G
belongs to a leaf. Then G is rigid.
Proof. (a) Suppose that (α) is not satisfied. Then there exists an independent set
A ⊆ [n] and i ∈ [n] \ N[A] such that N(i) ∩ [n] \ N[A] = B ∪ C with B, C 6= ∅ and
B ∩ C = ∅ and {j, k} ∈ E(G \ N[A]) ⊆ E(G) for all j ∈ B and all k ∈ C. Since
B, C 6= ∅ there exist j ∈ B and k ∈ C such that {j, k} ∈ E(G). Thus i is a vertex of
a 3-cycle in G. By assumption there exists a leaf {i, t} in G. Suppose that t ∈ N[A].
If t ∈ A then i ∈ N[A], a contradiction. Thus t ∈ N(A). Since deg t = 1 it follows
that i ∈ A, again a contradiction. Therefore we see that t ∈ [n] \ N[A]. This implies
that t ∈ B ∪ C. We may assume that t ∈ B. So {t, k} ∈ E(G), a contradiction since
N(t) = {i}.
It follows from Theorem 3.1 that G is inseparable if it satisfies (α). Suppose now
that G does not contain any 3-cycle. Then, by the first part of the statement, G
satisfies condition (α), and so it is inseparable.
(b) Suppose that G does not satisfy (β). Then there exists an independent set
A of the vertices of G such that G \ N[A] contains an isolated edge, say e = {i, j}.
We show that e is not a branch of G and so we get a contradiction. Let v ∈ N0 (e)
and let deg v = 1. Then we have either N(v) = {i} or N(v) = {j}. Without loss of
generality we may assume that N(v) = {i}. Since e is an isolated edge in G \ N[A]
we have v ∈ N[A]. Suppose that v ∈ A. Then {i} = N(v) ⊆ N(A), a contradiction.
Thus v ∈ N(A), and so there exists t ∈ A such that v ∈ N(t). Since N(v) = {i} it
follows that t = i. This implies that i ∈ A, which is again a contradiction. Hence
deg v ≥ 2, as desired.
(c) follows from (a) and (b).

Rigid graphs. The next two lemmata will help us to classify the rigid chordal graphs
and rigid graphs without induced cycles of length 4,5 or 6.
Recall that a graph G is chordal if any cycle of length ≥ 4 has chord. A chord of
a cycle C is an edge {i, j} of G with i, j ∈ V (C) which is not an edge of C
Lemma 3.8. Let G be a rigid graph on the vertex set [n], and let A be an independent
set of vertices of G. Then G \ N[A] is rigid.
21

Proof. Let B be an independent set of vertices of G \ N[A]. Then A ∪ B is an
independent set of vertices of G. Indeed, suppose that {i, j} ∈ E(G) for some i ∈ A
and some j ∈ B. Then j ∈ N(i) implies that j ∈ N(A) ⊆ N[A]. Since N[A] ∩B = ∅
it follows that j ∈
/ B which is a contradiction.
Clearly, N[A]∪N[B] = N[A∪B]. Thus, ([n]\N[A])\N[B] = [n]\N[A∪B]. Since
for any subset C of [n], G\C is an induced subgraph of G, we have (G\N[A])\N[B] =
G \ N[A ∪ B]. Since rigidity is characterized by (α) and (β), the statement follows.

Let G be a graph on the vertex set [n]. For each e = {i, j} ∈ E(G) we define the
set OG (e) as follows:
[
OG (e) = {v ′ : v ′ ∈
N(v), N(v ′ ) ∩ {i, j} = ∅}.
v∈N0 (e)

Lemma 3.9. Let G be a rigid graph on the vertex set [n] which does not contain
any induced 4-cycle, and let e = {i, j} be an edge of G which is not a branch. Then
OG (e) 6= ∅.
Proof. First we show that for all v ∈ N0 (e) we have N(v)\{i, j} =
6 ∅. Note that since
G is rigid the edge e is not isolated, and so N0 (e) 6= ∅. Suppose that there exists
v ∈ N0 (e) such that N(v) ⊆ {i, j}. Without loss of generality we may assume that
v ∈ N(i). Since e is not a branch we have deg v ≥ 2. It follows that N(v) = {i, j}.
Therefore G(v) consists of two isolated vertices i and j which contradicts the fact
that G is rigid.
Now suppose that OG (e) = ∅, i.e., for all v ∈ N0 (e) and for all v ′ ∈ N(v) we have
N(v ′ ) ∩ {i, j} =
6 ∅. Since N0 (e) 6= ∅ we may assume that there exists v ∈ N(i) with
v 6= j. As shown above N(v) \ {i, j} =
6 ∅. Suppose that for all v ′ ∈ N(v) \ {i, j}
we have i ∈ N(v ′ ). Then i is an isolated vertex in G(v) , a contradiction. Thus
there exists v ′ ∈ N(v) \ {i, j} such that v ′ ∈
/ N(i). Hence v ′ ∈ N(j) which implies
that v ∈ N(j) because G does not contain any induced 4-cycle. Since v ′ ∈ N(j) and
v ′ 6= i, j we have v ′ ∈ N0 (e). So N(v ′′ )∩{i, j} =
6 ∅ for all v ′′ ∈ N(v ′ ). As shown above
′
N(v ) \ {i, j} =
6 ∅. Suppose that there exists v ′′ ∈ N(v ′ ) \ {i, j} such that v ′′ ∈
/ N(j).
Then v ′′ ∈ N(i). It follows that G contains the induced 4-cycle with vertices i, j, v ′
and v ′′ , a contradiction. Consequently, v ′′ ∈ N(j) for all v ′′ ∈ N(v ′ ) \ {i, j}. Then j
′
is an isolated vertex in G(v ) , a contradiction. This completes the proof.

Theorem 3.10. Let G be a graph on the vertex set [n] such that G does not contain
any induced cycle of length 4, 5 or 6. Then G is rigid if and only if each edge of G
is a branch and each vertex of a 3-cycle of G belongs to a leaf.
Proof. By using part (c) of Proposition 3.7 it is enough to show that if a rigid graph
G does not contain any induced cycle of length 4, 5 or 6, then each edge of G is a
branch and each vertex of a 3-cycle of G belongs to a leaf.
Suppose that e = {i, j} ∈ E(G) is not a branch. By Lemma 3.9, OG (e) 6= ∅.
We claim that there exists A ⊆ OG (e) such that A is independent in G and e is an
isolated edge in G \ N[A]. This will imply that G is not rigid, a contradiction. Let
G′ be the induced subgraph of G on the vertex set OG (e) and let C1 , . . . , Cm be the
22

connected components of G′ . Let u, v ∈ V (Ck ) such that {u, v} ∈ E(G). We show
that either N(u) ∩ N0 (e) ⊆ N(v) ∩ N0 (e) or N(v) ∩ N0 (e) ⊆ N(u) ∩ N0 (e).
Assume that N(u) ∩ N0 (e) 6⊆ N(v) ∩ N0 (e). Then there exists x ∈ N(u) ∩ N0 (e)
such that {v, x} is not an edge in G. Without loss of generality we may assume that
i ∈ N(x).
Let y ∈ N(v) ∩ N0 (e), and first suppose that y ∈ N(i). Then we have the 5-cycle
with vertices i, x, u, v and y. Since v, u ∈ OG (e) it follows that {u, i}, {v, i} ∈
/ E(G)
and since {v, x} ∈
/ E(G) it follows that {u, y} ∈ E(G) because G does not contain
any induced cycle of length 4 and 5. Therefore y ∈ N(u) ∩ N0 (e). On the other
hand if y ∈ N(j), then we have the 6-cycle with vertices i, x, u, v, y and j. Note
that {v, x}, {u, i}, {u, j}, {v, i}, {v, j} ∈
/ E(G). This implies that {v, y} ∈ E(G)
since G does not contain any induced cycle of length 4, 5 and 6. Thus either
N(u) ∩ N0 (e) ⊆ N(v) ∩ N0 (e) or N(v) ∩ N0 (e) ⊆ N(u) ∩ N0 (e), as desired.
Now given Ck we choose a maximal set Dk = {u1 , . . . , ul } ⊆ V (Ck ) with the
property that the sets N(ur ) ∩ N0 (e) are pairwise different. After having defined the
set Dk for each Ck we are ready to define the set A.
We let A be the unique subset of OG (e) such that A ∩ Ck consists of all elements
ur ∈ Dk with the property that N(ur ) ∩ N0 (e) 6⊆ N(us ) ∩ N0 (e) for all us ∈ Dk with
s 6= r.
In order to complete the proof we show that A is independent in G and e is an
isolated edge in G \ N[A]. Let u, v ∈ a and assume that {u, v} ∈ E(G). Then there
exists k such that u, v ∈ Dk ⊆ V (Ck ). Therefore either N(u)∩N0 (e) ⊆ N(v)∩N0 (e)
or N(v) ∩ N0 (e) ⊆ N(u) ∩ N0 (e). Thus by the choice of A, it follows that u = v, a
contradiction. So A is an independent set of G.
Finally we show that e is an isolated edge of G′′ := G \ N[A]. Note that for
any v ∈ N0 (e) ∩ V (G′′ ) and for any v ′ ∈ N(v) \ {i, j} we have N(v ′ ) ∩ {i, j} 6= ∅.
In fact, suppose that there exists v1 ∈ N(v) such that N(v1 ) ∩ {i, j} = ∅. So
v1 ∈ V (Ck ) for some k. If v1 ∈ A, then v ∈ N(A) ⊆ N[A], a contradiction. Hence
v1 ∈
/ A. Therefore, by the choice of A, there exists v2 ∈ A such that N(v1 ) ∩ N0 (e) ⊆
N(v2 )∩N0 (e). Since v ∈ N(v1 )∩N0 (e) we have v ∈ N(v2 ) and so v ∈ N(A) ⊆ N[A],
a contradiction. This shows that OG′′ (e) = ∅.
Suppose that e is not an isolated edge of G′′ , i.e., N0 (e) ∩ V (G′′ ) 6= ∅. We observe
that e is not a branch in G′′ . Indeed, if e is a branch, then since e is not isolated,
there exists v ∈ N0 (e) ∩ V (G′′ ) such that degree of v in G′′ is one. We may assume
that v ∈ N(i) \ N(j). Since e is not a branch in G we have N(v) \ {i, j} =
6 ∅ and
for any v ′ ∈ N(v) \ {i, j} we have v ′ ∈ N[A]. This implies that for any v ′ ∈ N(v),
v ′ ∈ N(A) because if v ′ ∈ a, then v ∈ N(A) ⊆ N[A] and hence v ∈
/ V (G′′ ), a
contradiction. As seen in the previous paragraph, for any v ′ ∈ N(v) \ {i, j} we have
N(v ′ ) ∩ {i, j} 6= ∅. If v ′ ∈
/ N(i), then v ′ ∈ N(j). Since v ∈
/ N(j) we will get the
induced 4-cycle with the vertices i, v, v ′ and j, a contradiction. So v ′ ∈ N(i) for
any v ′ ∈ N(v). It follows that i is an isolated vertex in G(v) , a contradiction. Thus
e is not a branch in G′′ .
Lemma 3.8 implies that G′′ is rigid and hence by Lemma 3.9 it follows that
OG′′ (e) 6= ∅, a contradiction. So indeed e is isolated in G′′ .
23

Now we prove that each vertex of a 3-cycle of G belongs to a leaf. Suppose that
there exists i ∈ [n], i belongs to a 3-cycle in G and it does not belong to a leaf. So for
all v ∈ N(i) we have deg v ≥ 2. Let j and k be the two other vertices of this 3-cycle.
If N(i) = {j, k}, then j and k are isolated vertices of G(i) , contradicting (α). So
N(i) \ {j, k} =
6 ∅. Since each edge of the graph G is a branch, for any v ∈ N(i) the
edge {i, v} is a branch. Since i does not belong to a leaf it follows that any v ∈ N(i)
belongs
S to a leaf. Thus for any v ∈ N(i) there exists iv ∈ N(v) with deg iv = 1. Set
a = v∈N (i)\{j,k} {iv }. Clearly, A is an independent set of the vertices of G and j, k
are two isolated vertices in (G \ N[A])(i) , a contradiction. Consequently, i belongs
to a leaf, as desired.

Corollary 3.11. Let G be a chordal graph. Then G is rigid if and only if each edge
of G is a branch and each vertex of a 3-cycle of G belongs to a leaf.
Corollary 3.12. Let G be a graph on the vertex set [n]. Suppose that all cycles of
G have length ≥ 7 (which for example is the case when G is a forest). Then G is
rigid if and only if each edge of G is a branch.
Proof. Since G does not contain any 3-cycle, the statement follows from Theorem 3.10.

As another application we have
Corollary 3.13. Let C be a cycle. Then C is rigid if and only if C is a 4-cycle or
a 6-cycle.
Proof. Suppose that |C| =
6 4, 5, 6. Then by Theorem 3.10, C is not rigid. Suppose
now that |C| = 5. Then C \ N[A] is an isolated edge, where A = {i} for some vertex
i of C, and hence the condition (β) is not satisfied. So C is not rigid also when
|C| = 5. In conclusion, C is not rigid if |C| ∈
/ {4, 6}.
Next suppose that |C| ∈ {4, 6}. Since C does not contain a 3-cycle, it follows
that C satisfies (α) by Proposition 3.7(a).
Note that for any nonempty independent subset A of V (C), C \ N[A] is either an
empty graph (i.e., a graph containing no edge) or a path of length 3. Therefore, the
cycle C also satisfies the condition (β). Hence C is rigid.

Acknowledgement: We would like to express our deep gratitude to the referee
for his/her careful reading and for his/her excellent advices, which improved the
presentation of this paper considerably.
References
[1] K. Altmann, J.A. Christophersen, Deforming Stanley-Reisner schemes, Math. Ann. 348(3)
(2010), 513–537.
[2] K. Altmann, J.A. Christophersen, Cotangent cohomology of Stanley-Reisner rings. Manuscripta
Math. 115(3) (2004), 361–378.
[3] V. Ene, J. Herzog, F. Mohammadi, Monomial ideals and toric rings of Hibi type arising from
a finite poset, European Journal of Combinatorics 32(3) (2011), 404–421.
[4] G. Fløystad, B.M. Greve, J. Herzog, Letterplace and co-letterplace ideals of posets,
http://arxiv.org/abs/1501.04523v1
24

[5] D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geomtry, Springer, 1994.
[6] J. Herzog, Deformation von Cohen-Macaulay Algebren, Journal fr die reine und angewandte
Mathematik 318 (1980), 83–105.
[7] J. Herzog, and T. Hibi, Monomial Ideals, Graduate Text in Mathematics, Springer, 2011.
[8] J. Herzog, T. Hibi, Distributive lattices, bipartite graphs and Alexander duality, J. Algebraic
Combin. 22(3) (2005), 289–302.
[9] S. Lichtenbaum, M. Schlessinger, The Cotangent Complex of a Morphism , Trans. Amer. Math.
Soc. 128(1) (1967), 41–70.
[10] J. Stevens, Deformations of singularities, Lecture Notes in Mathematics (1811), Berlin:
Springer, 2003.
Klaus Altmann, Institut für Mathematik, Freie Universität Berlin, Arnimallee
3, D-14195 Berlin, Germany
E-mail address: altmann@math.fu-berlin.de
Mina Bigdeli, Department of Mathematics, Institute for Advanced Studies in
Basic Sciences (IASBS), Gava zang, 45195-1159 Zanjan, 45137-66731 Iran
E-mail address: m.bigdelie@iasbs.ac.ir
Jürgen Herzog, Fakultät für Mathematik, Universität Duisburg-Essen, 45117
Essen, Germany
E-mail address: juergen.herzog@gmail.com
Dancheng Lu, Department of Mathematics, Soochow University, 215006 Suzhou,
P.R.China
E-mail address: ludancheng@suda.edu.cn

25

