A Relative Laplacian spectral recursion

CombinaTexas

Texas State University, San Marcos February, ’05 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)

Theorem: This recursion works for the “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

Let s(L_{i}) denote multiset of eigenvalues of L_{i}. Define a natural generating function:

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

E’vals are integers(!) w/nice formulas(!) for: pairs of shifted complexes with the same vertex ordering (D-Reiner ’02; D ’03);

[figure]

pairs of matroids related by a strong map (Kook-Reiner-Stanton ’00; D ’03).

[figure]

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)

Thm: If Φ is shifted pair (same vertex ordering) or matroid pair (M − f, M/f), then

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

[figure: 5; 15; 24; 35; 25; 34; 134; 234; 124; 125]

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).