# 13 a glimpse of combinatorial commutative rstan/algcomb/ ¢ ical algebra beyond the scope

Post on 27-Jun-2020

1 views

Embed Size (px)

TRANSCRIPT

13 A glimpse of combinatorial commutative

algebra.

13.1 Simplicial complexes

In this chapter we will discuss a profound connection between

commutative rings and some combinatorial properties of simpli- cial complexes. The deepest and most interesting results in this

area require a background in algebraic topology and homolog- ical algebra beyond the scope of this book. However, we will

be able to prove a highly nontrivial combinatorial result that relies on commutative algebra (i.e., the theory of commutative rings) in an essential way. This result is our Theorem 13.25, the

characterization of f -vectors of shellable simplicial complexes. Of course we must first define these terms and then set up the

necessary machinery.

Let V = {x1, . . . , xn} be a finite set, called a vertex set. An

abstract simplicial complex on V , or just simplicial complex for short, is a collection ∆ of subsets of V satisfying the following two conditions (of which the second is the significant one):

1. {xi} ∈ ∆ for 1 ≤ i ≤ n

2. If F ∈ ∆ and G ⊆ F , then G ∈ ∆.

An element F of ∆ is called a face. A maximal face F , i.e., a face that is not contained in any larger face, is called a facet.

The dimension of F is #F − 1. In particular, the empty set Ø is a face of dimension −1, unless ∆ = Ø (see the remark

1

below concerning empty simplicial complexes and empty faces). An i-dimensional face is called an i-face. Soon we will see the

geometric reason for our definition of dimension.

13.1 Remark. There is a small subtlety about the defini-

tion of simplicial complex that can lead to confusion. Namely, one must distinguish between the empty simplicial complex ∆ =

Ø which has no faces whatsoever, and the simplicial complex ∆ = {Ø} whose only face is the empty set Ø.

If Γ is any finite collection of finite sets, then 〈Γ〉 denotes the

smallest simplicial complex containing the elements of Γ. Thus

〈Γ〉 = {F : F ⊆ G for some G ∈ Γ}.

In presenting examples we will often abbreviate a set such as {1, 2, 3} as simply 123. Thus for instance 〈123, 14, 24〉 denotes

the simplicial complex with faces

Ø, 1, 2, 3, 4, 12, 13, 23, 14, 24, 123.

It is worthwhile to understand simplicial complexes geomet- rically, though such understanding is not really germane to our

main results here. Let us first review some basic definitions. A convex set in Rd is a subset S of Rd such that if u, v ∈ S,

then the line segment joining u and v is also in S. Equivalently, λu + (1 − λ)v ∈ S for all real numbers 0 ≤ λ ≤ 1. Clearly the

intersection of convex sets is convex. The convex hull of any subset S of Rd, denoted conv(S), is defined to be the intersec-

tion of all convex sets containing S. It is therefore the smallest convex set in Rd containing S.

2

A set {v0, v1, . . . , vj} ⊂ R d is affinely independent if the fol-

lowing condition holds: if α0, α1, . . . , αj are real numbers for which

∑ αivi = 0 and

∑ αi = 0, then α0 = α1 = · · · = αj = 0.

Equivalently, define an affine subspace of Rd to be the translate of a linear subspace, i.e., a set

A = {v ∈ Rd : v · y(1) = α1, . . . , y (k) = αk},

where y(1), . . . , y(k) ∈ Rd (with each y(i) 6= 0) and α1, . . . , αk ∈

R are fixed, and where v · y denotes the usual dot product in R

d (with respect to some basis). The dimension of A is the

dimension of the linear subspace {v ∈ Rd : v ·y = 0}. The affine span of a subset S of Rd, denoted aff(S), is the intersection of all affine subspaces containing S. It is easy to see that aff(S) is

itself an affine subspace. It is then true that a set of k+1 points of Rd is affinely independent if and only if its affine span has

dimension k, the maximum possible. In particular, the largest number of points of an affinely independent subset of Rd is d+1.

A simplex (plural simplices) σ in Rd is the convex hull of an affinely independent subset of Rd. The dimension of a simplex

σ is the dimension of its affine span. Equivalently, if σ is the convex hull of j+1 affinely independent points, then dimσ = j. If S is affinely independent and σ = conv(S), then a face of σ is a

set conv(T ) for some T ⊆ S. In particular, taking T = Ø shows thatØ is a face of σ. A face τ of dimension zero (i.e., τ is a single

point) is called a vertex of Γ. If dimσ = j, then σ has ( j+1 i+1

)

i-dimensional faces. For instance, a zero-dimensional simplex

is a point, a one-dimensional simplex is a line segment, a two- dimensional simplex is a triangle, a three-dimensional simplex is a tetrahedron, etc.

3

A (finite) geometric simplicial complex is a finite set Γ of simplices in Rd such that the following two conditions hold:

1. If σ ∈ Γ and τ is a face of σ, then τ ∈ Γ.

2. If σ, τ ∈ Γ, then σ ∩ τ is a common face (possibly empty)

of σ and τ .

We sometimes identify Γ with the union ⋃

σ∈Γ σ of its simplices.

In this situation Γ is just a subset of Rd, but it is understood that it has been described as a union of certain simplices.

There is an obvious abstract simplicial complex ∆ that we can associate with a geometric simplicial complex. Namely, the vertex set V of ∆ consists of the vertices of Γ, and a set F of

vertices of ∆ is a face of ∆ if F is the set of vertices of some simplex σ ∈ Γ. We then say that Γ (regarded as a union of its

simplices) is a geometric realization of ∆, denoted Γ = |∆|. Note that if F is a face of ∆ with k+1 vertices, then it corresponds to a

k-dimensional simplex in Γ, explaining why we defined dimF = #F − 1.

Note. In some situations it is useful for ∆ to have a unique (canonical) geometric realization. We can do this as follows. Suppose that ∆ has n vertices v1, . . . , vn. Let δi be the ith unit

coordinate vector in Rn. For each face F = {vi1, . . . , vik} ∈ ∆, define the simplex σF = conv(δi1, . . . , δik). The linear indepen-

dence of the δi’s guarantees that σF is indeed a simplex and that σF∩σG = σF∩G. Hence the set Γ = {σF : F ∈ ∆} is a geometric

realization of ∆, so we could define Γ as the geometric realiza- tion of ∆ (unique once we have labelled the vertices v1, . . . , vn).

4

However, for our purposes we don’t need this uniqueness.

13.2 Remark. (for those with some knowledge of topology)

The geometric realization |∆| is a topological space X (a topo- logical subspace of some Rd). We say that ∆ is a triangulation

of X.

13.3 Example. Let ∆ = 〈123, 234, 235, 36, 56, 57, 8〉. A

geometric realization of ∆ is shown in Figure 1, projected from three dimensions. Note that since three triangles share the edge 23, any geometric realization in Rd requires d ≥ 3. It is a result

of Karl Menger, though irrelevant for us, that any d-dimensional simplicial complex can be realized in R2d+1, and that this result

is best possible, i.e., the dimension 2d + 1 cannot in general be decreased. In fact, the simplicial complex whose facets are

all the (d+ 1)-element subsets of a (2d+ 3)-element set cannot be realized in R2d. For example, when d = 1 we get that the

complete graph K5 cannot be embedded in the plane (without crossing edges), a famous result in graph theory known to Euler at least implicitly, since he showed in 1750 that f1 ≤ 3f0− 6 for

any planar graph. The first person to realize explicitly that K5 is not planar seems to be A. F. Möbius in 1840, who stated the

result in the form of a puzzle.

13.4 Example. Let V = {1, 1̄, 2, 2̄, 3, 3̄} and

∆ = 〈123, 1̄23, 12̄3, 123̄, 1̄2̄3, 1̄23̄, 12̄3̄, 1̄2̄3̄〉.

Then the boundary of an octahedron is a geometric realiza-

tion of ∆. See Figure 2. Thus we can also say, following Remark 13.2, that ∆ is a triangulation of the 2-sphere (two-

dimensional sphere).

5

1 3 6

8

7 4

5 2

Figure 1: A geometric realization

1

1

2

2

3

3

Figure 2: The boundary of an octahedron

6

We now come to the combinatorial information about simpli- cial complexes that is our primary interest in this chapter. For

i ≥ −1, let fi be the number of i-dimensional faces of ∆. Thus f−1 = 1 unless ∆ = Ø, and f0 = #V , the number of vertices of

∆. If dim∆ = d− 1, then the vector

f(∆) = (f0, f1, . . . , fd−1)

is called the f -vector of ∆. Thus the simplicial complex ∆ of Figure 1 has f -vector (8, 10, 3), while that of Figure 2 has f -

vector (6, 12, 8).

An important general problem is to characterize the f -vector

of various classes of simplicial complexes. The first class to come to mind is all simplicial complexes. In other words, what vectors

(f0, f1, . . . , fd−1) of positive integers are f -vectors of (d − 1)- dimensional simplicial complexes? Although this result is not

directly related to the upcoming connection with commutative algebra, we will discuss it because of its general interest and its analogy to the upcoming Theorem 13.28.

We first make some strange-looking definitions and then ex- plain their connection with f -vectors.

13.5 P