##
**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