Nombres de Ramsey

[aNyFuTuRe-]

Salut à tous,

J'aimerai en savoir un plus sur la relation entre nombres de Ramsey et théorie des graphes? Quelqu'un aurait-il l'amabilité de m'expliqué simplement le rapport : comment ca marche quoi en gros

J'aimerai traité des question du types : " Soit E un groupe formé d'un nombre impair de personnes. Montrer qu'il existe au moins un personne dont le nombre de connaissance est pair".

Au premier abord ça peut paraître évident (?) mais a montrer c'est dur...
Il faut compter de deux manières différentes le nombre de couples (x,y) de personne où x connaît y.


Merci d'avance
-----

[Médiat]

Au premier abord ça peut paraître évident (?) mais a montrer c'est dur...

Cette partie est effectivement facile, en langage des graphes : si tu comptes les arêtes du graphe qui partent de chaque sommet et que tu les ajoutes, tu obtiens une somme d'un nombre impair de nombres impairs, le résultat est donc impair, sauf que tu as ainsi compté chaque arête 2 fois (une fois pour chacun des sommets) le résultat devrait donc être pair...

[aNyFuTuRe-]

Merci pour votre réponse mais pourriez vous m'en dire plus sur le lien entre nombre de Ramsey et théorie des graphes?

[Médiat]

Merci pour votre réponse mais pourriez vous m'en dire plus sur le lien entre nombre de Ramsey et théorie des graphes?

Les nombre de Ramsey que je connais sont liés à la bicoloration des graphes, c'est donc bien une partie de la théorie des graphes...

[A voir en vidéo sur Futura]

[aNyFuTuRe-]

Pourriez vous m'expliciter ce lien entre nombre de Ramsey et bicoloration des graphes?

Par exemple, si l'on considère un graphe a 6 sommets (donc 6 personnes) de quelle manière montre t-on que l'on peut trouver soit 3 personnes qui se connaissent deux a deux soit 3 qui ne se connaissent pas ? (c'est le problème de base pour illustrer les nombres de Ramsey que j'ai résolu avec une autre méthode que celle qui utilise les graphes )

Dernière question: la présence de triangles dans les graphes est est-elle nécessaire dans ce genre de problème ?

Merci de m'éclairer