Matroid Steiner complexes are Laplacian integral

AMS Regional Meeting

Bard College Oct., ’05 Matroid Steiner complexes are Laplacian

integral

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 and Federico Ardila say: Steiner complexes generalize matroids, and are closed under Alexander duality.

Theorem: Laplacian eigenvalues of Steiner complexes are integral…

Conjecture:… 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_{Δ} (t, q) := _{i}^{∑} t^{i} _{λ∈s(L_{i−1}(Δ))}^{∑} q^{λ}

Tutte polyn. deletion-contraction recursion: T_{M} = T_{M−e} + T_{M/e}

[figure]
B(M − e) = {B ∈ B: e ∉ B}
B(M/e) = {B − e: B ∈ B, e ∈ B}

Spectral recursion:

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

• Matroids: Kook ’04 (w/different error term); D ’05

• Shifted complexes: D ’05

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 (D ’05): Δ 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 (char’n of Chari ’93)

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)

From original defn (Colbourn-Pulleyblank ’89), 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)

Thm: Steiner complexes are Laplacian integral …

Conj:… and satisfy spectral recursion.

RELATIVE PAIRS

Thm (D ’05): Relative pairs of shifted complexes (Δ′ ⊆ Δ, both shifted on same underlying vertex order) satisfy

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

where Φ = Δ − Δ′, for suitable Φ ∥ e.

What about matroids? (M −e, M/e) is integral, with a nice formula for eigenvalues; Vic Reiner suggests looking at (N, N′), where N → N′ is a strong map. Perhaps even more generally (and vaguely) (S, S′) where S′ ⊆ S are both Steiner complexes on same underlying matroid.