Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Matching theory for combinatorial geometries


Authors: Martin Aigner and Thomas A. Dowling
Journal: Trans. Amer. Math. Soc. 158 (1971), 231-245
MSC: Primary 05.27
DOI: https://doi.org/10.1090/S0002-9947-1971-0286689-5
MathSciNet review: 0286689
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given two combinatorial (pre-) geometries and an arbitrary binary relation between their point sets, a matching is a subrelation which defines a bijection between independent sets of the geometries. The theory of matchings of maximum cardinality is developed in two directions, one of an algorithmic, the other of a structural nature. In the first part, the concept of an augmenting chain is introduced to establish as principal results a min-max type theorem and a generalized Marriage Theorem. In the second part, Ore's notion of a deficiency function for bipartite graphs is extended to determine the structure of the set of critical sets, i.e. those with maximum deficiency. The two parts of the investigation are then connected using the theory of Galois connections.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05.27

Retrieve articles in all journals with MSC: 05.27


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1971-0286689-5
Keywords: Combinatorial geometry, matroid, geometric relation, matching, augmenting chain, König-Egerváry theorem, Marriage Theorem, deficiency function, geometric lattice, Galois connection, distributive lattice
Article copyright: © Copyright 1971 American Mathematical Society

American Mathematical Society