Shifted simplicial complexes and algebraic shifting

AMS Regional Meeting

Binghamton Univ. Oct., ’03 Shifted simplicial complexes and algebraic

shifting

Art Duval, University of Texas at El Paso

OVERVIEW

• shifted complexes

• algebraic shifting – symmetric, exterior

– iterated Betti numbers ∗ characterizations

∗ decompositions

• Laplacians – shifted complexes and matroids – recursion

WHY ALGEBRAIC SHIFTING?

It maps a simplicial complex Γ to a shifted simplicial complex Δ(Γ), such that:

• many algebraic, topological invariants preserved; and

• Δ(Γ) is shifted, so

– Δ(Γ) is combinatorially simpler; and – those algebraic and topological invariants are easily computed from the combinatorics of Δ(Γ).

Example (Björner-Kalai ’88): To characterize possible pairs of f-vectors and (homology) Betti numbers of simplicial complexes, algebraically shift, preserving f and Betti’s. Betti’s are now easy to read: facets that don’t contain vertex 1.

SHIFTED COMPLEXES

Defn: A simplicial complex Γ on ordered vertex set [n] = {1, …, n} is shifted if

F ∈ Γ, v′ < v ⇒ (F − v) ˙∪ v′ ∈ Γ.

Examples:

123 134 234 17 124 135 235 46 125 136 236 126 145  [figure: 12; 13; 14; 15; 24; 23; 34; 25; 35; 45]

Equivalently, Γ is an order ideal in the componentwise partial order on ordered subsets of [n].

NEAR-CONES (Björner-Kalai)

Δ′ ˙∪B any simplicial complex B some facets (boundary of B in Δ′) near-cone Δ = (v ∗ Δ′) ˙∪B, v apex (Alternatively: v ∗ (Δ′ ˙∪ B)− “v ∗ B”)

Homology Betti numbers easy to compute:

β̃_{i}(Δ) := dim H̃_{i}(Δ) = #B_{i}

(facets of each dimension, not containing vertex 1).

Examples:

Betti numbers (1, 1, 0) and (0, 0, 0).

[figure]

SHIFTED IS ITERATED NEAR-CONE

Δ = 1 ∗ \overbrace{((2 ∗ \underbrace{((3 ∗ Δ′′′) ˙∪ B_{2})}_{Δ′′} ˙∪B_{1})}^{Δ′} ˙∪B_{0}

Example:

\begin{matrix}Δ′′′ = & \{∅\} \\ Δ′′ = & 3 ∗ Δ′′′ ˙∪ \{4, 5, 6\} \\ Δ′ = & 2 ∗ Δ′′ ˙∪ \{34, 35, 36, 45, 7\} \\ Δ = & 1 ∗ Δ′ ˙∪ \{234, 235, 236, 46\} \end{matrix}

123 134 234
124 135 235
125 136 236
126 145 46

17

SHIFTED ⇒ SHELLABLE

Shelling is a way to build a simplicial complex one facet at a time, so that as each facet F is added, a unique new minimal face R(F) is added. Therefore Δ = ˙∪_{s}[R(F_{s}), F_{s}]. For a shellable complex (Björner-Wachs ’96),

h_{i,r}(Δ) = #{facets F : |R(F)| = r, |F | = i}.

A shifted complex has a canonical shelling, by arranging facets in lexicographic order. In this shelling, R(F) = F − [init(F)]. Thus, for a shifted complex,

h_{i,r}(Δ) = #{facets F : init(F) = i−r, |F | = i}.

Example: 123 134 234 17 124 135 235 46 125 136 236 126 145

ALGEBRAIC SHIFTING (Kalai) Map simplicial complex Γ to new simplicial complex Δ^{e}(Γ). Exterior version Stanley-Reisner face-ring:

x^{F} := ∧_{i∈F} x_{i}

I_{Γ} := ⟨x^{F} : F ∉ Γ⟩
Λ[Γ] := Λ[x_{1}, …, x_{n}]/I_{Γ}
y_{j} := α_{j1}x_{1} + α_{j2}x_{2} + ⋯ + α_{jn}x_{n},

where α_{ij}’s “generic” (for instance, added algebraically indpt. variables). Define Δ^{(e)} by: F ∈ Δ^{e}(Γ) ⇔ y^{F} ∉ span {y^{G}: G <_{lex} F } in Λ[Γ] Equivalently,

I_{Δ^{e}(Γ)} = Gin_{revlex} (I_{Γ}) = in_{revlex} (gI_{Γ}), where g is “generic” in GL(n). (Gin is generic initial ideal, and in is initial ideal, from Gröbner basis theory.)

SYMMETRIC ALGEBRAIC SHIFTING

(Kalai ’91, but also recent papers by Herzog, et. al.)

Use ordinary (commutative) Stanley-Reisner facering, and then, almost as before,

I_{Δ^{s}(Γ)} = ϕGin_{revlex} (I_{Γ}),

where ϕ is the “squarefree” operator, e.g.,

ϕ(y_{4}y_{6}^{3}y_{7}) = ϕ(y_{4}y_{6}y_{6}y_{6}y_{7})

= y_{4−4} y_{6−3} y_{6−2} y_{6−1} y_{7−0} = y_{0}y_{3}y_{4}y_{5}y_{7}

This is of interest for graded ideals other than I_{Γ} (i.e., not squarefree), without applying ϕ. In other words Gin_{revlex} is an interesting operator on arbitrary graded ideals. “Strongly stable” ideal is commutative algebra version of shifted complex, and Gin(I) is strongly stable.

“AXIOMS” OF ALGEBRAIC SHIFTING

1. Δ(Γ) is a shifted simplicial complex;

2. Γ′ ⊆ Γ ⇒ Δ(Γ′) ⊆ Δ(Γ);

3. f(Γ) = f(Δ(Γ)), β̃(Γ) = β̃(Δ(Γ));

4. Cone (Δ(Γ)) = Δ(Cone (Γ));

5. Γ shifted ⇒ Δ(Γ) = Γ;

6. Γ Cohen-Macaulay iff Δ(Γ) CM (note that a shifted complex is CM iff it is pure).

(Note: 5 follows from the previous properties!)

Example: Alg. shift triangular bipyramid.

[figure]

ITERATED BETTI NUMBERS

Algebraic version of deconing of shifted complexes. Exterior (D-Rose ’00; earlier version Kalai) or symmetric (Babson-Novik-Thomas).

Take homology (exterior) or local cohomology (symmetric) of exterior or symmetric facering using the first generic variable, then algebraically “peel off” that variable. Repeat until there’s nothing left. The iterated Betti numbers are the dimensions of homology or local cohomology at each step.

Equivalently, read the iterated Betti numbers of Δ(Γ):

b_{i,r}(Γ) = h_{i,r}(Δ(Γ))

= #{facets F : init(F) = i − r, |F | = i}.

F = {1, 2, …, i − r; k_{1}, …, k_{r}}

ALGEBRAIC BETTI NUMBERS β_{i,j}(Γ), invariants of minimal free resolution of k[Γ] over S:

0 → F_{t} → ⋯ → F_{1} → S^{1} → k[Γ] → 0

F_{i} = _{j}^{⨁} S(−j)^{β_{i,j}}

It was long known that algebraic Betti numbers, in addition to being important in and of themselves, determine many interesting invariants of k[Γ] (equivalently, Γ):

• Krull dimension (1 + dim Γ);

• Hilbert series (f-vector);

• homological dimension;

• regularity;

• depth; and

• topological Betti numbers of Γ.

EXTREMAL NUMBERS

Extremal algebraic Betti numbers (Bayer-Charalambous-Popescu ’99): β_{i,j} ≠ 0, can’t make i or j − i bigger, without making β = 0. (Southeast corner of Macaulay diagram.)

Easy to show these are enough to find invariants of previous slide, except for the Hilbert series (f-vector).

Extremal symmetric iterated Betti numbers (BNT): b_{i,r}^{s}(Γ) = h_{i,r}(Δ^{s}(Γ)) ≠ 0, can’t make i smaller, or r bigger, without making b = 0. (Recall this counts facets F = [i − r] ˙∪ R in Δ^{s}(Γ), with |F | = i, |R| = r).

Thm (BNT): Extremal symmetric iterated Betti numbers determine the extremal algebraic Betti numbers.

CHARACTERIZING INVARIANTS

Characterize those many invariants of all simplicial complexes.

reduced to

Characterize extremal h-numbers (or, “init” data) of all shifted complexes.

extremal h (or, “init”) of Δ^{s}(Γ)

→ extremal symm. iterated Bettis of Γ

→ extremal Betti numbers of Γ

→ various invariants of Γ

Extremal: h_{i,r} ≠ 0, can’t make i smaller, or r bigger, without making h = 0. (Recall this counts facets F = [i−r] ˙∪R, with |F | = i, |R| = r).

DECOMPOSITIONS: COHEN-MACAULAY COMPLEXES

Conj (Stanley ’79, Garsia ’80): If Δ is Cohen-Macaulay, then it may be partitioned

Δ = ˙∪_{s}[R_{s}, F_{s}]

([R_{s}, F_{s}] denotes a Boolean interval) where each F_{s} is a facet of Δ, and so

h_{j}(Δ) = #{s: |R_{s}| = j}.

For a pure shellable complex,

h_{j}(Δ) = h_{d,j}(Δ) = #{facets F : |R(F)| = j}.

DECOMPOSITIONS: ALL COMPLEXES

Conj (Kalai ’93): If

Δ^{e}(Γ) = ˙∪_{s}[F_{s}, G_{s}]

is a “nice” partition of Δ(Γ), then there is a partition

Γ = ˙∪_{s}[A_{s}, B_{s}]

where

dim A_{s} = dim F_{s}, dim B_{s} = dim G_{s}.

“Nice” includes the canonical shelling of a shifted complex, where R(F) = F − [init(F)], so

Conj (D-Zhang ’01): Any simplicial complex Γ can be partitioned

Γ = ˙∪_{s}[A_{s}, B_{s}]

where

#{s: |A_{s}| = j, |B_{s}| = i} = h_{i,j}(Δ^{e}(Γ)) = b_{i,j}^{e}(Γ).

Prop DZ ⇒ Garsia-Stanley

BOOLEAN TREES

[figure]

Thm (D-Zhang): Any simplicial complex Γ can be partitioned Γ = ˙∪_{s}T_{s}, where each T_{s} is a Boolean tree, and

#{s: |min (T_{s})| = j, |max (T_{s})| = i} = b_{i,j}^{e}(K).

Cor: If Δ is Cohen-Macaulay, then it may be partitioned Δ = ˙∪T_{s}, where each T_{s} is a Boolean tree whose maximal element is a facet of Δ, and

#{s: |min (T_{s})| = j} = h_{j}(Δ).

Question: How much of this can we repeat for symmetric iterated Betti’s? Especially since Cohen-Macaulay is defined in symmetric (commutative) algebra. Note BNT conjecture: b_{i,j}^{s} ≤ b_{i,j}^{e}.

LAPLACIANS

C_{i} = CΓ_{i}, the i-dimensional ℝ-chains of Γ (ℝ-linear combinations of i-dim’l faces of Γ)

∂ = ∂_{i}: C_{i} → C_{i−1} usual signed boundary δ_{i−1} = ∂_{i}^{∗}: C_{i−1} → C_{i} coboundary.

C_{i+1} ⇌^{∂}_{∂^{∗}} C_{i} ⇌^{∂}_{∂^{∗}} C_{i−1}

Defn: i-dimensional Laplacian of Γ:

L_{i}(Γ) = ∂_{i+1} ∂_{i+1}^{∗} + ∂_{i}^{∗}∂_{i}: C_{i} → C_{i}

[figure]

Easy observations about s, eigenvalues

s(L_{i}) = s(∂_{i+1} ∂_{i+1}^{∗} ) ∪ s(∂_{i}^{∗}∂_{i})

s(∂_{i}^{∗}∂_{i}) = s(∂_{i}∂_{i}^{∗}), except for 0’s, and number of 0 eigenvalues is ith Betti number. So we may as well just consider s′′_{i} = s(∂_{i}^{∗}∂_{i}), which only depends on C_{i}.

DEGREE SEQUENCES

Defn: d_{i} is the i-dimensional degree sequence (d_{i})_{j} = # i-faces containing vertex j.

Example:

123 134 234 124 135 235 125 136 236 126 145  8 7 7 4 4 3

s′′ = (6, 6, 6, 5, 3, 3, 3, 1, 0, 0, 0)

Thm (D-Reiner ’02): If a simplicial complex is shifted, then

s′′_{i} = (d_{i})^{T} .

Also integral for

• matroids (Kook-Reiner-Stanton ’00)

• chessboard complexes (Friedman-Hanlon ’98)

• matching complexes of K_{n} (Dong-Wachs ’02).

MATROIDS AND SHIFTED COMPLEXES

Both: collection of subsets of ground set E = {1, …, n}.

Matroid bases B: ∀B ∈ B, ∀b ∈ B ∀B′ ∈ B, ∃b′ ∈ B′ such that

(B − b) ∪ b′ ∈ B.

Shifted family K: ∀F ∈ K, ∀v ∈ F ∀v′ < v, if v′ ∉ F, then

(F − v) ∪ v′ ∈ K.

Independence complex IN(M) of matroid M is simplicial complex of subsets of bases (these are the independent sets).

Simplicial complex Δ is shifted if it is shifted in every dimension. Note that taking all subsets of the members of a shifted family gives a shifted simplicial complex.

SPECTRAL RECURSION FOR MATROIDS…

S_{M}(t, q) := _{i}^{∑} t^{i} _{λ∈s(L_{i−1}(IN(M)))}^{∑} q^{λ}

Tutte-Grothendieck invariants have a deletioncontraction recursion:

ϕ(M) = ϕ(M − e) + ϕ(M/e)
B(M − e) = {B ∈ B: e ∉ B}  (r = r(M))
B(M/e) = {B − e: B ∈ B, e ∈ B} (r = (M) − 1)

Thm (Kook): S_{M} = qS_{M−e} + qtS_{M/e} +(1 − q)(error term ).

Conj (Kook-Reiner): error term = S_{(M−e,M/e)}, where (M − e, M/e) = (IN(M − e), IN(M/e)) is the “relative complex” of IN(M − e) with all the faces from IN(M/e) removed.

Thm: This is true, i.e.,

S_{M} = qS_{M−e} + qtS_{M/e} + (1 − q)S_{(M−e,M/e)}.

… AND FOR SHIFTED COMPLEXES

Generalize deletion and contraction to arbitrary simplicial complex Γ.

Γ − e = {F ∈ Γ: e ∉ F }
Γ/e = {F − e: F ∈ Γ, e ∈ F }  = lk_{Γ} e

[figure]
S_{Γ}(t, q) := _{i}^{∑} t^{i} _{λ∈s(L_{i−1}(Γ))}^{∑} q^{λ}

Thm: Spectral recursion holds for shifted complexes Δ:

S_{Δ} = qS_{Δ−e} + qtS_{Δ/e} + (1 − q)S_{(Δ−e,Δ/e)} .

COMMON GENERALIZATION?

What else has integral Laplacian spectrum, and satisfies the spectral recursion? Call such complexes integral, and spectral, respectively.

Defn: join Γ_{1} ∗ Γ_{2} = {F_{1} ˙∪ F_{2} : F_{i} ∈ Γ_{i}} Thm: If Γ_{1} and Γ_{2} are integral (resp., spectral), then so is Γ_{1} ∗ Γ_{2}.

disjoint union Thm: If Γ_{1} and Γ_{2} are integral (resp., spectral), then so is Γ_{1} ˙∪ Γ_{2}.

Defn: i-skeleton Γ^{(i)} := {F ∈ Γ: dim F ≤ i}. Thm: If Γ is integral (resp., spectral), then so is Γ^{(i)}, for every i.

DUALS

Recall matroid dual: B^{∗} = {E − B: B ∈ B}. Defns: dual Γ^{∗} := {E − F : F ∈ Γ} (simplicial complex ↔ order filter) complement Γ^{c} = {F ⊆ E: F ∉ Γ} (simplicial complex ↔ order filter) Alexander dual Γ^{∨} := Γ^{∗c} = Γ^{c∗} (simplicial complex ↔ simplicial complex) Thm: Γ integral (resp., spectral) iff Γ^{∗} integral (resp., spectral) iff Γ^{c} integral (resp., spectral). (modify spectral recursion, slightly, for order filters: S_{Γ^{∗}} = qS_{Γ^{∗}−e} + qtS_{Γ^{∗}/e} + (1 − q)tS_{(Γ^{∗}/e,Γ^{∗}−e)} ) Cor: Γ integral (resp., spectral) iff Γ^{∨} is. Rmk: Γ is shifted iff Γ^{∨} is