Computing the rank partition and the flag transversal of a matroid
type: Item
instance of: scholarly article
title: Computing the rank partition and the flag transversal of a matroid
zbMATH Open document ID: 0951.05019
DOI: 10.1016/S0012-365X(99)00297-6
author: J. A. Dias Da Silva
author: Amélia Fonseca
published in: Discrete Mathematics
publication date: 2000-12-11T00:00:00Z
review text: 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.
reviewed by: Ferenc Fodor
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 1455603
zbMATH Keywords: flag transversal
zbMATH Keywords: matroid
zbMATH Keywords: rank partition
zbMATH Keywords: \(k\)-transversal
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00297-6
OpenAlex ID: W2058123292
description: scientific article; zbMATH DE number 1455603