Contexte historique et modèles aléatoires
En 1958, Edgar Gilbert a introduit le modèle de graphe aléatoire binomial pour représenter les réseaux téléphoniques, modèle repris indépendamment par Erdős et Rényi. Le processus consiste à prendre n sommets, à choisir chaque paire et à créer une arête selon le résultat d’une pièce de monnaie, éventuellement biaisée. Ce modèle, noté G(n,p), a permis dans les années 1970 de caractériser les conditions d’apparition d’un cycle hamiltonien, c’est‑à‑dire un chemin passant une fois par chaque sommet. Deux décennies plus tard, les chercheurs ont étendu ces résultats aux graphes réguliers, où chaque sommet possède exactement r arêtes, mais les dépendances structurelles rendent l’analyse nettement plus difficile.
Principe du sandwich de graphes
Kim et Vu, au début des années 2000, ont proposé une « sandwich » : construire simultanément un graphe binomial G(n,p) et un graphe r‑régulier G_reg de sorte que les arêtes de G soient incluses dans G_reg (couche inférieure) et que G_reg soit elle‑même incluse dans un autre graphe binomial plus dense (couche supérieure). Si une propriété monotone (par exemple la présence d’un cycle hamiltonien) est vraie pour le graphe le plus dense, elle se transmet automatiquement aux deux autres couches. Le défi réside dans la génération conjointe des deux processus aléatoires, qui utilisent habituellement des mécanismes incompatibles.
Preuve du conjecture en 2025
En 2025, trois mathématiciens ont finalisé la démonstration du « sandwich conjecture » formulé en 2004 : pour tout graphe r‑régulier suffisamment grand, il existe toujours une paire de graphes binomiaux G_low et G_high satisfaisant G_low ⊆ G_reg ⊆ G_high. La preuve repose sur une analyse fine des probabilités d’apparition d’arêtes dans les deux processus, combinée à des techniques de couplage de mesures et à un raffinement du lemme de concentration de Chernoff. Les auteurs ont montré que, dès que r dépasse un seuil logarithmique en n (par exemple r ≥ C·log n), la probabilité de construire le sandwich tend vers 1 lorsque n → ∞.
Implications et limites
Le résultat permet de transférer immédiatement toute propriété monotone prouvée pour les graphes binomiaux — telles que la connectivité, la présence de cycles hamiltoniens ou les seuils de percolation — aux graphes réguliers, qui modélisent plus fidèlement les réseaux physiques (Internet, réseaux neuronaux). Cependant, la démonstration s’appuie sur l’hypothèse d’un nombre de sommets « suffisamment grand », sans fournir de borne explicite exploitable en pratique. De plus, les propriétés non monotones (par exemple la distribution exacte du nombre de triangles) restent hors de portée du sandwich. Les travaux futurs devront donc préciser les constantes cachées et explorer des extensions vers des modèles de graphe plus structurés, comme les graphes hyperboliques ou les réseaux à degrés hétérogènes.
