Transversals and Matroids
Peter Horák · 1990
The first application of matroids in transversal theory goes back to the early forties and since then they have played the essential role in this area. As a matter of fact, there are two fundamental results concerning both transversals and matroids. In [9] Rado established a necessary and sufficient condition for a finite family of sets to possess a transversal which is independent in a given matroid. The second result, stated by Edmonds and Fulkerson [3], says that the partial transversals of a finite family of sets form a matroid. The two theorems lie at the very heart of transversal theory and therefore there are many variations and generalizations of them. A comprehensive survey of this field is in [7], for later ones see e.g. [10]. Yet, the generalizations of these classical results seem to go in different directions. In this paper it is shown that by means of k-transversals, introduced by Asratian [1] and originally called compatible transversals, it is possible to obtain “parallel” generalization of them.