Gudule : tout d'abord, bienvenue chers lecteurs, nous voici de retour pour un nouveau chapitre de PJAM, le bouquin auquel il faudra mettre fin avant que CN ne devienne totalement fou.

CN (dans le fond de la pièce, devant un écran) : c'est trop bien!!!!!!!

(Il agite des bras comme un(e) one-directioner hystérique)

Gudule : après ces probas qui lui ont fait beaucoup de mal, j'ai réussi à sauver CN en trouvant le site internet http://www.openproblemgarden.org . Qui récapitule des problèmes ouverts. Tous ceux dont on a déjà parlé y sont bien sûr, et il y en a beaucoup d'autres.

CN (bave) : les graaaaaaaphes !

Gudule : alors parlons de la conjecture de la reconstruction. Allez, maître, au boulot.

(CN ronchonne)

Considérez un graphe, c'est-à-dire un ensemble de trucs reliés entre eux.

Parce que nous sommes dans PJAM, nous allons nommer les trucs des « schtroumpfs » plutôt que des sommets et les liens des « amitiés » plutôt que des arcs. Dans le monde merveilleux des schtroumpfs, si je suis ami avec quelqu'un alors il est ami avec moi, contrairement à la vraie vie.

Non, en fait je déteste écrire le mot « schtroumpf ».

Prenez donc un graphe. Vous faites sauter un des sommets (et donc tous les arcs qui l'incluaient) et vous obtenez un graphe plus petit qui est un sous-graphe induit. Pour des raisons qui m'échappent, vous appelez ça une carte.

Attention, pas une carte comme dans « carte du monde ». Non, une carte comme dans Pokémon, ou comme dans l' « âme des cartes » chère à la réincarnation du pharaon.

(NDA : J'ai été jeune à une époque)

Vous refaites l'opération avec chaque sommet et vous obtenez un deck.

(Oui, un deck : un ensemble de cartes. Certains vieux comme moi ont connu cette époque à laquelle on jouait à des jeux avec des cartes rassemblées en « deck ». C'était avant que Big Brother n'invente Pokémon Go pour contrôler vos déplacements et...

Gudule : vous n'allez quand même pas vous y mettre vous aussi ?

Gudule, que fais-tu dans cette parenthèse ?

Gudule : bon, je m'en vais, je vous attends à l'extérieur.)

La « conjecture de la reconstruction », dans sa version forte, dit qu'un graphe est déterminé par son deck. Plus exactement, c'est « à isomorphisme près », un isomorphisme n'étant rien d'autre qu'une préservation de la structure du graphe.

Donc vous pouvez reconstruire le graphe à partir de ses sous-graphes. Un tel graphe est dit « reconstructible », et on aimerait bien montrer que tous les graphes le sont. Plus facile à dire qu'à faire. Comme d'habitude, des amateurs de probas ont déjà remarqué que ça marchait pour « presque tous » les graphes. Si vous construisez un graphe aléatoire avec n sommets, lorsque n devient grand, la probabilité que ce graphe soit reconstructible (et même juste reconstructible à partir de trois cartes de son deck !) tend vers 1.

(Attention ! Je n'aime pas les probabilités en général mais j'aime bien les graphes aléatoires. Eh oui, l'être humain est plein de contradictions).

Voici donc une preuve de plus pour ceux qui en doutaient que les graphes sont des objets compliqués.

Gudule : qui en doutait ?

Lui, là, derrière son écran. Oui, je te vois. Je suis sûr que tu en doutais, misérable. Tremble devant la toute-puissance du FTM, créateur des maths et de l'univers, et surtout des maths.

FTM : j'ai clairement passé plus de temps sur les maths que sur l'univers. En fait, je venais juste de terminer les maths, j'étais content de moi, j'ai mis de l'eau à chauffer pour le thé et je me suis assoupi. Et là, sans faire gaffe, la chaudière a explosé. Le Big Bang. La théière a été catapultée entre Andromède et la Voie Lactée. Elle s'est ensuite crashée au XIVe siècle en Asie, conduisant à l'invention du thé ainsi qu'à celle des nouilles en raison du culte pastafariste. Mais c'est en Italie qu'à la suite de révélations que je lui ai faites, Léonard de Vinci a inventé le spaghetti dont les proportions divines inspirées du nombre d'or...

(Gudule prend des notes pour ses chroniques)

(Dan Brown prend des notes pour son prochain roman)

(Giorgio A. Tsoulakos prend des notes pour le prochain épisode d'Alien Theory : la vérité sur les contacts de nos ancêtres avec le FTM)

(CN regarde avec de grands yeux la conjecture d'Erdos-Turan sur les bases additives)

(Alcibiade s'enfuit du frigo)

Alcibiade : je suis libre !

-----------------------

...

Je dors trop peu en ce moment.

Et m'en vais d'ailleurs vérifier que mon dernier yaourt est toujours dans le frigo, j'ai un doute.