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 ensembles héréditairement finis (en) (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 prédicat BIT (en)^[1]. 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 = 100₂, 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^[2] ; c'est ce résultat qui justifie l'article défini dans l'expression « le graphe aléatoire » qui le désigne parfois.

Un graphe isomorphe au graphe complémentaire du graphe de Rado peut être obtenu (presque sûrement) par la même construction en choisissant les arêtes avec une probabilité 1–p, ce qui montre que le graphe de Rado est auto-complémentaire^[3].

La propriété d'extension caractérise le graphe de Rado, et permet de montrer que de nombreuses constructions lui sont isomorphes.

Dans les constructions d'Ackermann en 1937, les sommets du graphe de Rado sont les ensembles héréditairement finis (c'est-à-dire les ensembles finis dont les éléments sont eux-mêmes héréditairement finis) et une arête relie deux sommets lorsque l'un d'eux est élément de l'autre^[4].

Une autre construction du graphe de Rado est analogue à celle des graphes de Paley. Les sommets sont les nombres premiers de la forme 4n + 1, et une arête les relie si l'un des deux est résidu quadratique modulo l'autre (cette relation étant symétrique d'après la loi de réciprocité quadratique)^[5].

On peut également le construire comme graphe d’intersection d'un système de blocs infini où chaque bloc est infini (dénombrable)^[6].

Le graphe de Rado satisfait la propriété d'extension suivante^[2] : pour tout couple d'ensembles de sommets finis disjoints U et V, il existe un sommet x n'appartenant ni à U, ni à V, et connecté à tous les sommets de U, mais à aucun de ceux de V ; cette propriété caractérise ce graphe, comme montré ci-dessous.

La définition du graphe par représentation binaire en permet une démonstration constructive, en posant

${\displaystyle x=2^{1+\max(U\cup V)}+\sum _{u\in U}2^{u}}$ :

x est par construction plus grand que tous les éléments de U et de V, adjacent à tous les éléments de U, et puisque U et V sont disjoints, x n'est adjacent à aucun élément de V^[a].

La construction comme graphe aléatoire donne à chaque sommet non dans U ou V une probabilité p^|U|(1-p)^|V| de satisfaire la propriété d'extension, indépendamment des autres sommets ; comme il y a une infinité de tels sommets, il y en a presque sûrement un satisfaisant la propriété^[2].

Pour tout graphe fini ou infini dénombrable G, la propriété d'extension permet de construire un sous-graphe du graphe de Rado isomorphe à G. La démonstration se fait par récurrence sur les sommets de G (supposés indexés par les entiers) : supposant construit un isomorphisme pour les n premiers sommets, on ajoute un nouveau sommet en choisissant dans le graphe de Rado un sommet ayant exactement les mêmes liens avec les sommets déjà construits que les sommets correspondants dans G^[7]. Pour cette raison, on dit parfois que le graphe de Rado est un graphe universel^[8], mais il s'agit en fait d'une notion plus faible que celle de problème universel, définie par la théorie des catégories.

Le graphe de Rado est, à isomorphisme près, le seul graphe dénombrable ayant la propriété d'extension. En effet, si G et H sont deux graphes ayant cette propriété, chacun des deux est isomorphe à un sous-graphe de l'autre ; précisant la construction de ces sous-graphes, il est possible d'obtenir par récurrence un isomorphisme entre G et H en utilisant la méthode du va-et-vient (de façon analogue à la démonstration du théorème de Cantor-Bernstein)^[9].

Partant de deux sous-graphes du graphe de Rado finis et isomorphes, la construction précédente permet de prolonger cet isomorphisme en un automorphisme du graphe entier ; on dit que le graphe de Rado est ultrahomogène^[9]. En particulier, il existe un automorphisme envoyant deux arêtes quelconques l'une sur l'autre, et le graphe de Rado est donc un graphe symétrique. Le groupe des automorphismes du graphe de Rado est un groupe simple ayant la puissance du continu^[10].

Toute partition finie des sommets du graphe de Rado induit au moins un sous-graphe isomorphe au graphe entier. Cameron 2001 en donne une preuve courte, obtenue en recollant des sous-ensembles de chaque sous-graphe induit qui ne vérifieraient pas la propriété d'extension. Trois graphes non-orientés dénombrables seulement ont cette propriété : le graphe de Rado, le graphe complet, et le graphe vide^[11]. Bonato, Cameron et Delić 2000 et Diestel et al. 2007 ont montré que les seuls graphes orientés ayant la même propriété sont obtenus à partir de ces trois graphes en choisissant des orientations convenables des arêtes.

Si l'on s'intéresse à des partitions des arêtes, un résultat analogue, mais plus faible, montre qu'il existe un sous-graphe isomorphe au graphe de Rado entier en choisissant les arêtes parmi deux des éléments de la partition, mais que ce n'est pas toujours possible de prendre les arêtes dans un seul élément^[12].

Ronald Fagin a démontré que si un énoncé concernant les graphes (plus rigoureusement un énoncé de la théorie égalitaire du premier ordre contenant la relation d'adjacence ${\displaystyle a\sim b}$, qui exprime qu'une arête relie les sommets a et b) est vrai pour le graphe de Rado, il est vrai pour presque tous les graphes finis, c'est-à-dire que la proportion des graphes à n sommets pour lesquels l'énoncé est vrai tend vers 1 lorsque n tend vers l'infini^[13].

La propriété d'extension peut être exprimée par une suite infinie d'énoncés du premier ordre ${\displaystyle E_{i,j}}$, l'affirmant pour tous les ensembles de sommets U et V ayant respectivement i et j éléments^[14]. Par exemple, ${\displaystyle E_{1,1}}$ peut s'écrire comme

${\displaystyle \forall a:\forall b:a\neq b\rightarrow \exists c:c\neq a\wedge c\neq b\wedge c\sim a\wedge \lnot (c\sim b).}$

Haim Gaifman (en) a démontré^[15] que l'ensemble des ${\displaystyle E_{i,j}}$ et des énoncés affirmant que la relation d'adjacence est symétrique et antiréflexive sont les axiomes d'une théorie complète^[16], dont le graphe de Rado est l'unique modèle dénombrable (ce dernier résultat découle de l'unicité des graphes possédant la propriété d'extension, et permet de démontrer la complétude grâce au critère de Łoś–Vaught^[17]).

La propriété universelle du graphe de Rado ne se généralise pas, par exemple, à des plongements isométriques, c'est-à-dire à des isomorphismes conservant la distance : le graphe de Rado est de diamètre deux, et donc aucun graphe de diamètre supérieur ne peut s'y plonger isométriquement. Moss a construit pour chaque valeur de n un graphe contenant isométriquement tous les graphes finis de diamètre n^[18], obtenant le graphe infini complet pour n = 1 et le graphe de Rado pour n = 2.

Saharon Shelah a étudié l'existence de graphes universels non dénombrables, obtenant des conditions d'existence suffisantes sur leur cardinal^[19].

• (de) Wilhelm Ackermann, « Die Widerspruchsfreiheit der allgemeinen Mengenlehre », Math. Ann., vol. 114, n^o 1,‎ 1937, p. 305-315 (DOI 10.1007/BF01594179).
• (en) Anthony Bonato, Peter Cameron et Dejan Delić, « Tournaments and orders with the pigeonhole property », Canad. Math. Bull., vol. 43, n^o 4,‎ 2000, p. 397-405 (DOI 10.4153/CMB-2000-047-6, MR 1793941, lire en ligne).
• (en) Peter J. Cameron, Oligomorphic Permutation Groups, Cambridge, Cambridge University Press, coll. « London Mathematical Society Lecture Note Series » (n^o 152), 1990 (ISBN 0-521-38836-8, MR 1066691).
• (en) Peter J. Cameron, « The random graph », dans The Mathematics of Paul Erdős, II, Berlin, Springer, coll. « Algorithms Combin. » (n^o 14), 1997 (Bibcode 2013arXiv1301.7544C, MR 1425227, arXiv 1301.7544), p. 333-351.
• (en) Peter J. Cameron, « The random graph revisited », dans European Congress of Mathematics, vol. I (Barcelona, 2000), Basel, Birkhäuser, coll. « Progr. Math. » (n^o 201), 2001 (MR 1905324), p. 267-274.
• Jean-Paul Delahaye, « Un graphe universel et singulier », Pour la science, n^o 493,‎ novembre 2018, p. 78-83.
• (en) Reinhard Diestel, Imre Leader, Alex Scott et Stéphan Thomassé, « Partitions and orientations of the Rado graph », Trans. Amer. Math. Soc., vol. 359, n^o 5,‎ 2007, p. 2395-2405 (DOI 10.1090/S0002-9947-06-04086-4, MR 2276626).
• (en) Herbert B. Enderton (en), A Mathematical Introduction to Logic, New York-London, Academic Press, 1972 (MR 0337470).
• (en) P. Erdős et A. Rényi, « Asymmetric graphs », Acta Math. Acad. Sci. Hungar., vol. 14,‎ 1963, p. 295-315 (DOI 10.1007/BF01895716, MR 0156334).
• (en) Ronald Fagin, « Probabilities on finite models », J. Symb. Logic, vol. 41, n^o 1,‎ 1976, p. 50-58 (DOI 10.1017/s0022481200051756, MR 0476480, lire en ligne).
• (en) Haim Gaifman, « Concerning measures in first order calculi », Israel J. Math., vol. 2,‎ 1964, p. 1-18 (DOI 10.1007/BF02759729, MR 0175755).
• (en) Étienne Grandjean, « Complexity of the first-order theory of almost all finite structures », Information and Control, vol. 57, n^os 2-3,‎ 1983, p. 180-204 (DOI 10.1016/S0019-9958(83)80043-6, MR 742707).
• (en) Daniel Horsley, David A. Pike et Asiyeh Sanaei, « Existential closure of block intersection graphs of infinite designs having infinite block size », Journal of Combinatorial Designs, vol. 19, n^o 4,‎ 2011, p. 317-327 (DOI 10.1002/jcd.20283, MR 2838911).
• (en) C. Ward Henson, « A family of countable homogeneous graphs », Pacific Journal of Mathematics, vol. 38,‎ 1971, p. 69-83 (DOI 10.2140/pjm.1971.38.69, MR 0304242).
• (en) A. H. Lachlan et Robert E. Woodrow, « Countable ultrahomogeneous undirected graphs », Trans. Amer. Math. Soc., vol. 262, n^o 1,‎ 1980, p. 51-94 (DOI 10.2307/1999974, MR 583847).
• (en) D. Lascar, « Automorphism groups of saturated structures; a review », dans Proc. ICM, vol. II (Beijing, 2002), Beijing, Higher Ed. Press, 2002 (Bibcode 2003math......4205L, MR 1957017, arXiv math/0304205, lire en ligne), p. 25-33.
• (en) J. Łoś (en), « On the categoricity in power of elementary deductive systems and some related problems », Colloquium Math., vol. 3,‎ 1954, p. 58-62 (MR 0061561).
• (en) David Marker, Model Theory : An Introduction, New York, Springer-Verlag, New York, coll. « GTM » (n^o 217), 2002, 342 p. (ISBN 0-387-98760-6, MR 1924282, lire en ligne).
• (en) Lawrence S. Moss, « Existence and nonexistence of universal graphs », Fundamenta Mathematicae, vol. 133, n^o 1,‎ 1989, p. 25-37 (MR 1059159).
• (en) Lawrence S. Moss, « The universal graphs of fixed finite diameter », dans Graph Theory, Combinatorics, and Applications, vol. 2 (Kalamazoo, MI, 1988), New York, Wiley, coll. « Wiley-Intersci. Publ. », 1991 (MR 1170834), p. 923-937.
• (en) Maurice Pouzet et Norbert Sauer, « Edge partitions of the Rado graph », Combinatorica, vol. 16, n^o 4,‎ 1996, p. 505-520 (DOI 10.1007/BF01271269, MR 1433638).
• (en) Richard Rado, « Universal graphs and universal functions », Acta Arith., vol. 9,‎ 1964, p. 331-340 (lire en ligne).
• (en) Saharon Shelah, « On universal graphs without instances of CH », Annals of Pure and Applied Logic, vol. 26, n^o 1,‎ 1984, p. 75-87 (DOI 10.1016/0168-0072(84)90042-3, MR 739914).
• (en) Saharon Shelah, « Universal graphs without instances of CH: revisited », Israel J. Math., vol. 70, n^o 1,‎ 1990, p. 69-81 (DOI 10.1007/BF02807219, MR 1057268).
• (en) Joel Spencer, The Strange Logic of Random Graphs, Berlin, Springer-Verlag, coll. « Algorithms and Combinatorics » (n^o 22), 2001 (ISBN 3-540-41654-4, DOI 10.1007/978-3-662-04538-1, MR 1847951).
• (en) J. K. Truss, « The group of the countable universal graph », Math. Proc. Cambridge Philos. Soc., vol. 98, n^o 2,‎ 1985, p. 213-245 (DOI 10.1017/S0305004100063428, Bibcode 1985MPCPS..98..213T, MR 795890).
• (en) Robert L. Vaught, « Applications to the Löwenheim-Skolem-Tarski theorem to problems of completeness and decidability », Indag. Math., vol. 16,‎ 1954, p. 467-472 (MR 0063993).

• Portail des mathématiques
• Portail de l'informatique théorique