Topological properties of activity orders for matroid bases

Abstract: Las Vergnas introduced several lattice structures on the bases of an ordered matroid M by using their external and internal activities. He also noted that when computing the Moebius function of these lattices, it was often zero, although he had no explanation for that fact. The purpose of this paper is to provide a topological reason for this phenomenon. In particular, we show that the order complex of the external lattice L of M is homotopic to the independence complex of the restriction M^*|T where M^* is the dual of M and T is the top element of L. We then compute some examples showing that this latter complex is often contractible which forces all its homology groups, and thus its Moebius function, to vanish. A theorem of Bj"orner also helps us to calculate the homology of the matroid complex.

Review text

Las Vergnas introduced several lattice structures on the bases of an ordered matroid \(M\) by using their external and internal activities: Let \(M\) be a matroid on a finite linearly ordered set \(E\). Given a set \(F \subseteq E\), we say \(e\in E\) is active with respect to \(F\) if there is a circuit in \(F \cup \{e\}\) in which \(e\) is minimal with respect to the ordering on \(E\). Let \(\text{Act}_M(F) =\{e: e\) is active with respect to \(F\}\). The elements of the set \(\text{Ext}_M(F) = \text{Act}_M(F) -F\) are called externally active with respect to \(F\). Las Vergnas defined the external lattice of \(M\) via \(A \leq^{\text{ext}}_M B\) if and only if \(A \subseteq B \cup \text{Ext}_M(B)\). When augmented with a minimum element, the resulting order is in fact a graded lattice with rank function \(\rho_M(B) = | \text{Ext}_M(B)| +1\). This lattice is denoted \(L(M)\). Using the dual matroid \(M^*\), Las Vergnas also defined an internal order. The paper under review studies the Möbius function of these lattices. In particular, this paper provides a topolgical reason for the Möbius function to often be zero. The order complex of the external lattice \(L(M)\) is homotopic to the independence complex of the restriction \(M^*| T\) where \(M^*\) is the dual of \(M\) and \(T\) is the top element of \(L(M)\). This latter complex is often contractible, forcing the Möbius function to vanish. A theorem of Björner is used in calculating the homology of the matroid complex. Open problems are also discussed.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Topological properties of activity orders for matroid bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1775895)