1990 | OriginalPaper | Buchkapitel
Transversals and Matroids
verfasst von : P. Horák
Erschienen in: Topics in Combinatorics and Graph Theory
Verlag: Physica-Verlag HD
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.