En théorie des graphes, la conjecture des lits superposés (ou du lit superposé) est une conjecture en théorie de la percolation, proposée en 1985 par ..
La conjecture est réfutée en par Nikita Gladkov, et Alexander Zimin, qui explicitent un contre-exemple..
Graphes en lits superposés vignette| Exemple de graphe en lits superposés. Les deux « lits » sont les graphes et , et les « montants » les arêtes , Un graphe en lits superposés est constitué de deux graphes connexes isomorphes, généralement représentés comme deux graphes identiques disposés l'un au-dessus de l'autre (les deux « lits »), connectés par des arêtes supplémentaires (les « montants ») reliant deux à deux les nœuds homologues..
Conjecture On supprime aléatoirement les arêtes du graphe, avec pour chacune la même probabilité . La conjecture de 1985 stipule que la probabilité qu'un nœud du « lit » supérieur reste connecté à un autre nœud du même « lit » est supérieure ou égale à la probabilité que reste connecté à (le nœud du « lit » inférieur homologue de ).
Réfutation En s'inspirant des travaux de Lawrence Hollom sur une variante de la conjecture généralisée aux hypergraphes, Gladkov, Pak et Zimin construisent un contre-exemple dont chacun des deux « lits » comporte , pour . À l'aide d'un ordinateur, ils en découvrent un autre, toujours pour , dont chaque « lit » ne comporte que .
Notes et références
Bibliographie
Catégorie:Théorie des graphes lits superposés