×

Defining matroids through sequential selection. (English) Zbl 1118.05010

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.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
05D15 Transversal (matching) theory
Full Text: DOI

References:

[1] Bollobás, B., Modern Graph Theory (1998), Springer: Springer New York · Zbl 0902.05016
[2] T. Brylawski, Private communication, 2002; T. Brylawski, Private communication, 2002
[3] Dawson, J. E., A simple approach to some basic results in matroid theory, J. Math. Anal. Appl., 84, 555-559 (1981) · Zbl 0479.05021
[4] Edmonds, J.; Fulkerson, D. R., Transversals and matroid partition, J. Nat. Bureau Stand. B, 69, 147-153 (1965) · Zbl 0141.21801
[5] S. Jones, Operations on graphs and matroids, Masters Thesis, The University of Montana, 2002; S. Jones, Operations on graphs and matroids, Masters Thesis, The University of Montana, 2002
[6] Oxley, J., Matroid Theory (1992), Oxford Press · Zbl 0784.05002
[7] Welsh, D., Matroid Theory (1976), Academic Press · Zbl 0343.05002
[8] West, D. B., Introduction to Graph Theory (2001), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.