1956/01/01 by Péter L. Erdős, R. Rado · 439 citations
Mathematics · Computer Science · Medicine · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #Mathematical and Theoretical Analysis #Calculus (dental) #Mathematics #Partition (number theory) #Set (abstract data type) #Computer science #Combinatorics #Medicine
paper · pdf · doi:10.1090/s0002-9904-1956-10036-0
published in Bulletin of the American Mathematical Society 62(5), 427-489 (American Mathematical Society)
openalex publication_date 1956/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/07
Introduction. Dedekind's pigeon-hole principle, also known as the box argument or the chest of drawers argument (Schubfachprinzip) can be described, rather vaguely, as follows. If sufficiently many objects are distributed over not too many classes, then at least one class contains many of these objects. In 1930 F. P. Ramsey [12] discovered a remarkable extension of this principle which, in its simplest form, can be stated as follows. Let S be the set of all positive integers and suppose that all unordered pairs of distinct elements of S are distributed over two classes. Then there exists an infinite subset A of S such that all pairs of elements of A belong to the same class. As is well known, Dedekind's principle is the central step in many investigations. Similarly, Ramsey's theorem has proved itself a useful and versatile tool in mathematical arguments of most diverse character. The object of the present paper is to investigate a number of analogues and extensions of Ramsey's theorem. We shall replace the sets S and A by sets of a more general kind and the unordered pairs, as is the case already in the theorem proved by Ramsey, by systems of any fixed number r of elements of S. Instead of an unordered set S we consider an ordered set of a given order type, and we stipulate that the set A is to be of a prescribed order type. Instead of two classes we admit any finite or infinite number of classes. Further extension will be explained in 2, 8 and 9.