Graphe de Rado

En mathématiques, et plus précisément en théorie des graphes, le graphe de Rado, appelé également graphe d'Erdős–Rényi ou graphe aléatoire, est un graphe infini dénombrable étudié au début des années 1960 par Richard Rado, Paul Erdős et Alfréd Rényi, caractérisé par la propriété d’extension, qui implique qu’il contient (en tant que sous-graphe) n'importe quel graphe fini ou dénombrable. Il en existe plusieurs constructions ; c'est en particulier (presque sûrement) le graphe aléatoire obtenu en choisissant au hasard pour chaque paire de sommets s'ils sont connectés ou non. Le graphe de Rado fut construit par Wilhelm Ackermann en 1937 à partir des (plus exactement, il décrivit un graphe orienté à partir duquel on obtient le graphe de Rado en supprimant l'orientation). Dans leur travail sur les graphes aléatoires, Paul Erdős et Alfréd Rényi le construisirent comme un graphe aléatoire infini et montrèrent qu'il possède un nombre infini d'automorphismes par un argument qui permettrait également d'en prouver l'unicité. Richard Rado le redécouvrit en tant que graphe universel, et en donna une construction déterministe essentiellement équivalente à celle d'Ackermann. Ackermann et Rado donnèrent une construction explicite utilisant le . Identifiant les sommets du graphe et les entiers naturels 0, 1, 2,..., une arête relie les sommets x et y (avec x < y) si et seulement si le bit de rang x de la représentation binaire de y vaut 1. Par exemple, il y a un lien entre x = 2 et y = 4 = 1002, mais non entre x = 1 et y. Le graphe de Rado apparaît presque sûrement quand on applique le modèle de graphe aléatoire développé par Erdős et Rény à un ensemble dénombrable de sommets. Plus précisément, choisissant indépendamment pour chaque paire de sommets avec probabilité p (0 < p < 1) si ces sommets sont reliés par une arête, le graphe résultant est presque sûrement (c'est-à-dire avec probabilité 1) isomorphe au graphe de Rado ; c'est ce résultat qui justifie l'article défini dans l'expression « le graphe aléatoire » qui le désigne parfois.