Defining matroids through sequential selection (Q854847): Difference between revisions

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.