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.

**[1]**Martin Aigner and Thomas A. Dowling,*Matching theorems for combinatorial geometries*, Bull. Amer. Math. Soc.**76**(1970), 57–60. MR**0276116**, https://doi.org/10.1090/S0002-9904-1970-12365-5**[2]**Claude Berge,*Théorie des graphes et ses applications*, Collection Universitaire de Mathématiques, II, Dunod, Paris, 1958 (French). MR**0102822****[3]**G. Birkhoff,*Lattice theory*, Amer. Math. Soc. Colloq. Publ., vol. 25, Amer. Math. Soc., Providence, R. I., 1940; rev. ed., 1948, 1967. MR**1**, 325; MR**10**, 673.**[4]**Henry H. Crapo and Gian-Carlo Rota,*On the foundations of combinatorial theory: Combinatorial geometries*, Preliminary edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. MR**0290980****[5]**Jack Edmonds,*Submodular functions, matroids, and certain polyhedra*, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 69–87. MR**0270945****[6]**L. Mirsky and Hazel Perfect,*Applications of the notion of independence to problems of combinatorial analysis*, J. Combinatorial Theory**2**(1967), 327–357. MR**0225675****[7]**Oystein Ore,*Galois connexions*, Trans. Amer. Math. Soc.**55**(1944), 493–513. MR**0010555**, https://doi.org/10.1090/S0002-9947-1944-0010555-7**[8]**Oystein Ore,*Graphs and matching theorems*, Duke Math. J.**22**(1955), 625–639. MR**0073171****[9]**R. Rado,*A theorem on independence relations*, Quart. J. Math., Oxford Ser.**13**(1942), 83–89. MR**0008250**

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