Computing the rank partition and the flag transversal of a matroid (Q1567267): Difference between revisions

Let \(M\) be a matroid on a set \(S\) of cardinality \(m\). The set \(\{ I_1\cup I_2\cup\dots\cup I_k : I_i\) is an independent set in \(M\), \(i=1,\dots , k\}\) of subsets of \(S\) is the set of independent sets of a matroid called the \(k\)th power of \(M\). The rank of this matroid is denoted by \(\rho _k\). By convention \(\rho _0=0\). It is well known that if \(M\) has no loops, then the sequence \(\rho (M)=(\rho _1-\rho _0,\dots , \rho _m-\rho _{m-1})\) is a partition of \(m\) called the rank partition of \(M\). The authors give two procedures which can compute the rank partition of a matroid based only on the knowledge of the values of the rank function. We say that \(T\subseteq S\) is a \(k\)-transversal of \(M\) if \(T\) is the disjoint union of \(k\) bases of the restriction of \(M\) to \(T\). The maximal \(k\)-transversals have the same closure and this closure contains the closure of the maximal \((k+1)\)-transversal. The flag transversal is defined to be the greatest strictly increasing chain whose terms are closures of maximal \(k\)-transversals for some \(k\). The authors show that one of the provided procedures makes it possible to determine the flag transversal of a matroid.