Defining matroids through sequential selection
Let \(E\) be a finite set and \(\mathcal{S}\) a collection of subsets of \(E\). A set \(I\subseteq E\) is a sequential transversal of \(\mathcal{S}\) if either \(I\) is empty, or there is an element \(x\) in some set of \(\mathcal{S}\) where no other element of \(I\) is represented and such that \(I \setminus \{x\}\) is also a sequential transversal. Every sequential transversal is a partial transversal, but not conversely. Since partial transversals are the independent sets of a matroid on \(E\), a natural question to ask is whether or not sequential transversals also define a matroid on \(E\). The authors show that this is indeed the case if and only if the set of all sequential transversals, \(\mathcal{T}_{\mathcal{S}}\), of \(\mathcal{S}\) coincides with the set of all sequential transversals of the blocker of the maximal sets of \(\mathcal{T}_{\mathcal{S}}\). It is also shown that every matroid on \(E\) can be defined as a pair \((E, \mathcal{T}_{\mathcal{S}})\), where \(\mathcal{T}_{\mathcal{S}}\) is order-independent. For a cyclically 4-edge connected planar graph \(G\) and \(\mathcal{S}\) the collection of 3-circuits of \(G\), \((E(G), \mathcal{T}_{\mathcal{S}})\) is a matroid, but fails to be one if \(G\) is only required to be planar and 3-connected. Several other examples are provided.
- A simple approach to some basic results in matroid theory
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- Transversals and matroid partition
This page was built for publication: Defining matroids through sequential selection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q854847)
