Counting weighted simplicial spanning trees of shifted complexes

CombinaTexas

Texas A&M February, ’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

COUNTING SPANNING TREES OF K_{n} Thm (Cayley): K_{n} has n^{n−2} spanning trees. T spanning tree: set of edges containing all vertices and

1. |T |= n − 1

2. no cycles (H̃_{1}(T) = 0)

3. connected (H̃_{0}(T) = 0) Note: Any two conditions imply the third.

WITH WHAT WEIGHTING?

vertices Silly (n^{n−2}(x_{1} ⋯ x_{n})) edges No nice structure (can’t see n^{n−2}) edges and vertices Get Prüfer coding

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

∑_{T ∈ST (K_{n})} wt T = (x_{1} ⋯ x_{n})(x_{1} + ⋯ + x_{n})^{n−2}

ARBITRARY GRAPHS

Thm (Matrix Tree): Graph G has | det L_{r}(G)| spanning trees, where L_{r}(G) is the reduced Laplacian matrix of G.

Defn 1: L(G) = D(G) − A(G) D(G) = diag (deg v_{1}, …, deg v_{n}) A(G) = adjacency matrix Defn 2: L(G) = ∂(G)∂(G) ^{T} ∂(G) = incidence matrix (boundary matrix) “Reduced”: remove rows/columns corresponding to any one vertex

Proof (Matrix Tree Theorem):

det L_{r}(G) = det ∂_{r}(G)∂_{r}(G)^{T} = _{T}^{∑}(det ∂_{r}(T))^{2}
= _{T}^{∑}(±1)^{2}

by Binet-Cauchy

EXAMPLES

Example:

[figure: 1; 2; 3; 4]

(\begin{matrix}3 & −1 & −1 & −1 \\ −1 & 3 & −1 & −1 \\ −1 & −1 & 2 & 0 \\ −1 & −1 & 0 & 2 \end{matrix}) , (\begin{matrix}−1 & −1 & −1 & 0 & 0 \\ 1 & 0 & 0 & −1 & −1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{matrix})

Example: K_{n}

L(K_{n}) = nI − J  (n × n);
L_{r}(K_{n}) = nI − J  (n − 1 × n − 1)
det L_{r} = ∏ eigenvalues
= (n − 0)^{(n−1)−1} (n − (n − 1))
= n^{n−2}

WEIGHTED MATRIX TREE THEOREM

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

where L̂ is weighted Laplacian.

Defn 1: L̂(G) = D̂(G) − Â(G)

D(G) = diag (d̂eg v_{1}, …, d̂eg v_{n}) d̂eg v_{i} = ∑_{v_{i}v_{j}∈E} x_{i}x_{j}

A(G) = adjacency matrix (entry x_{i}x_{j} for edge v_{i}v_{j})

Defn 2: L̂(G) = ∂(G)B(G)∂(G) ^{T}

∂(G) = incidence matrix B(G) diagonal, indexed by edges, entry ±x_{i}x_{j} for edge v_{i}v_{j}

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} = 234 |\begin{matrix}1 + 3 + 4 & −√23 & −√24 \\ −√23 & 1 + 2 & 0 \\ −√24 & 0 & 1 + 2 \end{matrix}|

= 234|1I + (\begin{matrix}3 + 4 & −√23 & −√24 \\ −√23 & 2 & 0 \\ −√24 & 0 & 2 \end{matrix})|

= 234(1 + 0)(1 + 2)(1 + 2 + 3 + 4) = (1234)(1 + 2)(1 + 2 + 3 + 4)

THRESHOLD GRAPHS

Defn 1: V = 1, …, n E ∈ E, i ∉ E, j ∈ E, i < j ⇒ E ∪ i − j ∈ E. Defn 2: Can build recursively, by adding isolated vertices, and coning.

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

Thm (Merris ‘94): Threshold graph has

_{r≠1}^{∏} (d^{T})_{r}

spanning trees, where d is degree sequence. Thm (Martin-Reiner ‘03; implied by Remmel-Williamson ‘02): If G is threshold, then

_{T ∈ST (G)}^{∑} wt T = (x_{1} ⋯ x_{n}) _{r≠1}^{∏} ((d^{T})_{r} ; ∑ ; i=1 x_{i}).

SIMPLICIAL SPANNING TREES of K_{n}^{k}

Simplicial complex: Δ ⊆ 2^{V}; F ⊆ G ∈ Δ ⇒ F ∈ Δ. K_{n}^{k} denotes the k-dimensional complete complex on n vertices (so K_{n} = K_{n}^{1}).

Simplicial spanning trees of K_{n}^{k} (Kalai, ‘83): 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 (K_{n}^{k})}^{∑} |H̃_{k−1}(T)|^{2} = n^{\binom{n−2}{k}}

WEIGHTING

As before, weight tree by product of the faces of the tree, and, for nice factoring, weight face by product of vertices.

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

Thm (Kalai ’83):

_{T ∈SST (K_{n})}^{∑}|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, again. “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

EXAMPLE n = 4, k = 2

∂^{T} = 12 13 14 23 24 34 123 -1 1 0 -1 0 0 124 -1 0 1 0 -1 0 134 0 -1 1 0 0 -1 234 0 0 0 -1 1 -1

L = (\begin{matrix}2 & −1 & −1 & 1 & 1 & 0 \\ −1 & 2 & −1 & −1 & 0 & 1 \\ −1 & −1 & 2 & 0 & −1 & −1 \\ 1 & −1 & 0 & 2 & −1 & 1 \\ 1 & 0 & −1 & −1 & 2 & −1 \\ 0 & 1 & −1 & 1 & −1 & 2 \end{matrix})

Note that L_{F,G} ≠ 0 iff F and G differ by just one vertex.

SIMPLICIAL SPANNING TREES of ARBITRARY COMPLEXES

Defn: (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.

f_{k} is number of k-dimensional faces; β_{k} = dim_{ℚ} H̃_{k}

SIMPLICIAL MATRIX TREE THEOREM Thm (DKM):

_{T ∈SST (Δ)}^{∑} |H̃_{k−1}(T)|^{2}= \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)} There is also analogous weighted version.

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_{Δ}

(D-Reiner ‘02) Eigenvalues of top-dimensional Laplacian given by d^{T} where d is degree sequence, d_{i} =|{facets F : i ∈ F }|.

EXAMPLE: BIPYRAMID

B_{Δ} = 234, 235 lk_{Δ} 1 = 23, 24, 25, 34, 25; 2, 3, 4, 5; ∅ del_{Δ} 1 = lk_{Δ} 1 ˙∪ B_{Δ} . Eigenvalues COUNTING TREES OF SHIFTED COMPLEXES

Pick U to be ridges ((k −1)-dimensional faces) containing 1, which is acyclic, and contains (k − 1)-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| ; ∏ ; r=1 1+d_{r}^{T} ; ∑ ; i=1 x_{i},

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