Problème de théorie des graphes

[nekochan]

Bonjour,
j'ai en fait plusieurs questions et je vous remercie par avance pour vos éclaircissements :lol3:

1) Je ne me souviens plus des origines du résultat suivant : on considère 6 personnes qui peuvent se connaître ou pas (cette relation étant symétrique), alors il existe forcément 3 personnes qui, ou bien se connaissent toutes, ou bien ne se connaissent pas. Ce résultat porte-t-il un nom particulier ?

2) Le problème précédent est lié à celui revenant à déterminer le graphe contenant le plus de sommets possibles tel qu'en coloriant les arêtes avec 2 couleurs, tout triangle soit avec 2 couleurs. Si on passe à trois couleurs possibles et qu'on garde la règle que tout triangle possède exactement deux couleurs, est-ce que le problème est connu et/ou facile à résoudre ?

3) Existe-t-il d'autres jolies généralisations du problème initial ?

[Aristarque]

Problème interessant. Je suppose qu'outre la symétrie de la relation "se connaître", il faut supposer la transitivité. Je ne connais pas l'origine historique du problème, ni l'éventuelle existence d'un grand
théorème général dont on puisse déduire immédiatement la solution au problème.

Le problème en lui même est bien sûr facilement résoluble.

Supposons un graphe (non orienté et exprimant une relation transitive) à 6 arrêtes tel qu'il n'existe pas 3 sommets tous reliés entre eux. On montre alors qu'il existe 3 sommets sans aucune relation les uns avec les autres.

En effet, prenons 2 arrêtes A et B non reliées entre elles (cela existe, sinon 6>3 arrêtes seraient reliées entre elles contrairement à l'hypothèqe). Y a-t-il une troisième arrête sans relation ni avec A ni avec B ?

1) Si oui, alors nous sommes parvenus à notre but.

2) Si non, alors on dispose de 6-2= 4 arrêtes qui doivent être toutes reliées soit à A, soit à B.
Le principe des tiroirs nous dit qu'au moins 2 de ces 4>2 arrêtes est rangée dans la même catégorie (les deux catégories étant "arrêtes reliées à A" et "arrêtes reliées à B") Ainsi, on compte alors 3 arrêtes reliées entre elles, ce qui contredit l'hypothèse de départ. Le cas 2 ne peut donc pas advenir.


Pour ce qui est de ta reformulation en terme de graphe coloré, il me semble qu'il faut ajouter la précision "graphe complet" pour que ta traduction soit juste. Autrement dit, le problème équivaut à trouver le graphe bicolore complet ayant le maximum de sommets tel que tout triangle soit bicolore (les deux couleurs symbolisant les deux états "se connaitre", "ne pas se connaitre" dans la formulation initiale du problème". La démonstration ci-dessus montre qu'une telle configuration n'existe pas pour un nombre d'arrete >4. Il me semble donc que le problème ci-dessus fonctionne déjà avec 5 personnes et non pas 6.

[Ben314]

Salut,
J'ai pas bien compris la réponse de Aristarque (et en particulier le fait qu'il demande à la relation d'être transitive alors que l'énoncé "classique" ne le demande pas).
La preuve standard du résultat avec 6 personnes consiste effectivement à considérer un graphe complet (i.e. chaque sommets est reliée à tout les autres) à 6 sommets (les 6 personnes) dont les arrêtes sont coloriées de deux couleurs selon que les sommets "se connaissent" ou "ne se connaissent pas".

On part d'un sommet A au pif.
De A il part 5 arrêtes donc forcément il y en a au moins 3 de la même couleur AB, AC, AD.
Soit les 3 arrêtes du triangle BCD sont de la même couleur et on a gagné.
Soit elles ne sont pas de la même couleur donc au moins une des trois, par exemple BC, est de la même couleur que AB, AC, AD et le triangle ABC est monochrome.

Des généralisations possible de ce résultat sont les jolis Théorèmes de Ramsey

Edit : Il existe un (unique à permutation prés) coloriage bicolore des arrêtes d'un graphe complet à 5 sommets tels qu'aucun triangle ne soit monochrome : la valeur 6 est minimale.

[nekochan]

Merci à vous deux pour vos réponses, même si tout comme Ben314 je n'ai pas bien compris le message d'Aristarque

[Aristarque]

En effet, la demande de transitivité était de trop. (D'ailleurs, pour l'exemple concret de la relation
de connaissance entre des personnes, c'était bizarre de la demander). Le résultat que j'ai démontré est donc moins fort que celui de BEN314. C'est pour cela que je m'en sors avec 5 arrêtes au lieu de 6.

Mise à part l'hypothèse injustifiée que j'ai rajouté, ma réponse était compréhensible j'espère?