Ramsey theory

The Ramsey theory (after Frank Plumpton Ramsey ) is a branch of combinatorics within discrete mathematics . It deals with the question of how many elements must be selected from a set with a certain structure so that this structure can be found in the subset and a certain property is fulfilled. Famous sentences of the Ramsey theory all have this property in common.

Examples

The drawer principle is a simple example . This means that when objects are distributed on drawers, at least one of the drawers contains at least two objects. ${\ displaystyle k + 1}$ ${\ displaystyle k}$

In another example, 6 people meet. Each two are either friends with each other or not. Then there is (always!) Either a group of three, in which everyone is friends, or a group of three, in which there are no friendships at all.

Formulation of the solution as a graph problem

Fig. 1

Let be a graph with nodes (for the people) and red edges for friends and gray edges for non-friends. We are looking at a person . This always has at least three friends or not-friends ( Fig. 1 ). If two of the three end nodes of the same type (connected in red in the picture) were linked with another red edge, we already have a group of three that are all friends (or not) with each other. If, on the other hand, all three end nodes were connected with three gray edges, we would again have a group of three who are all unfriended (friends). ${\ displaystyle {\ mathcal {G}} = (V, E)}$ ${\ displaystyle n = 6}$ ${\ displaystyle A}$

In this example, pairs from a set with alternating elements are classified into two disjoint classes (friends and not friends). No matter what the assignment looks like, there is a homogeneous group of three.

Another example is Sim .

Famous sentences of the Ramsey theory

The drawer principle makes statements about the number of objects in drawers and is the starting point of the Ramsey theory.

Ramsey's classical theorem examines how big a graph has to be so that there is always a clique of a corresponding color and size for one color . Infinite versions of this theorem play a role in abstract set theory, see Ramsey theorem (set theory) .

The rate of Van der Waerden examined the minimum size of a lot , so that under a color that quantity is always a monochromatic arithmetic progression is to find a certain length. ${\ displaystyle \ {1, \ cdots, n \}}$

The coloring of planes, more precisely, the coloring of planes has become known under the Schur theorem. ${\ displaystyle x + y = z}$

literature

Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer: Ramsey Theory . 2nd Edition. Wiley, New York, NY, 1990, ISBN 0-471-50046-1
Bruce M. Landman, Aaron Robertson: Ramsey Theory on the Integers . 1st edition. AMS, Rhode Island, 2004, ISBN 0-8218-3199-2
Richard Rado: Studies on Combinatorics . Dissertation, Berlin 1933