Ramsey's theorem

Ramsey's theorem (after Frank Plumpton Ramsey ) answered the question of whether absolutely certain substructures occur in a graph. More colored complete graphs are considered on the occurrence of monochromatic subgraphs down, and it turns out that such must actually occur for sufficiently large graphs. A practical application is the game Sim

Considerably more difficult than the pure existential statement is made ​​accurate quantification, which is regarded here as a "sufficiently large" to, ie the exact calculation, or at least estimate the Ramsey numbers.

Statement of the theorem

We consider a complete graph with vertices, the edges of which were with two colors, such as red and blue colored. Is there herein corners so that all edges between them are red, we say that the graph contains a red subgraph corresponding to blue subgraphs. With this notation, the set of Ramsey claims:

Be natural numbers. Every sufficiently large complete graph whose edges were colored red or blue, contains a red subgraph or a blue - subgraphs. " Sufficiently large" here means for a number of and dependent. The smallest number that can be selected for, and is Ramsey number is designated. Conversely, it is possible to color the complete graph with vertices so that it produces neither a red nor a blue - subgraph - subgraph.

The theorem also holds in generalized form for more than two colors. Accordingly, there are also dyes with colors corresponding Ramsey numbers.

Examples

• In general, as can be seen by swapping the colors.
• : Each subgraph with only one corner is automatically monochrome.
• Either all edges are red or there is a blue edge.

Calculation of

The picture shows that it is possible to so, as red and blue to color the complete graph with five vertices with two colors that neither a red nor a blue triangle appears. Consequently certainly applies: or.

Looking the other way around in any way a red - and blue-colored herein to any corner, as occurs in the five edges in ending one of the two colors, without loss of generality. red, at least three times ( pigeonhole principle ). If one of the edges between the three corresponding endpoints red, so we have a red one. Otherwise, all edges are blue between these three endpoints, and we have a blue one. So in every red-blue- colored one finds a red or a blue, ie, we have: .

Overall, we obtain so.

The considerations made ​​here already show essential thoughts for a proof of the theorem and a simple recursive estimation for Ramsey numbers, but not sufficient for an accurate determination of the Ramsey numbers:

A lower bound for the Ramsey numbers are obtained with the probabilistic method, as is true of

Illustration

The Ramsey number answers the question of how many people you have to invite to a party, for example, so that guests do not know each or guests know each other. " Know " in this example is a symmetric relation, ie, if person A knows person B, then B also knows A.

Consider, for example. With and follows (see above).

Thus if we have guests, so we can now draw the complete graph and start dyeing. You need every edge color either red or blue (red: guests do not know one, blue: guests know each other ) and reached the following possible colorings:

• All edges are colored red.
• All edges are colored blue.
• Two edges are colored blue and red.
• Two edges are colored red and blue.

For the three guests, this means:

• No one knows another.
• All three know each other.
• A person knows two people who do not know each other.
• Two people know each other, but not the third person.

This description is merely illustrative. The analogy to the guests treated not problems that strange " Know Yourself ( - not ) " relationships have ( everyone seems to know not two know each other, but who is the third ) also is not considered that any person A person B knows, but person B person A does not know. In addition, no transitive relationships are represented.