Ramsey theory

The Ramsey ( according to Frank Plumpton Ramsey ) is a branch of combinatorics within discrete mathematics. It deals with the question of how many elements from a provided with a certain amount of structure must be chosen so that this structure can be found in the subset and a certain property is satisfied. Famous sets of Ramsey have it all together this property.

Examples

As a simple example is the pigeonhole principle. This means that at least one of the drawers drawers containing at least two objects when distributing objects.

In another example, meet 6 people. The two are either friends with each other or not friends. Then there are ( stets! ) a group of three who each friend each other or are not friends.

Formulation of the solution as a graph problem

Be a graph with nodes (for the people) and red edges for friends or gray edges for non- friends. We consider a person. This has always at least three friends or non - friends ( Fig. 1). Would now two of the three identical terminal nodes ( red in the picture linked ) linked to a further red edge, so we already have a group of three who are all friends with each other (or not ). On the other hand, if all three end nodes connected to three gray edges, so we had again a group of three, all without befriends ( friends ) are.

In this example, pairs are from a sechselementigen amount into two disjoint classes classified (friends and non- friends). No matter what the assignment looks like, there is a homogeneous group of three.

Another example is Sim

Famous sets of Ramsey

• The pigeonhole principle makes statements about the number of objects contained in drawers and is the starting point of the Ramsey theory.
• The classical theorem of Ramsey examines how large a graph must be so for a coloring always a clique in the corresponding color and size exists. Infinite versions of this play set in abstract set theory a role, see Ramsey's theorem ( set theory ).
• The set of Van der Waerden investigated the minimum size of a lot, so that under a coloring of this set to always find a monochromatic arithmetic progression of certain length.
• The dyeing of levels, more specifically, the coloring of the plane has become known as the set of Schur.