Mois : septembre 2014

TPA : Théorème de Ramsey

Publié le par Balise2 commentaires

Je viens de me rendre compte que j’avais pas encore parlé de théorie de Ramsey dans ce blog, ce qui est profondément scandaleux, parce que c’est un sujet très rigolo. Donc, commençons – aujourd’hui, c’est TPA.

Supposons que nous ayons un graphe dit « complet », c’est-à-dire qu’on se donne un ensemble de sommets, et qu’on trace tous les arcs possibles entre tous les sommets. On dénote par K_n le graphe complet sur n sommets - par exemple, je vous présente K_5 :

 

k5-mono

Maintenant, on va colorier les arcs du graphe en rouge et en bleu, de façon arbitraire. On peut par exemple colorier tous les arcs en bleus, tous les arcs en rouge, ou choisir d’autres coloriages :

Et avec ce coloriage, on se pose une première question : est-ce qu’il est possible d’avoir un coloriage tel qu’on ne puisse pas trouver dans la figure un triangle bleu ou un triangle rouge, c’est-à-dire trois sommets reliés uniquement par des arcs bleus ou rouges ? Les deux du haut ne fonctionnent clairement pas (puisque tous les sommets sont reliés par des arcs bleus et rouges respectivement). Le coloriage en bas à gauche ne fonctionne pas non plus : il a un triangle bleu et un triangle rouge (vous les voyez ?). Le coloriage en bas à droite n’a pas de triangle rouge, mais il a un triangle bleu.

Pour 5 points, ce n’est pas très difficile de finir par trouver un coloriage qui ne contient ni triangle bleu ni triangle rouge, et c’est celui-ci :

k5-notriangle

L’étape suivante est de se poser la même question non pas avec un graphe complet sur 5 sommets (K_5) mais avec un graphe complet sur 6 sommets (K_6), comme celui-ci :

k6

Et la réponse est non, ce n’est pas possible : on ne peut pas colorier une K_6 avec deux couleurs en évitant d’avoir un triangle monochromatique (tout bleu ou tout rouge, donc). La première remarque qu’on peut faire, c’est que pour vérifier par force brute que c’est effectivement le cas, ça va prendre un petit peu de temps. Le graphe ci-dessus a 15 arcs, ce qui correspond à 2^{15} coloriages différents. Pour voir ça, on peut choisir un ordre pour les arcs (n’importe quel ordre) et commencer à colorier. Pour le premier arc, on peut choisir rouge ou bleu, ça fait deux choix. Pour le deuxième arc, idem – et on a déjà quatre choix avec deux arcs, puisqu’ils peuvent être tous les deux rouges, tous les deux bleus, rouge-bleu ou bleu-rouge. Le troisième choix multiplie encore ces choix par deux (puisque chaque choix peut correspondre à un troisième arc rouge ou bleu), et ainsi de suite pour les 15 arcs, soit 2×2×2×…×2 = 2^{15}. 2^{15}, ça fait 32768. À la main, ça va faire beaucoup de coloriages à vérifier, mais sur un ordinateur, ça reste encore nettement dans le domaine du faisable.

Avant de programmer le coloriage et de vérifier, on peut se demander s’il y aurait moyen de prouver qu’il y a toujours un triangle monochromatique dans une K_6 coloriée avec 2 couleurs. Donc, on prend un coloriage, n’importe lequel. On prend un sommet, n’importe lequel aussi. Ce sommet, il a 5 arcs qui y sont connectés, et parmi ces cinq arcs, il y en a au moins trois qui sont de la même couleur (parce que si j’ai au plus deux arcs bleus ET au plus deux arcs rouges, ben j’ai au plus 4 arcs). Pour faire simple, je vais supposer que les trois arcs qui sont de la même couleur sont bleus (je peux toujours faire ça, si ce n’est pas le cas il suffit de remplacer rouge par bleu et bleu par rouge dans ce qui suit). Maintenant on fait une petite figure avec des notations.

k6-firstcolors

J’ai au moins trois arcs bleus qui partent de mon sommet initial, j’en choisis exactement trois (les deux autres peuvent être rouges ou bleus). Ces arcs définissent trois points sur le graphe, qui sont les autres extrémités des trois arcs ; je nomme ces points u, v et w. Et là, il peut se passer plusieurs choses. Si l’arc entre u et v est bleu, alors j’ai un triangle bleu. Si l’arc entre v et w est bleu, alors j’ai un triangle bleu. Si l’arc entre u et w est bleu, alors j’ai un triangle bleu. Et si rien de tout ça ne se passe…

k6-plusred

ben l’arc entre u et v est rouge, l’arc entre v et w est rouge, et l’arc entre w et u est rouge aussi, donc le triangle défini par u, v, w est tout rouge. Tout ce que j’ai raconté là s’applique à n’importe quel coloriage (même s’il faut éventuellement changer rouge en bleu et bleu en rouge), et donc on ne peut pas trouver de coloriage qui n’ait ni triangle bleu, ni triangle rouge.

La remarque suivante, c’est que n’importe quelle K_n (c’est-à-dire un graphe complet sur n sommets), pour n \geq 6, contient une K_6. Donc si on ne peut pas colorier une K_6 sans avoir de triangle monochromatique, on ne peut pas non plus colorier une K_n, n\geq 6 sans triangle monochromatique.

Donc, pour les triangles, on sait ce qu’il se passe : pour n\leq 5, on peut trouver un coloriage tel qu’on ne trouve pas de triangle monochromatique, et pour n \geq 6, on a prouvé qu’il n’existait pas.

La question suivante est : maintenant qu’on a des choses pour les triangles, est-ce qu’on peut avoir le même genre de résultat pour plus de points ? Plus spécifiquement, si je considère une K_n, est-ce que je peux la colorier avec deux couleurs de manière à éviter d’y trouver une K_4, K_5, K_6, K_{42} de la même couleur (remarquons qu’un triangle est une K_3 😉 )? Et ben, c’est une question compliquée. Pour être sûr de trouver une K_4, il a été prouvé qu’on a besoin de 18 points. Ce qui veut dire qu’on peut colorier ce bidule-là avec 2 couleurs et ne pas y trouver de K_4 monochromatique:

K17

Si on rajoute un sommet et qu’on le connecte à tous les autres, par contre, on est sûr de trouver une K_4 monochromatique si on colorie avec deux couleurs. Là, pour le coup, si on veut réellement vérifier tous les coloriages possibles, il va vraiment falloir faire des progrès sur la puissance informatique. Une K_{18} (un graphe complet sur 18 sommets, donc) a 153 arcs, donc si on se mettait en tête de vérifier tous les coloriages, il faudrait en vérifier 2^{153}. Si on est capable de vérifier un coloriage par nanoseconde (ce qui n’est pas franchement réaliste), il faudrait plus de 3 000 000 000 000 000 000 000 000 000 (3 suivi de 27 zéros) SIÈCLES pour tout vérifier… on est pas rendu 🙂

Là où ça devient VRAIMENT amusant, c’est quand on se pose la question de trouver des K_5 et supérieur (qui soient monochromatiques, donc). Pour la K_5, on sait que pour plus de 49 sommets, on la trouvera nécessairement. On sait aussi qu’on peut construire un coloriage sur 42 sommets sans K_5 monochromatique. Le lecteur attentif aura remarqué qu’on ne sait pas ce qu’il se passe entre 43 et 49 sommets… La situation est de moins en moins claire au fur et à mesure : pour la K_{10} monochromatique, on sait que le seuil se situe quelque part entre 798 (pour 797 sommets on sait qu’on peut colorier sans avoir de K_{10} monochromatique) et… 23556 (pour un graphe complet sur 23556 sommets colorié avec deux couleurs, on sait qu’on aura toujours une K_{10} monochromatique).

Le théorème de Ramsey qui donne son nom à ce billet de blog dit que quelque soit r, on peut trouver un n tel que tout coloriage avec deux couleurs d’une K_n contienne nécessairement une K_r monochromatique. Ledit théorème est plus général que ça : il dit que pour tout r_1, r_2, r_3... r_\ell on peut trouver un n tel que tout coloriage de K_n avec \ell couleurs c_1, c_2,..., c_\ell contient ou bien une K_{r_1} de couleur c_1, ou bien une K_{r_2} de couleur c_2, …, ou bien une K_{r_\ell} de couleur c_\ell. Et on dénote n par R(r_1, r_2,..., r_\ell). (Pour rattacher aux trucs précédents, j’ai démontré que R(3,3) = 6, et j’ai indiqué que R(4,4) = 18, 43 \leq R(5,5) \leq 49 et que 798 \leq R(10,10) \leq 23556.

On peut exprimer ça de façon plus « philosophique » en disant qu’une structure suffisamment grande aura toujours un peu d’ordre local quelque part. Ce que je trouve personnellement assez fascinant.

Le mot de la fin revient à Joel Spencer: « Erdős nous a demandé d’imaginer une force d’extraterrestres, beaucoup plus puissante que nous, qui atterrit sur Terre et nous demande la valeur de R(5,5), ou bien ils détruisent la planète. Dans ce cas, dit-il, nous devrions combiner la puissance de tous nos ordinateurs et de tous nos mathématiciens pour tenter de trouver la valeur. Mais supposons qu’ils demandent R(6,6). Dans ce cas, il pense qu’il faudrait détruire les extraterrestres. » (traduction personnelle).

#balisebooks – Août 2014

Publié le par Balise3 commentaires

On aurait pu penser qu’un mois où j’ai 12h d’avion aurait été un mois faste pour le #balisebooks, mais on aurait visiblement eu tort. Et en plus c’était un mois assez peu enthousiasmant sur les bouquins que j’ai lus (après, si c’est un problème d’humeur générale ou la faute à pas de chance… allez savoir.)

Bone Crossed, de Patricia Briggs (en français ), est le 4e tome des Mercy Thompson,  qui s’en va chasser des fantômes à Spokane. Toujours dans la lignée.

Spring MVC: Beginner’s Guide, d’Amuthan G (pas de traduction française) est un gros tutoriel sur le framework Java Spring MVC. Plutôt bien fichu, j’ai appris beaucoup de choses (et je suis capable de les appliquer à mes bidules courants), quelques problèmes de cohérence ici et là mais rien d’insurmontable. Un peu plus de profondeur aurait été appréciée par moments (sur les mécanismes d’injection par exemple).

Fall of Giants, de Ken Follett (La Chute des géants, en français) est le premier tome de la Century Trilogy. On y suit l’histoire de plusieurs personnages au début du XXe siècle jusqu’à quelques années après la fin de la première guerre mondiale – au Royaume-Uni, en Allemagne, aux États-Unis et en Russie. Je l’ai trouvé long – il m’a fallu trois semaines pour le finir (en ne lisant que ça), ce qui est rare, mais plutôt chouette. Et comme je suis nulle en histoire, j’y ai même appris des choses (genre, par exemple, l’histoire des taxis de la Marne).

Vivien’s Heavenly Ice Cream Shop, d’Abby Clements (La Merveilleuse boutique de crèmes glacées de Viviane, en français) est l’histoire de deux sœurs qui héritent de la boutique de glaces de leur grand-mère. C’est meugnon, c’est plein de bons sentiments et de décisions stupides, vite lu, vite oublié. Mais je mangerais bien de la glace.

Lock In, de John Scalzi (pas encore de traduction en français) est à la fois un bon bouquin et la déception de ce mois-ci. J’avais lu Unlocked, la grosse nouvelle d’intro, en juin, et j’avais été très enthousiaste ; Lock In m’a moins enthousiasmée. Dans le monde décrit dans Unlocked, Chris est un des patients Haden – il est paralysé dans son lit, mais il peut se balader librement grâce à un « threep » – un genre de robot contrôlé par la pensée, en gros. C’est son premier jour au FBI – et le voilà à enquêter sur la mort violente de quelqu’un, mort pour laquelle le seul témoin et suspect est un Intégrateur (une personne qui peut mettre à disposition son corps pour les Haden), ce qui pose évidemment quelques problèmes sur l’identité « réelle » du coupable. J’ai l’impression que Lock In aurait gagné à être un peu plus long. Ça reste très sympa : le feeling est un peu celui des Cavernes d’Acier d’Asimov ; mais j’attendais exceptionnel.

S’il ne fallait en lire qu’un… Fall of Giants.