Une conjecture à dormir debout


Fabien Aoustin

Les lits superposés ne sont pas que des meubles pour chambres d’enfants, dortoirs ou casernes. Ce sont aussi des objets mathématiques !

 Prenez un graphe G, c’est-à-dire un ensemble de sommets, reliés entre eux par des arêtes : ce sera la couchette du bas. Prenez un deuxième exemplaire G' du même graphe : ce sera la couchette du haut. Il ne reste plus qu’à relier chaque sommet de G à son homologue dans G' pour obtenir un « lit superposé ». 

 


On relie ensemble deux copies d’un même graphe pour obtenir un « lit superposé ». 

 

Un jeu amusant consiste alors à éliminer chaque arête du « lit superposé » avec une certaine probabilité p fixée à l’avance et de regarder les chemins qui subsistent. Prenons le cas d’un triangle ABC pour la « couchette » du bas, relié à un triangle A'B'C'. On peut obtenir 512 graphes différents et pour p = 1/2 toutes ces configurations sont équiprobables. On dénombre 362 graphes dans lesquels il existe un chemin de A vers B mais seulement 307 pour lesquels on peut aller de A à B'.

 


Un exemple de graphe obtenu après élimination aléatoire d’arêtes.
Il y a encore un chemin pour aller de A vers B
mais il n’y en ... Lire la suite

-->