Geometric random graphs and Rado sets of continuous functions

Geometric random graphs and Rado sets of continuous functions, Discrete Analysis 2021:3, 21 pp.

For several reasons, random graphs play a central role in the theory of finite graphs. For example, a typical random graph has properties that are hard to establish for explicitly defined graphs, as Erdős famously observed when obtaining his lower bound for diagonal Ramsey numbers. And random graphs provide a model for the study of fascinating phenomena such as phase transitions, a model that is simple enough for remarkably precise results to be obtained but complex enough for those results to be highly interesting and non-trivial.

It is natural to wonder what one can say about infinite random graphs. If, for example, we define a graph $G$ with vertex set $\mathbb N$ by joining each pair of vertices $xy$ with probability $p$, with all choices made independently, then what can we say about $G$?

A rather surprising result is that provided $0<p<1$, all such graphs are isomorphic. More precisely, there is a single infinite graph $\Gamma$, known as the random graph, or sometimes the Rado graph, such that if $G$ is chosen as above, then with probability 1 $G$ is isomorphic to $\Gamma$.

Though surprising, this statement has an easy proof. Here is a quick sketch. Let $G_1$ and $G_2$ be two graphs chosen randomly as above and let $x_1,x_2,\dots$ and $y_1,y_2,\dots$ be enumerations of their vertices. Suppose now that we have finite sets $A,B\subset\mathbb N$ and a bijection $\phi:A\to B$ such that if $i,j\in A$, then $x_ix_j$ is an edge of $G_1$ if and only if $y_{\phi(i)}y_{\phi(j)}$ is an edge of $G_2$. Now let $i\notin A$ and let $A'$ be the set of $j\in A$ such that $x_i$ is joined to $x_j$. Then with probability 1 there exists $r\notin B$ such that the set of $s\in B$ such that $y_r$ is joined to $y_s$ is precisely $\phi(A')$. (That is because each $y_r$ has a non-zero probability of satisfying this condition, all edges are independently chosen, and there are infinitely many possibilities for $y_r$.) Using this simple observation, and the corresponding one with the roles of the $x_i$ and $y_i$ reversed, we can keep extending $\phi$ until all vertices in both vertex sets are matched.

In one way, this shows that the theory of random infinite graphs is not very interesting. But the random graph turns out to have an important role to play in some contexts, model theory being a notable example.

This paper looks at a class of infinite random graphs defined with reference to a separable metric space $X$. The idea is to pick a positive real number $\alpha$ and a countable dense subset $S\subset X$, and to define a random graph $G$ with vertex set $S$ by joining $x,y\in S$ with probability $p$ if $d(x,y)<\alpha$ and not joining them otherwise. Thus, locally this graph looks like the random graph, but distant vertices are not joined.

This class was introduced in a paper of the first two authors in 2009. That paper contains the result that if $X=\mathbb R$ with the usual metric, and $S$ is a countable dense subset of $X$ such that no two distinct points in $S$ have an integer distance from each other, then all the resulting random graphs are isomorphic. Again this is proved by a back-and-forth argument, but the details are significantly more complicated than they are for the original Rado graph. They also proved the same for the space $\ell_\infty^n$ (this time the condition is that no two distinct points have a coordinate that differs by an integer), as well as showing that it fails for the plane with the Euclidean distance.

In general, it seems that the Rado property requires some kind of $\ell_\infty$-ish structure to hold, which motivates the study in this paper of subsets of $C[0,1]$, the space of continuous functions on the closed interval $[0,1]$ with the sup norm. The authors consider the following three dense subsets of $C[0,1]$: piecewise linear functions, polynomials, and Brownian motions. In each case, in order to obtain countable dense sets that satisfy suitable conditions (similar to, but more complicated than, the conditions about coordinates that differ by an integer), they define a probability measure $\mu$ supported on the given class of functions that has full support in the sense that every non-empty open subset has positive measure, and they then choose points $x_1,x_2,\dots$ independently at random using the measure $\mu$.

In each case they obtain sets with the Rado property. However, it turns out, interestingly, that while the universal graphs that arise for piecewise linear functions and polynomials are the same, the one for Brownian motion paths is different. This reflects the fact that if two Brownian motion paths cross each other, then with probability 1 they cross each other infinitely many times. Moreover, the graphs in all three cases are not isomorphic to the graphs that arise for $\ell_\infty^n$ or for infinite-dimensional sequence spaces that were examined in an earlier paper of the authors.