A Ramsey theoretic problem for finite ordered sets

✍ Scribed by H.A. Kierstead; W.T. Trotter

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 467 KB
• Volume: 63
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90009-4

✦ Synopsis

In this paper, we consider the following Ramsey theoretic problem for finite ordered sets:

For each II 3 1, what is the least integer f(n) so that for every ordered set P of width it, there exists an ordered set Q of width f(n) such that every 2-coloring of the points of Q produces a monochromatic copy of P?

Before presenting our results on this problem, we pause to introduce some basic notation and terminology and to make some observations concerning the background of this problem. Throughout the paper, we consider only finite ordered sets. If P is an ordered set and X, y E P, we write x 11 y when x and y are incomparable. For a positive integer r, we let r = { 1, 2, . . . , r}.

An r-coloring of an ordered set Q is a mapping C$ : Q -+ r of the points of Q to a set of r elements. In this setting, the elements of r are called colors. When @ is an r-coloring of Q and cx E r, a subordered set P of Q such that $(x) = LY for every x E P is called a monochromatic subordered set (of color (u). In this paper, we are primarily interested in the case r = 2.

Accordingly, we write Q* P when every 2-coloring of Q produces a monochromatic copy of P, i.e., for every 2-coloring @ : Q + 2, there exists an LY E 2 and a monochromatic subordered set P' of color (Y so that P' is isomorphic to P. To indicate that the statement that Q+ P is false, we will write Q-,4= P. Lemma 1. For every ordered set P, there exists an ordered set Q so that Q + P.