A guide to the Rado graph : exploring structural and logical properties of the Rado graph

Abstract

The Rado graph, denoted R, is the unique (up to isomorphism) countably infinite random graph. It satisfies the extension property, that is, for two finite sets U and V of vertices of R there is a vertex outside of both U and V connected to every vertex in U and none in V . This property of the Rado graph allows us to prove quite a number of interesting results, such as a 0-1-law for graphs. Amongst other things, the Rado graph is partition regular, non-fractal, ultrahomogeneous, saturated, resplendent, the Fra´ıss´e-limit of the class of finite graphs, a non-standard model of the first-order theory of finite graphs, and has a complete decidable theory. We classify the definable subgraphs of the Rado graph and prove results for finite graphs that satisfy a restricted version of the extension property. We also mention some parallels between the rationals viewed as a linear order and the Rado graph.