A Relative Laplacian spectral recursion

Stanley 60th Birthday Conference

MIT June, ’04 A Relative Laplacian spectral recursion

Art Duval, University of Texas at El Paso

OVERVIEW

The eigenvalues of the combinatorial Laplacian of the independence complexes of matroids and of shifted complexes are integral, with combinatorial formulas. (KRS ’00; DR ’02)

For “nice” relative pairs of matroids and shifted complexes, there are nice formulas, too. (D ’03)

These eigenvalues satisfy the same nice recursion for both matroids and shifted complexes. (D ’03)

Conjecture: This recursion works for “nice” relative pairs as well, using the “right” definition of each term of the recursion in the relative case. (new)

SHIFTED FAMILIES AND COMPLEXES

Shifted family K: non-empty family of k-subsets of ground set E = {1, …, n} satisfying

∀F ∈ K, ∀v ∈ F, ∀v′ < v, if v′ ∉ F, then

(F − v) ∪ v′ ∈ K.

Example: 123, 124, 125, 126, 134, 135, 136, 145, 234, 235, 236.

A simplicial complex is shifted if its family of i-dimensional faces is shifted, for all i.

The simplicial complex formed by taking all subsets of every set F ∈ K is a pure shifted simplicial complex.

ORDER IDEAL

[figure: 123; 124; 134; 125; 135; 126; 234; 235; 145; 136; 146; 236; 245; 156; 246; 345; 346; 256; 356; 456]

MATROIDS

Bases B: non-empty family of k-subsets of ground set E = {1, …, n} satisfying

∀B ∈ B, ∀b ∈ B, ∀B′ ∈ B, ∃b′ ∈ B′ such that

(B − b) ∪ b′ ∈ B.

Example:

[figure: 1; 7; 4; 2; 6; 5; 3] B = \begin{aligned}& (3 ∈ B) & & (3 ∉ B) \\ 1346 & 2346 & 1246 & 1456 & 1467 \\ 1347 & 2347 & 1247 & 1457 & 2467 \\ 1356 & 2356 & 1256 & 2456 \\ 1357 & 2357 & 1257 & 2457 \\ 1367 & 2367 & 1267 \end{aligned}

The simplicial complex formed by taking all subsets of every base B ∈ B is the set of independent sets IN(M) of matroid M.

RELATIVE PAIRS OF COMPLEXES If Δ′ ⊆ Δ are a simplicial complexes on the same set of vertices, then Φ = (Δ, Δ′) := Δ − Δ′ is a relative pair of complexes. When Δ′ = ∅, then Φ = (Δ, ∅) = Δ. Φ is an interval in the Boolean algebra.

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} Example:

[figure]

EIGENVALUES OF LAPLACIANS 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 number of 0 eigenvalues is ith Betti number. So we may as well just consider s′′_{i} = s(∂_{i}^{∗}∂_{i}); when Φ = (Δ, ∅) = Δ, s′′_{i} only depends on C_{i}.

C_{i+1} ⇌^{∂}_{∂^{∗}} C_{i} ⇌^{∂}_{∂^{∗}} C_{i−1}
s_{i+1}  s_{i}  s_{i−1}
s′′_{i+1}  s′′_{i}  s′′_{i−1}
0^{β_{i+1}}  0^{β_{i}}  0^{β_{i−1}}
s′_{i+1}  s′_{i}  s′_{i−1}

EIGENVALUES OF SHIFTED COMPLEXES 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  877443 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} ,

in every dimension i.

EIGENVALUES OF SHIFTED PAIRS

Defn: Assume K is a k-family, K′ is a (k − 1)- family, and K′ ⊆ ∂K. Then

d_{j}(K, K′) = {F ∈ K: F − j ∉ K′},

and d(K, K′) = (d_{1}, …, d_{n}).

K 123 124 234 134 145 125 235 135 126 236 136
\overline{K′}  24  34 45 25  35 26 16 36

K′ = {12, 13, 14, 15, 23}

Thm (D ’03): If K and K′ are shifted with the same vertex ordering, then s(K, K′) = d(K, K′)^{T}

744 3 3 3 3 1 1 1

EIGENVALUES OF MATROIDS For matroids, eigenvalues are more easily described in terms of natural generating function:

S_{M}(t, q) := _{i}^{∑} t^{i} _{λ∈s(L_{i−1}(IN(M)))}^{∑} q^{λ} Thm (Kook-Reiner-Stanton ’00): For a matroid M with ground set E,

S_{M}(t, q) = q^{|E|} _{I∈IN(M)}^{∑} t^{rank (Ī)}(q^{−1})^{|π̄(I)|}, where π̄(I) is a function of I involving internal/external activity. (Ask about details later.) In particular, the eigenvalues of M are integers.

EIGENVALUES OF MATROID PAIRS

If the equivalent of pairs of shifted families with the same vertex ordering is strong maps, then it turns out we may as well restrict to (M − e, M/e).

Removing M/e from M − e partitions M − e, by the basic circuit ci(B, e), the unique circuit (minimal dependent set) in B ∪ e, so

L(M − e, M/e) = ⨁ ; \begin{matrix}C circuit \\ e∈C \end{matrix} L(M/C).

[figure: 1; 7; 4; 2; 6; 5; 3]

C =

ci(B, e) 123 345 3467
1246 1257 1456 2456 1467
M − e 1247 1267 1457 2457 2467

1256

[figure: M/C; 7; 6; 5; 4; 2; 6; 1; 7; 2; 5; 1]

SPECTRAL RECURSION FOR MATROIDS…

Tutte polyn. deletion-contraction recursion:

T_{M} = T_{M−e} + T_{M/e}
B(M − e) = {B ∈ B: e ∉ B}  (r = r(M))
B(M/e) = {B − e: B ∈ B, e ∈ B} (r = 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)).

Thm (D ’03): 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 (D ’03): Spectral recursion holds for shifted complexes Δ:

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

RELATIVE RECURSION

Say Φ = (Δ, Δ′). Define

Φ − e = {F ∈ Φ: e ∉ F }
= (Δ − e, Δ′ − e)
Φ/e = {F − e: F ∈ Φ, e ∈ F }
= (Δ/e, Δ′/e)
Φ ∥ e = Φ − {(F, F ˙∪ e): (F, F ˙∪ e) ⊆ Φ}
≈ (Δ − e, (Δ′ − e ∪ Δ/e))
˙∪ ((Δ′ − e ∩ Δ/e), Δ′/e)

Conj: If Δ, Δ′ shifted w/same vertex order or matroids w/strong map, then

S_{Φ} = qS_{Φ−e} + qtS_{Φ/e} + (1 − q)S_{Φ∥e} Example:

124 125 134 234
15 25 34 24 35

5

MORE ABOUT Φ ∥ e

Original description of (Δ−e, Δ/e) was (Δ, st_{Δ} e) (they are the same). In some sense, Φ ∥ e is (Φ, st_{Φ} e).

When plugging in q = 0, S is generating function for homology Betti numbers. (Δ, st_{Δ} e) has same homology as Δ, since st_{Δ} e is contractible, so recursion for Δ is trivially true for all Δ. Same is true for Φ; note st_{Φ} e = (st_{Δ} e, st_{Δ′} e).

EIGENVALUES OF MATROIDS (details)

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

Thm (KRS ’00): For matroid M(E),

S_{M}(t, q) = q^{|E|} _{I∈IN(M)}^{∑} t^{rank (Ī)}(q^{−1})^{|π̄(I)|},

where:

I = π(I) ˙∪ σ(I);

π(I) has internal activity 0 in Ī;

π̄(I) = \overline{π(I)}; and

σ(I) has external activity 0 in Ī/π̄(I).

Etienne-Las Vergnas (’98) first showed that there is a unique such decomposition of I; the algorithm, due to KRS, to find this decomposition was essential to the proof of the spectral recursion for matroids.