Counting weighted simplicial spanning trees of shifted complexes

AMS Southeastern Section Meeting

Davidson College Mar., ’07 Counting weighted simplicial spanning

trees of shifted complexes

Art Duval University of Texas at El Paso Caroline Klivans University of Chicago Jeremy Martin University of Kansas MATRIX TREE THEOREM

_{T ∈ST (G)}^{∑} wt T =| det L̂_{r}(G)|,

where

wt T = _{e∈T}^{∏} wt e = _{e∈T}^{∏}(_{v∈e}^{∏} x_{v}),

“Reduced”: remove rows/columns corresponding to any one vertex

L̂ = ∂∂^{T}, (weighted) Laplacian ∂, weighted boundary (incidence) matrix; the (e, v) entry is ±√wt e

∂^{T} = (\begin{matrix}−√12 & √12 & 0 & 0 \\ −√13 & 0 & √13 & 0 \\ −√14 & 0 & 0 & √14 \\ 0 & −√23 & √23 & 0 \\ 0 & −√24 & 0 & √24 \end{matrix})

Example:  [figure: 1; 2; 3; 4]

EXAMPLE

[figure: 1; 2; 3; 4]  1 2 3 4

L̂ = (\begin{matrix}1(2 + 3 + 4) & −12 & −13 & −14 \\ −12 & 2(1 + 3 + 4) & −23 & −24 \\ −13 & −23 & 3(1 + 2) & 0 \\ −14 & −24 & 0 & 4(1 + 2) \end{matrix} )

L̂_{r} = (\begin{matrix}2(1 + 3 + 4) & −23 & −24 \\ −23 & 3(1 + 2) & 0 \\ −24 & 0 & 4(1 + 2) \end{matrix} )

det L̂_{r} = (1234)(1 + 2)(1 + 2 + 3 + 4)

[figure]

SIMPLICIAL SPANNING TREES of COMPLETE SIMPLICIAL COMPLEX (Kalai ‘83)

Defn: Simplicial spanning tree: (Assume dim k; n vertices.) Set T, of k-dimensional faces, containing all (k − 1)-dimensional faces and:

1. |T |= \binom{n−1}{k}

2. H̃_{k}(T) = 0

3. H̃_{k−1}(T) is finite group

Note: Any two conditions imply the third.

How many are there? Bolker (‘76): should be n^{\binom{n−2}{k}}, but isn’t

Kalai (‘83): proves

_{T ∈SST}^{∑} |H̃_{k−1}(T)|^{2} = n^{\binom{n−2}{k}}

WEIGHTING

wt T = _{F ∈T}^{∏} wt F = _{F ∈T}^{∏}(_{v∈F}^{∏} x_{v})

Thm (Kalai ’83): _{T ∈SST}^{∑}|H̃_{k−1}(T)|^{2}(wt T)

= (x_{1} ⋯ x_{n})^{\binom{n−2}{k−1}}(x_{1} + ⋯ + x_{n})^{\binom{n−2}{k}}

Adin (’92) did something similar for complete r-partite complexes.

KALAI’S THEOREM

Proof (unweighted; weighted is similar):

n^{\binom{n−2}{k}} = det L_{r}(K_{n}^{k}) = det ∂_{r}(K_{n}^{k})∂_{r}(K_{n}^{k})^{T}
= _{T}^{∑}(det ∂_{r}(T))^{2}
= _{T}^{∑}|H̃_{k−1}(T)|^{2}

by Binet-Cauchy. “Reduced” now means pick one vertex, and then remove rows/columns corresponding to all (k − 1)-dimensional faces containing that vertex. L = ∂∂^{T} ∂: Δ_{k} → Δ_{k−1} boundary ∂^{T} : Δ_{k−1} → Δ_{k} coboundary

SIMPLICIAL MATRIX TREE THEOREM

Defn: Simplicial spanning tree of Δ: (Assume dim Δ = k.) k-dimensional complex T containing all (k−1)-dimensional faces of Δ (T^{(k−1)} = Δ^{(k−1)} ) and:

1. f_{k}(T) = f_{k}(Δ) − β_{k}(Δ) + β_{k−1}(Δ)

2. H̃_{k}(T) = 0

3. H̃_{k−1}(T) is finite group

Note: Any two conditions imply the third.

Thm (DKM):

_{T ∈SST (Δ)}^{∑} |H̃_{k−1}(T)|^{2}wt T = \frac{|H̃_{k−2}(Δ)|^{2}}{|H̃_{k−2}(Δ_{U})|^{2}} det L̂_{r}.

U =set of facets of (k − 1)-spanning tree of Δ L̂_{r} is L reduced by all of U Δ_{U} = U ∪ Δ^{(k−2)}

SHIFTED SIMPLICIAL COMPLEXES

Defn: V = 1, …, n F ∈ Δ, i ∉ F, j ∈ F, i < j ⇒ F ∪ i − j ∈ Δ (equivalently, the k-faces form an initial ideal in the componentwise partial order).

Ex: bipyramid = { 123, 124, 125, 134, 135, 234, 235} (and subfaces)

Δ = (1 ∗ lk_{Δ} 1) ˙∪ B_{Δ}

B_{Δ} = {F ∈ Δ: 1 ∉ F, F ˙∪ 1 ∉ Δ} lk_{Δ} 1 = {F − 1 : 1 ∈ F, F ∈ Δ}, shifted del_{Δ} 1 = {G: 1 ∉ G, G ∈ Δ}, shifted β_{i}(Δ) = f_{i}(B_{Δ} ) del_{Δ} 1 = lk_{Δ} 1 ˙∪ B_{Δ}

Example (bipyramid, continued): B_{Δ} = {234, 235 } lk_{Δ} 1 = {23, 24, 25, 34, 25; 2, 3, 4, 5; ∅ } del_{Δ} 1 = lk_{Δ} 1 ˙∪ B_{Δ} .

EIGENVALUES

Thm (D-Reiner ‘02): Non-0 eigenvalues of top-dim’l Laplacian of shifted complex given by d^{T} where d is degree sequence, d_{i} =|{facets F : i ∈ F }|.

Example (bipyramid): {123, 124, 125, 134, 135, 234, 235}

1 2 3 4 5

Example (del1): 234, 235

2 3 4 5 COUNTING TREES OF SHIFTED COMPLEXES

Pick U to be ridges ((k −1)-dimensional faces) containing 1, which is acyclic, and contains (k − 2)-faces of Δ, and so it is (the facets of) a simplicial spanning tree.

Also, H̃_{k−2}(Δ_{U}) = 0, and if Δ is pure and shifted, then H̃_{k−2}(Δ) = 0, so we just have to compute det L̂_{r}.

Ex: bipyramid. Set of all ridges is all possible edges, except 45. U = {12, 13, 14, 15}, so L̂_{r} is indexed by {23, 24, 25, 34, 35 }.

L̂_{r} =

\begin{matrix}23(1 + 4 + 5) & −234 & −235 & 234 & 235 \\ −234 & 24(1 + 3) & 0 & −234 & 0 \\ −235 & 0 & 25(1 + 3) & 0 & −235 \\ 234 & 234 & 0 & (1 + 2)34 & 0 \\ 235 & 0 & −235 & 0 & (1 + 2)35 \end{matrix}

SIMPLIFICATIONS

det L̂_{r} = (23)(24)(25)(34)(35) det M

det M = |\begin{matrix}1 + 4 + 5 & −√34 & −√35 & √24 & √25 \\ −√34 & 1 + 3 & 0 & −√23 & 0 \\ −√35 & 0 & 1 + 3 & 0 & −√23 \\ √24 & −√23 & 0 & 1 + 2 & 0 \\ √25 & 0 & −√23 & 0 & 1 + 2 \end{matrix}|
= |1I + N|

N = (\begin{matrix}4 + 5 & −√34 & −√35 & √24 & √25 \\ −√34 & 3 & 0 & −√23 & 0 \\ −√35 & 0 & 3 & 0 & −√23 \\ √24 & −√23 & 0 & 2 & 0 \\ √25 & 0 & −√23 & 0 & 2 \end{matrix})

Remarkably, N is a weighted Laplacian of del_{Δ} 1; N = ∂∂^{T} with

∂^{T} = (\begin{matrix}√4 & −√3 & 0 & √2 & 0 \\ √5 & 0 & −√3 & 0 & √2 \end{matrix})

The (F, G) entry of this matrix is ±√F − G.

FURTHER SIMPLIFICATIONS

This makes the eigenvalues of this N be 0, 0, 0, 2 + 3, 2 + 3 + 4 + 5, and det M = (1)^{3}(1 + 2 + 3)(1 + 2 + 3 + 4 + 5). Finally it makes the weighted tree enumerator of the bipyramid

(23)(24)(25)(34)(35) × (1)^{3}(1 + 2 + 3)(1 + 2 + 3 + 4 + 5).

More generally,

(_{F ∈R}^{∏} x_{F} ) |R| ; ∏ ; j=1 1+(d^{T})_{j} ; ∑ ; i=1 x_{i},

where R = facets of lk_{Δ} 1 and d is the degree sequence of del_{Δ} 1.

[figure: 2; 3; 4; 5]  2 3 4 5