Port complexes and the Laplacian spectral recursion

CombinaTexas

Texas A & M Univ. Apr., ’04 Port complexes and the Laplacian

spectral recursion

Art Duval, University of Texas at El Paso

OVERVIEW

The eigenvalues of the combinatorial Laplacian of the independence complexes of matroids are integral and satisfy a Tutte-like recursion.

These things are true for very few other simplicial complexes. Some natural operations, including Alexander duality, preserve being integral and satisfying recursion. But Alexander dual of a matroid is not a matroid!

Ed Swartz says: Steiner complexes generalize matroids, and are closed under Alexander duality.

Conjecture: Laplacian eigenvalues of Steiner complexes are integral, and satisfy the recursion.

MATROIDS (Examples for graphic matroids)

Ground set E: Edges of planar graph G.

Bases B: Spanning trees of G. (Maximal indpendent sets.)

Independent sets I: Forests of G. (Subsets of bases.)

For all matroids, not just graphic: Independence complex IN(M) of matroid M is simplicial complex of independent sets. (Facets are bases.)

Dual M^{∗}: Planar graph dual.

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}

Let

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

be the i-dimensional Laplacian of Δ.

EIGENVALUES OF LAPLACIANS s_{i}(Δ) = eigenvalues (w/multiplicity) of L_{i}(Δ). s integral for

• independence complex IN(M) of matroid M (Kook-Reiner-Stanton, J. AMS ’00)

• shifted complexes (D-Reiner, Trans. AMS ’02)

• chessboard complexes (Friedman-Hanlon, J. Alg. Comb. ’98)

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

• What else??!

SPECTRAL RECURSION

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

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

MORE GENERALLY

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

ALEXANDER DUAL

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

One clue comes from duality: For matroids and Tutte polynomial, T_{M^{∗}}(x, y) = T_{M}(y, x), where B^{∗} = {E − B: B ∈ B}.

Defns:

dual Δ^{∗} := {E − F : F ∈ Δ}
complement Δ^{c} := {F ⊆ E: F ∉ Δ}
Alexander dual Δ^{∨} := Δ^{∗c} = Δ^{c∗}
= {E − F : F ∉ Δ}

[figure]

Thm: Δ integral (resp., spectral) iff Δ^{∨} integral (resp., spectral).

STEINER COMPLEXES

circuits C(M), minimally dependent sets. cocircuits C^{∗}(M) = C(M^{∗}). (In graphic matroids, “cutsets”.) port P(M, e) = {C − {e}: e ∈ C, C ∈ C(M)} P^{∗}(M, e) = {C^{∗} − {e}: e ∈ C^{∗}, C^{∗} ∈ C^{∗}(M)}

[figure]

Steiner complex

S(M, e) = {F ⊆ E − {e}: P ⊈ F, ∀P ∈ P} Generalizes matroids: S(M × e, e) = IN(M), where × denotes free coextension

DUALITY, etc.

Steiner complexes closed under deletion, contraction, Alexander duality:

S(M, e) − f = S(M − f, e)
S(M, e)/f = S(M/f, e)
S(M, e)^{∨} = S(M^{∗}, e)

P and P^{∗} are blocking clutters; each clutter (anti-chain) is minimal for intersecting each of the sets in the other clutter.

P(M^{∗}, e) = P^{∗}(M, e)

Conjecture: Steiner complexes are Laplacian integral and spectral.