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 Pieter Kasteleyn (en)^[1].

La conjecture est réfutée en octobre 2024 par Nikita Gladkov, Igor Pak (en) et Alexander Zimin, qui explicitent un contre-exemple^[2],[3].

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^[4].

On supprime aléatoirement les arêtes du graphe, avec pour chacune la même probabilité p. La conjecture de 1985 stipule que la probabilité qu'un nœud x du « lit » supérieur reste connecté à un autre nœud y du même « lit » est supérieure ou égale à la probabilité que x reste connecté à y' (le nœud du « lit » inférieur homologue de y)^[4].

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 7 222 nœuds, pour ${\displaystyle p={\tfrac {1}{2}}}$. À l'aide d'un ordinateur, ils en découvrent un autre, toujours pour ${\displaystyle p={\tfrac {1}{2}}}$, dont chaque « lit » ne comporte que 82 nœuds^[4].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bunkbed conjecture » (voir la liste des auteurs).

• Clémentine Laurens, « La conjecture du lit superposé est fausse », Pour la science, n^o 567,‎ janvier 2025, p. 6-7 (lire en ligne, consulté le 4 janvier 2025)

• Portail des mathématiques