Yop !
Ca doit sans doute être tout bête, mais visiblement il y a quelque chose qui m'échappe.
On me demande de démontrer R(k,2)=k pour tout k (où R désigne le nombre de Ramsey).

"C'est le plus petit entier positif tel que toute coloration par deux couleurs des arêtes du graphe complet à n sommets contient le sous graphe complet à k sommets colorié d'une couleur, ou le sous graphe complet à 2 sommets colorié de l'autre couleur".
Je dois mal comprendre la définition alors, parce que je trouve R(k,2) = 2 peu importe la valeur de k :

Le graphe complet à 2 sommets possède une arête, on va forcément la colorer et donc tomber sur le graphe complet à 2 sommets

Enfin, le but c'est bien de s'assurer que quelle que soit la façon dont on colorie notre graphe, un sous graphe complet (à k sommets ou 2 sommets ) apparaîtra dans une certaine couleur ?

Je reformule un peu :

"C'est le plus petit entier positif n tel que toute coloration en bleu et rouge des arêtes du graphe complet à n sommets contient un sous graphe complet à k sommets colorié en bleu, ou un sous graphe complet à 2 sommets colorié en rouge".

Par exemple, si tu prends n=k-1, il existe le graphe colorié tout en bleu, qui ne vérifie pas la propriété

Ben du coup quand tu colories le graphe entièrement en bleu, t'as notamment colorié une arête en bleu, donc t'as bien fait apparaître le graphe complet à 2 sommets

Y a une autre formulation du nombre qui est : "R(m,n) est le nombre minimum d'individus que tu dois réunir pour être assuré que soit m se connaissent, soit n ne se connaissent pas"

Tu réunis deux mecs, ils peuvent ne pas se connaître, et du coup R(m,2) ça fait 2, non ?
La seule autre possibilité c'est qu'ils se connaissent, mais comme R(m,n)=R(n,m) ça revient au même

Ah non, ok j'ai compris c'est bon

Ben du coup quand tu colories le graphe entièrement en bleu, t'as notamment colorié une arête en bleu, donc t'as bien fait apparaître le graphe complet à 2 sommets

Relis bien, tu dois avoir soit k sommets bleus, soit 2 rouges. Pas 2 bleus.

Et oui pour l'autre formulation (tu remplaces juste bleu et rouge par connait / connait pas), mais par contre ensuite il faut que tout graphe de taille n vérifie la propriété, pas juste qu'il en existe un qui la vérifie.
Si tu en prends deux qui se connaissent, ça marche pas, dont R(m,2) > 2

Edit: Ok !

merci pour la réponse rapide en tous cas

tiens bizarre, j'étais sûr d'avoir édité l'erreur dans le titre quand j'ai édité celle dans le post