Théorème des amis et des étrangers

Supposons qu'une fête comporte six invités. Considérons deux d'entre eux. Ils pourraient se rencontrer pour la première fois—dans ce cas, nous allons les appeler des étrangers ou inconnus ; ou ils pourraient s'être rencontrés auparavant—dans ce cas, nous allons les appeler des connaissances mutuelles ou amis. Le théorème dit :

Dans toute fête de six personnes, soit au moins trois d'entre eux sont (par paires) mutuellement des étrangers, soit au moins trois d'entre eux sont (par paires) mutuellement des amis.

Une démonstration du théorème exige seulement un raisonnement logique en trois étapes. Il est commode de formuler le problème dans le langage de la théorie des graphes.

Supposons qu'un graphe simple a 6 sommets et que chaque paire de sommets (distincts) est jointe par une arête. Un tel graphe est appelé graphe complet (car il ne peut y avoir plus d'arêtes). Un graphe complet sur ${\displaystyle n}$ sommets est notée par le symbole ${\displaystyle K_{n}}$.

Maintenant, prenez le graphe ${\displaystyle K_{6}}$. Il a 15 arêtes en tout. Les 6 sommets correspondent aux 6 personnes de la fête. On choisit que les arêtes seront de couleur rouge ou bleu selon que les deux personnes représentées par les sommets reliés par l'arête commune, sont des étrangers ou des connaissances, respectivement. Le théorème affirme :

Peu importe comment vous coloriez les 15 arêtes d'un ${\displaystyle K_{6}}$ en rouge et bleu, vous ne pouvez pas éviter d'avoir soit un triangle rouge, un triangle dont les trois côtés sont de couleur rouge, ce qui représente trois paires d'étrangers mutuels—ou un triangle bleu, représentant les trois paires de connaissances mutuelles. En d'autres termes, quelles que soient les couleurs que vous utilisez, il y aura toujours au moins un triangle monochromatique (c'est un triangle dont tous les côtés ont la même couleur).

Choisissez un sommet quelconque ; appelons-le P. Il y a cinq arêtes issues de P. Elles sont de couleur rouge ou bleu. Le principe des tiroirs dit qu'au moins trois d'entre eux doivent être de la même couleur ; car s'il y a moins de trois d'une couleur, disons rouge, alors il y en a au moins trois qui sont en bleu.

Soient A, B, C les autres extrémités de ces trois arêtes, toutes de la même couleur, disons bleu. Si parmi AB, BC, CA, l'une est bleue, alors cette arête avec les deux arêtes joignant P aux extrémités de cette arête forme un triangle bleu. Si aucune parmi AB, BC, CA n'est bleue, alors les trois arêtes sont rouges et nous avons un triangle rouge, à savoir, ABC.

En fait, on peut trouver deux triangles monochromes.

L'extrême simplicité de cet argument, qui a si puissamment produit une conclusion très intéressante, est ce qui rend le théorème attrayant. En 1930, dans un article intitulé Sur un problème de logique formelle (On a Problem in Formal Logic), Frank Ramsey a prouvé un théorème très général (maintenant connu comme le théorème de Ramsey) dont ce théorème est un cas simple. Ce théorème de Ramsey est à la base du domaine connu sous le nom de théorie de Ramsey dans le domaine de la combinatoire.

Une 2-coloration K₅ sans monochromatique K₃

La conclusion du théorème ne tient pas si l'on remplace la fête de six personnes par une fête de moins de six. Pour l'illustrer, nous donner une coloration de ${\displaystyle K_{5}}$ avec le rouge et le bleu qui ne contient pas de triangle avec toutes les arêtes de la même couleur. Nous dessinons ${\displaystyle K_{5}}$ sous la forme d'un pentagone entourant une étoile (un pentagramme). Nous colorions les arêtes du pentagone en rouge et les arêtes de l'étoile en bleu. Ainsi, 6 est le plus petit nombre pour lequel nous pouvons prétendre appliquer le théorème. Dans la théorie de Ramsey, nous écrivons ce fait par :

${\displaystyle R(3,3:2)=6.\,}$

• V. Krishnamurthy. Culture, Excitement and Relevance of Mathematics, Wiley Eastern, 1990. (ISBN 81-224-0272-0).

• Coloration de graphe
• Graphe d'amitié

• (en) Bogomolny, Alexander, Party Acquaintances sur Cut The Knot (nécessite Java)