Computing the rank partition and the flag transversal of a matroid (Q1567267)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing the rank partition and the flag transversal of a matroid |
scientific article |
Statements
Computing the rank partition and the flag transversal of a matroid (English)
0 references
11 December 2000
0 references
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.
0 references
flag transversal
0 references
matroid
0 references
rank partition
0 references
\(k\)-transversal
0 references