## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  761.04003
Autor:  Erdös, Paul; Larson, Jean A.
Title:  Matchings from a set below to a set above. (In English)
Source:  Discrete Math. 95, No.1-3, 169-182 (1991).
Review:  One way to represent a matching in a graph of a set A with a set B is with a one-to-one function m: A ––> B for which each pair {a,m(a)} is an edge of the graph. If the underlying set of vertices of the graph is linearly ordered and every element of A is less than every element of B, then such a matching is a down-up matching. In this paper we investigate graphs on well-ordered sets of type \alpha and in many circumstances find either large independent sets of type \beta or down- up matchings with the initial set of some prescribed size \gamma. In this case we write \alpha ––> (\beta,\gamma-matching).
Classif.:  * 04A20 Combinatorial set theory
05C70 Factorization, etc.
Keywords:  partition relation; bipartite graph; graphs on well-ordered sets; large independent sets; down-up matchings

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag