Conjecture des lits superposés

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 Modèle:Lien.

La conjecture est réfutée en octobre 2024 par Nikita Gladkov, Modèle:Lien et Alexander Zimin, qui explicitent un contre-exempleModèle:,.

Graphes en lits superposés

Exemple de graphe en lits superposés. Les deux « lits » sont les graphes Modèle:Mvar et Modèle:Mvar, et les « montants » les arêtes Modèle:Mvar, Modèle:MvarModèle:Etc.

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é Modèle:Mvar. La conjecture de 1985 stipule que la probabilité qu'un nœud Modèle:Mvar du « lit » supérieur reste connecté à un autre nœud Modèle:Mvar du même « lit » est supérieure ou égale à la probabilité que Modèle:Mvar reste connecté à Modèle:Mvar (le nœud du « lit » inférieur homologue de Modèle:Mvar).

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 Modèle:Nombre, pour $p=\frac{1}{2}$. À l'aide d'un ordinateur, ils en découvrent un autre, toujours pour $p=\frac{1}{2}$, dont chaque « lit » ne comporte que Modèle:Nobr.

Bibliographie

• Modèle:Article