Theorem on friends and strangers

Theorem on friends and strangers For the friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós characterizing graphs in which each two vertices have exactly one neighbor, see friendship graph. 78 of the 156 possible friends-strangers graphs with 6 nodes. The other 78 can be obtained by reversing the red and blue colours of each graph. For each graph the red/blue nodes shows a sample triplet of mutual friends/strangers.

The theorem on friends and strangers is a mathematical theorem in an area of mathematics called Ramsey theory.

Contents 1 Statement 2 Conversion to a graph-theoretic setting 3 Sketch of a proof 4 Ramsey's paper 5 Boundaries to the theorem 6 References 7 External links Statement Suppose a party has six people. Consider any two of them. They might be meeting for the first time—in which case we will call them mutual strangers; or they might have met before—in which case we will call them mutual acquaintances. The theorem says: In any party of six people either at least three of them are (pairwise) mutual strangers or at least three of them are (pairwise) mutual acquaintances. Conversion to a graph-theoretic setting A proof of the theorem requires nothing but a three-step logic. It is convenient to phrase the problem in graph-theoretic language.

Suppose a graph has 6 vertices and every pair of (distinct) vertices is joined by an edge. Such a graph is called a complete graph (because there cannot be any more edges). A complete graph on {displaystyle n} vertices is denoted by the symbol {displaystyle K_{n}} .

Now take a {displaystyle K_{6}} . It has 15 edges in all. Let the 6 vertices stand for the 6 people in our party. Let the edges be coloured red or blue depending on whether the two people represented by the vertices connected by the edge are mutual strangers or mutual acquaintances, respectively. The theorem now asserts: No matter how you colour the 15 edges of a {displaystyle K_{6}} with red and blue, you cannot avoid having either a red triangle—that is, a triangle all of whose three sides are red, representing three pairs of mutual strangers—or a blue triangle, representing three pairs of mutual acquaintances. In other words, whatever colours you use, there will always be at least one monochromatic triangle ( that is, a triangle all of whose edges have the same color ). Sketch of a proof Choose any one vertex; call it P. There are five edges leaving P. They are each coloured red or blue. The pigeonhole principle says that at least three of them must be of the same colour; for if there are less than three of one colour, say red, then there are at least three that are blue.

Let A, B, C be the other ends of these three edges, all of the same colour, say blue. If any one of AB, BC, CA is blue, then that edge together with the two edges from P to the edge's endpoints forms a blue triangle. If none of AB, BC, CA is blue, then all three edges are red and we have a red triangle, namely, ABC.

Ramsey's paper The utter simplicity of this argument, which so powerfully produces a very interesting conclusion, is what makes the theorem appealing. In 1930, in a paper entitled 'On a Problem in Formal Logic,' Frank P. Ramsey proved a very general theorem (now known as Ramsey's theorem) of which this theorem is a simple case. This theorem of Ramsey forms the foundation of the area known as Ramsey theory in combinatorics.

Boundaries to the theorem A 2-colouring of K5 with no monochromatic K3 The conclusion to the theorem does not hold if we replace the party of six people by a party of less than six. To show this, we give a coloring of K5 with red and blue that does not contain a triangle with all edges the same color. We draw K5 as a pentagon surrounding a star (a pentagram). We color the edges of the pentagon red and the edges of the star blue. Thus, 6 is the smallest number for which we can claim the conclusion of the theorem. In Ramsey theory, we write this fact as: {displaystyle R(3,3:2)=6.} References V. Krishnamurthy. Culture, Excitement and Relevance of Mathematics, Wiley Eastern, 1990. ISBN 81-224-0272-0. External links Party Acquaintances at cut-the-knot (requires Java) Categories: Ramsey theoryTheorems in discrete mathematics

Si quieres conocer otros artículos parecidos a Theorem on friends and strangers puedes visitar la categoría Ramsey theory.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.


Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información