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