Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 715.05052
Autor: Erdös, Paul; Hajnal, András
Title: Ramsey-type theorems. (In English)
Source: Discrete Appl. Math. 25, No. ½, 37-52 (1989).
Review: From the authors' abstract: ``In this paper we will consider Ramsey-type problems for finite graphs, r-partitions and hypergraphs. All these problems ask for the existence of large homogeneous (monochromatic) configurations of a certain kind under the condition that the size of the underlying set is large. As it is quite common in Ramsey theory, most of four results are not sharp and almost all of them lead to new problems which seem to be difficult. The problems we treat are only loosely connected. So we will state and explain them section by section.''
Typical of the results in this paper is the following: Theorem 1.1. Assume \ell in N, 0 < c < 1/\ell. Then there is an n0 = n0(\ell,c) such that for all n > n0, G in In and k < ec\sqrt{log n/2} either G contains a homogeneous subset of size k or G is \ell-universal.
Here In is the class of all graphs with n vertices, a homogeneous subset is a set of pairwise adjacent or pairwise non-adjacent vertices, and G is \ell-universal if G contains, as an induced subgraph, a copy of each graph in I\ell.
Reviewer: J.E.Graver
Classif.: * 05C55 Generalized Ramsey theory
05A17 Partitions of integres (combinatorics)
05C65 Hypergraphs
Keywords: Ramsey-type problems; finite graphs; r-partitions; hypergraphs
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag