Simplicial complexes

(1)

Stanley-Reisner theory Resolutions Resolutions and simplicial complexes Cohen-Macaulay bipartite graphs

The interplay between graphs, simplicial complexes and commutative algebra

Informatics seminar, April 2016

Gunnar Fløystad

April 8, 2016

Gunnar Fløystad The interplay between graphs, simplicial complexes and commutative algebra Informatics seminar, April 2016

(2)

Simplicial complexes

V finite set.

Definition

A simplicial complex ∆ on V is a family of subset of V such that if X ∈ ∆ and Y ⊆ X , then Y ∈ ∆.

Example

{1, 2, 3}, {3, 4}, {1, 2}, {2, 3}, {1, 3}, {1}, {2}, {3}, {4},

∅

Topological realization:

Triangle with an edge attached.

(3)

Squarefree monomial ideals

Example

x ₂ x ₄ x ₅ x ₇ is a squarefree monomial. Write it m _{2,4,5,7} .

Definition

An ideal I ⊆ k [x 1 , . . . , x n ] is a squarefree monomial ideal if it is generated by squarefree monomials.

(4)

Stanley-Reisner ring

Simiplicial complexes on [n] = {1, 2, 3, . . . , n} ¹⁻¹ ↔ squarefree monomial ideals I _∆ :

R 6∈ ∆ ⇔ m _R ∈ I _∆ .

k k 1 n ∆

Note: R ∈ ∆ ⇔ m _R is nonzero in k [∆].

(5)

Stanley-Reisner ring

Simiplicial complexes on [n] = {1, 2, 3, . . . , n} ¹⁻¹ ↔ squarefree monomial ideals I _∆ :

R 6∈ ∆ ⇔ m _R ∈ I _∆ .

Definition

Stanley-Reisner ring k [∆] = k [x 1 , . . . , x n ]/I _∆ . Note: R ∈ ∆ ⇔ m _R is nonzero in k [∆].

(6)

Founding fathers

Richard Stanley, MIT

Proof of upper bound conjecture for simplicial spheres, 1975.

Melvin Hochster, U. of Michigan

Seminal paper, 1975

(7)

Rings from graphs I

Stanley-Reisner ring

Graph G :

1 2 3

4

5 Stanley-Reisner ideal:

I _G = hx ₁ x ₃ , x ₂ x ₄ , x ₁ x ₅ , x ₂ x ₅ , x ₃ x ₄ x ₅ i.

Stanley-Reisner ring k[G ] = k[x ₁ , . . . , x ₅ ]/I _G .

(8)

Rings from graphs I

Stanley-Reisner ring

Graph G :

1 2 3

4

5 Stanley-Reisner ideal:

I _G = hx ₁ x ₃ , x ₂ x ₄ , x ₁ x ₅ , x ₂ x ₅ , x ₃ x ₄ x ₅ i.

Stanley-Reisner ring k[G ] = k[x ₁ , . . . , x ₅ ]/I _G .

(9)

Rings from graphs II

Edge ideals

1 2 3

4

5 Edge ideal:

I (G ) = hx ₁ x ₂ , x ₂ x ₃ , x ₃ x ₄ , x ₄ x ₁ , x ₄ x ₅ , x ₃ x ₅ i.

The ring k [x 1 , . . . , x 5 ]/I (G ) is also a Stanley-Reisner ring k [∆]. The simplicial complex ∆ is the independence complex of the graph G .

(10)

Rings from graphs II

Edge ideals

1 2 3

4

5 Edge ideal:

I (G ) = hx ₁ x ₂ , x ₂ x ₃ , x ₃ x ₄ , x ₄ x ₁ , x ₄ x ₅ , x ₃ x ₅ i.

The ring k [x 1 , . . . , x 5 ]/I (G ) is also a Stanley-Reisner ring k [∆]. The

simplicial complex ∆ is the independence complex of the graph G .

(11)

Algebra

Let ∆ be a simplicial complex.

k [∆] is a ring. Use machinery of algebra to study ∆.

(12)

Bases and minimal generating sets

Field k vector space V dimension of V . Ring R module M ?

Modules rarely have a basis. Instead we take a minimal generating

set.

(13)

Example I

Example

Ring R = k [x , y , z]. Consider the ideal I = (xz, yz) ⊆ R (this is a module).

xz and yz form a minimal generating set.

Dependency y · xz − x · yz = 0.

Make a map

I ←− ^d Re ⊕ Rf = R ² xz ← e

yz ← f

(14)

Example I

Example

Ring R = k [x , y , z]. Consider the ideal I = (xz, yz) ⊆ R (this is a module).

xz and yz form a minimal generating set.

Dependency y · xz − x · yz = 0.

Make a map

I ←− ^d Re ⊕ Rf = R ² xz ← e

yz ← f

(15)

Make a map

I ←− ^d Re ⊕ Rf = R ² xz ← e

yz ← f

We see that (y , −x ) = ye − xz is in the kernel (nullspace) of d , in fact generates the kernel.

The kernel K of d are the (s, t) ∈ R ² such that (s, t) −→ ^d 0. The kernel K is a submodule of R ² .

Here (y , −x ) is in fact a basis for the kernel K , meaning that the map

K ← R ¹ = Rg (y , −x ) ← g ye − xf ← g is an isomorphism.

(16)

Make a map

I ←− ^d Re ⊕ Rf = R ² xz ← e

yz ← f

We see that (y , −x ) = ye − xz is in the kernel (nullspace) of d , in fact generates the kernel.

The kernel K of d are the (s, t) ∈ R ² such that (s, t) −→ ^d 0.

The kernel K is a submodule of R ² .

K ← R ¹ = Rg

(y , −x ) ← g

ye − xf ← g

is an isomorphism.

(17)

Make a map

I ←− ^d Re ⊕ Rf = R ² xz ← e

yz ← f

We see that (y , −x ) = ye − xz is in the kernel (nullspace) of d , in fact generates the kernel.

The kernel K of d are the (s, t) ∈ R ² such that (s, t) −→ ^d 0.

The kernel K is a submodule of R ² .

Here (y , −x ) is in fact a basis for the kernel K , meaning that the map

K ← R ¹ = Rg (y , −x ) ← g ye − xf ← g is an isomorphism.

(18)

Continuing

In general:

Iterate process. Find minimal generating set u 1 , . . . , u p of K . Make a map K ←− ^d

²

R ^p .

Continue and get

I ← R ^{r d}

¹

←− ^(=d) R ^p ←− ^d

²

R ^q ← · · · ,

called the resolution of I .

(19)

Example II

Example

I = (xz, yz) ← R ² ← R ¹ .

Variations:

R/I ← R ¹ ^[xz,yz] ←− R ²

h

_y

−x

i

←− R ¹

I ← R (−2) ² ← R (−3) ¹

(20)

Example II

Example

I = (xz, yz) ← R ² ← R ¹ .

Variations:

R /I ← R ¹ ^[xz,yz] ←− R ²

h

_y

−x

i

←− R ¹

I ← R (−2) ² ← R (−3) ¹

(21)

Founder commutative algebra

1862-1943

(22)

Commutative Algebra

Founding theorems

Theorem (1890)

Any ideal in a polynomial ring has a finite generating set.

Any finitely generated module over a polynomial ring

k [x ₁ , . . . , x _n ] has a minimal free

resolution of length ≤ n.

(23)

Commutative Algebra

Founding theorems

Theorem (1890)

Any ideal in a polynomial ring has a finite generating set.

Theorem (1890)

Any finitely generated module over a polynomial ring

k [x ₁ , . . . , x _n ] has a minimal free resolution of length ≤ n.

(24)

Rings from graphs

Graph G :

1 2 3

4

5 Stanley-Reisner ideal:

I _G = hx ₁ x ₃ , x ₂ x ₄ , x ₁ x ₅ , x ₂ x ₅ , x ₃ x ₄ x ₅ i.

Stanley-Reisner ring k[G ] = k[x ₁ , . . . , x ₅ ]/I _G .

(25)

Resolution of I _G

Resolution

R /I _G ← R ←

R(−2) ⁴

⊕ R(−3) ¹

←

R(−3) ³

⊕ R(−4) ³

← R(−5) ² .

0 1 2 3 o4 = total: 1 5 6 2 0: 1 . . . 1: . 4 3 . 2: . 1 3 2 Dimension of G : 1. Length of resolution: 3 Number of vertices: 5.

(26)

Resolution of I _G

Resolution

R /I _G ← R ←

R(−2) ⁴

⊕ R(−3) ¹

←

R(−3) ³

⊕ R(−4) ³

← R(−5) ² .

0 1 2 3 o4 = total: 1 5 6 2 0: 1 . . . 1: . 4 3 . 2: . 1 3 2

Number of vertices: 5.

(27)

Resolution of I _G

Resolution

R /I _G ← R ←

R(−2) ⁴

⊕ R(−3) ¹

←

R(−3) ³

⊕ R(−4) ³

← R(−5) ² .

0 1 2 3 o4 = total: 1 5 6 2 0: 1 . . . 1: . 4 3 . 2: . 1 3 2 Dimension of G : 1.

Length of resolution: 3 Number of vertices: 5.

(28)

Cohen-Macaulay simplicial complexes

Simplicial complex ∆. Always:

length resolution ≥ (n − 1) − dimension ∆.

Definition

∆ is Cohen-Macaulay if we have equality above.

(29)

Gorenstein simplicial complexes

Stanley-Reisner ideal of six-cycle:

I _C

₆

= (x ₁ x ₃ , x ₂ x ₄ , x ₃ x ₅ , x ₄ x ₆ , x ₅ x ₁ , x ₆ x ₂ , x ₁ x ₄ , x ₂ x ₅ , x ₃ x ₆ ).

Betti diagram of resolution:

0 1 2 3 4 o18 = total: 1 9 16 9 1 0: 1 . . . . 1: . 9 16 9 . 2: . . . . 1

Definition

∆ is Gorenstein if:

∆ is Cohen-Macaulay

Resolution of ∆ has symmetric form

(30)

Gorenstein simplicial complexes

Stanley-Reisner ideal of six-cycle:

I _C

₆

= (x ₁ x ₃ , x ₂ x ₄ , x ₃ x ₅ , x ₄ x ₆ , x ₅ x ₁ , x ₆ x ₂ , x ₁ x ₄ , x ₂ x ₅ , x ₃ x ₆ ).

Betti diagram of resolution:

0 1 2 3 4 o18 = total: 1 9 16 9 1 0: 1 . . . . 1: . 9 16 9 . 2: . . . . 1

Definition

∆ is Gorenstein if:

∆ is Cohen-Macaulay

Resolution of ∆ has symmetric form

(31)

Resolution of edge ideal

Graph G:

1 2 3

4 5 I (G ) = hx ₁ x ₂ , x ₂ x ₃ , x ₃ x ₄ , x ₄ x ₁ , x ₄ x ₅ i

0 1 2 3 o13 = total: 1 5 6 2 0: 1 . . . 1: . 5 6 2

Dimension independence complex: 2

Length resolution: 3 Vertices: 5

Not Cohen-Macaulay!

(32)

Resolution of edge ideal

Graph G:

1 2 3

4 5 I (G ) = hx ₁ x ₂ , x ₂ x ₃ , x ₃ x ₄ , x ₄ x ₁ , x ₄ x ₅ i

0 1 2 3 o13 = total: 1 5 6 2 0: 1 . . . 1: . 5 6 2

Length resolution: 3 Vertices: 5

Not Cohen-Macaulay!

(33)

Resolution of edge ideal

Graph G:

1 2 3

4 5 I (G ) = hx ₁ x ₂ , x ₂ x ₃ , x ₃ x ₄ , x ₄ x ₁ , x ₄ x ₅ i

0 1 2 3 o13 = total: 1 5 6 2 0: 1 . . . 1: . 5 6 2

Dimension independence complex: 2

Length resolution: 3 Vertices: 5

Not Cohen-Macaulay!

(34)

Let P finite poset. Let P ₁ and P ₂ be copies of P . If p ∈ P write

p ₁ ∈ P ₁ and p ₂ ∈ P ₂ .

(35)

Make a bipartite graph G = (P ₁ , P ₂ ) where the edges are pairs {p ₁ , q 2 } such that p ≤ q.

Theorem (J.Herzog, T.Hibi, 2004)

A bipartite graph is Cohen-Macaulay if and only if it comes from a poset as above.

(36)

Make a bipartite graph G = (P ₁ , P ₂ ) where the edges are pairs {p ₁ , q 2 } such that p ≤ q.

Theorem (J.Herzog, T.Hibi, 2004)

A bipartite graph is Cohen-Macaulay if and only if it comes from a

poset as above.

(37)

Generalization

Consider a chain p ¹ ≤ p ² ≤ · · · ≤ p ⁿ in the poset P . Squarefree monomial: x _1,p

¹

x _2,p

²

· · · x _n,p

ⁿ

. L(n, P ): ideal generated by all such monomials.

Theorem (2011, Herzog et.al.)

The ideal L(n, P ) defines a Cohen-Macaulay simplicial complex of codimension |P| in the simplex on n|P | vertices.

(38)

Generalization

Consider a chain p ¹ ≤ p ² ≤ · · · ≤ p ⁿ in the poset P . Squarefree monomial: x _1,p

¹

x _2,p

²

· · · x _n,p

ⁿ

. L(n, P ): ideal generated by all such monomials.

Theorem (2011, Herzog et.al.)

The ideal L(n, P ) defines a Cohen-Macaulay simplicial complex of

codimension |P | in the simplex on n|P | vertices.

(39)

Balls and spheres

Theorem (2016, D’Ali,F.,Nematbahksh)

The ideal L(n, P ) defines a simplicial (i.e. triangulated) ball (of dimension (n − 1)|P | − 1).

Simplicial complexes

The interplay between graphs, simplicial complexes and commutative algebra

Informatics seminar, April 2016

Gunnar Fløystad

April 8, 2016

Simplicial complexes

V finite set.

Definition

A simplicial complex ∆ on V is a family of subset of V such that if X ∈ ∆ and Y ⊆ X , then Y ∈ ∆.

Example

{1, 2, 3}, {3, 4}, {1, 2}, {2, 3}, {1, 3}, {1}, {2}, {3}, {4},

∅

Topological realization:

Triangle with an edge attached.

Squarefree monomial ideals

Example

x 2 x 4 x 5 x 7 is a squarefree monomial. Write it m {2,4,5,7} .

Definition

An ideal I ⊆ k [x 1 , . . . , x n ] is a squarefree monomial ideal if it is generated by squarefree monomials.

Stanley-Reisner ring

Simiplicial complexes on [n] = {1, 2, 3, . . . , n} 1−1 ↔ squarefree monomial ideals I ∆ :

R 6∈ ∆ ⇔ m R ∈ I ∆ .

k k 1 n ∆

Note: R ∈ ∆ ⇔ m R is nonzero in k [∆].

Stanley-Reisner ring

Simiplicial complexes on [n] = {1, 2, 3, . . . , n} 1−1 ↔ squarefree monomial ideals I ∆ :

R 6∈ ∆ ⇔ m R ∈ I ∆ .

Definition

Stanley-Reisner ring k [∆] = k [x 1 , . . . , x n ]/I ∆ . Note: R ∈ ∆ ⇔ m R is nonzero in k [∆].

Founding fathers

Richard Stanley, MIT

Proof of upper bound conjecture for simplicial spheres, 1975.

Melvin Hochster, U. of Michigan

Seminal paper, 1975

Rings from graphs I

Stanley-Reisner ring

Graph G :

1

2 3

4

5

Stanley-Reisner ideal:

I G = hx 1 x 3 , x 2 x 4 , x 1 x 5 , x 2 x 5 , x 3 x 4 x 5 i.

Stanley-Reisner ring k[G ] = k[x 1 , . . . , x 5 ]/I G .

Rings from graphs I

Stanley-Reisner ring

Graph G :

1

2 3

4

5

Stanley-Reisner ideal:

I G = hx 1 x 3 , x 2 x 4 , x 1 x 5 , x 2 x 5 , x 3 x 4 x 5 i.

Stanley-Reisner ring k[G ] = k[x 1 , . . . , x 5 ]/I G .

Rings from graphs II

Edge ideals

1

2 3

4

5

Edge ideal:

I (G ) = hx 1 x 2 , x 2 x 3 , x 3 x 4 , x 4 x 1 , x 4 x 5 , x 3 x 5 i.

The ring k [x 1 , . . . , x 5 ]/I (G ) is also a Stanley-Reisner ring k [∆]. The simplicial complex ∆ is the independence complex of the graph G .

Rings from graphs II

Edge ideals

1

2 3

4

5

Edge ideal:

I (G ) = hx 1 x 2 , x 2 x 3 , x 3 x 4 , x 4 x 1 , x 4 x 5 , x 3 x 5 i.

The ring k [x 1 , . . . , x 5 ]/I (G ) is also a Stanley-Reisner ring k [∆]. The

simplicial complex ∆ is the independence complex of the graph G .

Algebra

Let ∆ be a simplicial complex.

k [∆] is a ring. Use machinery of algebra to study ∆.

Bases and minimal generating sets

Field k vector space V dimension of V . Ring R module M ?

Modules rarely have a basis. Instead we take a minimal generating

set.

x ₂ x ₄ x ₅ x ₇ is a squarefree monomial. Write it m _{2,4,5,7} .

Simiplicial complexes on [n] = {1, 2, 3, . . . , n} ¹⁻¹ ↔ squarefree monomial ideals I _∆ :

R 6∈ ∆ ⇔ m _R ∈ I _∆ .

Note: R ∈ ∆ ⇔ m _R is nonzero in k [∆].

Simiplicial complexes on [n] = {1, 2, 3, . . . , n} ¹⁻¹ ↔ squarefree monomial ideals I _∆ :

R 6∈ ∆ ⇔ m _R ∈ I _∆ .

Stanley-Reisner ring k [∆] = k [x 1 , . . . , x n ]/I _∆ . Note: R ∈ ∆ ⇔ m _R is nonzero in k [∆].

I _G = hx ₁ x ₃ , x ₂ x ₄ , x ₁ x ₅ , x ₂ x ₅ , x ₃ x ₄ x ₅ i.

Stanley-Reisner ring k[G ] = k[x ₁ , . . . , x ₅ ]/I _G .

I _G = hx ₁ x ₃ , x ₂ x ₄ , x ₁ x ₅ , x ₂ x ₅ , x ₃ x ₄ x ₅ i.

Stanley-Reisner ring k[G ] = k[x ₁ , . . . , x ₅ ]/I _G .

I (G ) = hx ₁ x ₂ , x ₂ x ₃ , x ₃ x ₄ , x ₄ x ₁ , x ₄ x ₅ , x ₃ x ₅ i.

I (G ) = hx ₁ x ₂ , x ₂ x ₃ , x ₃ x ₄ , x ₄ x ₁ , x ₄ x ₅ , x ₃ x ₅ i.

I ←− ^d Re ⊕ Rf = R ² xz ← e

I ←− ^d Re ⊕ Rf = R ² xz ← e

I ←− ^d Re ⊕ Rf = R ² xz ← e

The kernel K of d are the (s, t) ∈ R ² such that (s, t) −→ ^d 0. The kernel K is a submodule of R ² .

K ← R ¹ = Rg (y , −x ) ← g ye − xf ← g is an isomorphism.

I ←− ^d Re ⊕ Rf = R ² xz ← e

The kernel K of d are the (s, t) ∈ R ² such that (s, t) −→ ^d 0.

The kernel K is a submodule of R ² .

K ← R ¹ = Rg

I ←− ^d Re ⊕ Rf = R ² xz ← e

The kernel K of d are the (s, t) ∈ R ² such that (s, t) −→ ^d 0.

The kernel K is a submodule of R ² .

K ← R ¹ = Rg (y , −x ) ← g ye − xf ← g is an isomorphism.

Iterate process. Find minimal generating set u 1 , . . . , u p of K . Make a map K ←− ^d

R ^p .

I ← R ^{r d}

←− ^(=d) R ^p ←− ^d

R ^q ← · · · ,

I = (xz, yz) ← R ² ← R ¹ .

R/I ← R ¹ ^[xz,yz] ←− R ²

←− R ¹

I ← R (−2) ² ← R (−3) ¹

I = (xz, yz) ← R ² ← R ¹ .

R /I ← R ¹ ^[xz,yz] ←− R ²

←− R ¹

I ← R (−2) ² ← R (−3) ¹