Topological Properties of Activity Orders for Matroids

Rieuwert J. Blok Dipartimento di Matematica Università degli studi di Roma “Tor Vergata” Via della ricerca scientifica 00133 Roma, ITALY blokr@member.ams.org and Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027, USA sagan@math.msu.edu www.math.msu.edu/˜ sagan

0. Origin of the Problem

1. Matroids and the External Order

2. The Order Complex

3. The Main Theorem

4. Applications

5. An Open Problem 1. Matroids and the External Order

Let M be a matroid on a finite set E and let

B(M) = {B ⊆ E | B is a base of M }.

Ex. 1. The vector matroid M = (V, +, ·,) has E = V, a finite dimensional vector space over a finite field, and

B(V) = {B| B is a basis of V }.

2. The graph matroid M = G where G is a connected graph has E = E(G) (edges of G) and

B(G) = {E(T) | T is a spanning tree of G }.

Here we will make no distinction between F ⊆ E and the spanning graph of G with edge set F.

The independent sets of M are

I(M) = {I | I ⊆ B for some base B }.

The circuits of M are

C(M) = {C | C a minimal dependent set }.

If M = G then a circuit of M is just a cycle in G.

From now on all matroids will be ordered, i.e., there will be a total order on E. Then F ⊆ E has external active set

Act (F) = {e ∈ E | e = min C where C ∈ C(F ∪ e) }.

[figure: Ex. Let G =; 0; 1; 2; 3; 4; and F =; 0; 3; 4]

Then Act (F) = {1}.

The external lattice of the ordered matroid M is

L(M) = B(M) ⊎ ˆ0

where ˆ0 is a unique minimal element and for bases A, B ∈ B(M)

A ≤ B iff A ⊆ B ∪ Act (B).

Theorem 1 (Las Vergnas) L(M) is a lattice with unique maximal element T which is the lexicographically largest base (writing sets in increasing order). L(M) is also ranked with rank function

ρ(B) = | Act (B)| + 1.

[figure: G =; 0; 1; 2; 3; 4] [figure: L(G) =; 2; 3; 4; 1; 2; 3; 1; 2; 4; 0; 3; 4; 0; 1; 2; 0; 1; 3; 0; 1; 4; 0; 2; 4; ˆ0]

4

2. The Order Complex

An abstract simplicial complex is a finite family Δ of finite nonempty sets called simplices such that

S ∈ Δ and R ⊆ S (R ≠ ∅) implies R ∈ Δ.

Let P be any finite poset with a unique minimal element ˆ0 and unique maximal element ˆ1. The order complex of P is

Δ(P) = {C | C is a chain in P \ ˆ0, ˆ1 }.

Note that this is an abstract simplicial complex since a subset of a chain is again a chain.

We have the correspondences

P  Δ(P)
1-chain vertex
2-chain edge
3-chain triangle
k-chain simplex of dimension k − 1

If M is an ordered matroid then Δ(M) = Δ(L(M)).

[figure: Δ(G) =; 0; 1; 3; 1; 2; 3; 0; 3; 4; 0; 1; 2; 0; 1; 4; 1; 2; 4; 0; 2; 4]

6

3. The Main Theorem

If M is a matroid on E then the dual of M is the matroid M^{∗} defined by

B(M^{∗}) = {B^{∗} | B^{∗} = E − B for some B ∈ B(M) }.

Ex. For our example graph E(G) = {0, 1, 2, 3, 4} so

\begin{aligned}B(M) & = & \{012, 013, 014, 024, 123, 124, 034, 234\} \\ B(M^{∗}) & = & \{34, 24, 23, 13, 04, 03, 12, 01\} \end{aligned}

If M is a matroid on E and F ⊆ E then the restriction of M to F is the matroid M|F defined by

B(M|F) = {B ∩ F | B ∈ B(M) and |B ∩ F | maximum }.

Ex. (cont) Let F = T = 234 = ˆ1 in L(G)

B(M^{∗}|T) = {34, 24, 23}.

If M is a matroid then the matroid complex [M] is the abstract simplicial complex whose simplices are the nonempty independent sets of M.

Ex. (cont) We have a homotopy equivalence

[M^{∗}|T] = {34, 24, 23, 2, 3, 4} ≃ S^{1} (a 1-sphere)

Theorem 2 (B & S) If T = ˆ1 in L(M) then

Δ(M) ≃ [M^{∗}|T].

4. Applications Denote the Möbius function of L(M) by

μ(M) := μ_{L(M)}(ˆ0, T).

So μ(M) is the reduced Euler characteristic of Δ(M)

μ(M) = _{i≥−1}^{∑}(−1)^{i} dim H̃_{i}(Δ(M)).

The rank of M is rk(M) := |B| for any B ∈ B(M). Corollary 3 (B & S) Let rk(M) = r > 1.

(i) If there is B ∈ B(M) with B ⊆ E − T, then H̃_{i}(M) = {0} for all i ≥ 0 and μ(M) = 0.

(ii) If E − S contains a base of M for all S ⊂ T but not for S = T, then

H̃_{i}(M) = \{ \begin{matrix}ℤ & if i = r − 2, \\ \{0\} & else, \end{matrix} and μ(M) = (−1)^{r−2}.

Proof (i) By definition E − B ∈ B(M^{∗}) and we’re given E − B ⊇ T. So Δ(M) ≃ [M^{∗}|T] ≃ (r − 1)-ball and we are done. (ii) Similarly Δ(M) ≃ [M^{∗}|T] ≃ (r −2)-sphere.

A star is a complete bipartite graph of the form K_{1,n}.

Corollary 4 (B & S) Consider a matroid obtained by ordering the edges of the complete graph K_{r}, r > 2.

(i) If T is not a star then then μ(K_{r}) = 0.

(ii) If T is a star then μ(K_{r}) = (−1)^{r−3}.

Proof (i) If T is not a star, then K_{r} − E(T) is connected. So K_{r} − E(T) contains a spanning tree and thus a base for K_{r}. Now use the previous corollary. (ii) is similar.

Note that Δ(M) is not necessarily shellable: Take an ordering of E(K_{r}) so that the r − 1 largest edges all meet at a vertex v. So every edge of E − T is active and

dim Δ(K_{r}) = ρ(L(K_{r}))−2 = | Act (T)|−1 = \binom{r − 1}{2}−1.

But from Corollary 4, Δ(K_{r}) has non-zero homology in dimension r − 3.

Theorem 5 (Björner) The complex [M] is shellable for any matroid M.

5. An Open Problem

Las Vergnas also defined an internal order ≤_{I} on M in a way equivalent to defining

A ≤_{I} B iff E − B ≤ E − A in L(M^{∗}).

If L_{I}(M) is the resulting lattice, then it is isomporphic to the poset dual of L(M^{∗}) and so has the same homology and Möbius function.

One can combine the external and internal orders as follows. Define the internal-external order ≤_{IO} on B(M) by

A ≤_{IO} B iff A ≤ B or A ≤_{I} B .

It follows from results of Las Vergnas that this is a well-defined partial order.

Question 6 What can be said about the homology and Möbius function of the corresponding poset L_{IO}(M)?