# Geometric random graphs and Rado sets of continuous functions

Anthony Bonato  Department of Mathematics
Ryerson University
Toronto, ON
Canada, M5B 2K3<EMAIL_ADDRESS>,  Jeannette Janssen  Department of
Mathematics and Statistics
Dalhousie University
Halifax, NS
Canada, B3H 3J5<EMAIL_ADDRESS>and  Anthony Quas  Department of
Mathematics and Statistics
University of Victoria
Victoria BC
Canada, V8W 2Y2<EMAIL_ADDRESS>
###### Abstract.

We prove the existence of Rado sets in normed subspaces of the Banach space of
continuous functions on $[0,1]$. A countable dense set $S$ is Rado if with
probability 1, the infinite geometric random graph on $S$, formed by
probabilistically making adjacent elements of $S$ that are within unit
distance of each other, is unique up to isomorphism. We show that for a
suitable measure which we construct, almost all countable dense sets in the
subspaces of piecewise linear functions and of polynomials are Rado. Moreover,
all graphs arising from such sets are of a unique isomorphism type. For the
subspace of Brownian motion paths, almost all countable subsets are Rado (for
a suitable measure) and the resulting graphs are of a unique isomorphism type.
We show that the graph arising from piecewise linear functions and polynomials
is not isomorphic to the graph arising from Brownian motion paths. Moreover,
these graphs are non-isomorphic to graphs arising from Rado sets in
$\mathbb{R}^{n}$, or the sequence spaces $c$ and $c_{0}$.

###### Key words and phrases:

graphs, random geometric graphs, infinite dimensional normed spaces,
continuous functions

###### 1991 Mathematics Subject Classification:

05C63, 05C80, 54E35, 46B04

The authors gratefully acknowledge support from NSERC

##  1\. Introduction

Erdős and Rényi [13] discovered that for $p\in(0,1)$, almost surely
realizations of the infinite binomial random graph $G(\mathbb{N},p)$ are
isomorphic (and the isomorphism class is the same for all $p\in(0,1)$). The
almost sure isomorphism class is named the _infinite random graph_ , or the
_Rado_ graph, and is written $R$. The graph $R$ is the unique countable graph
satisfying the _existentially closed_ (or _e.c._) property: for all finite
disjoint sets of vertices $A$ and $B$ (one of which may be empty), there is a
vertex $z\notin A\cup B$ adjacent to all vertices of $A$ and to no vertex of
$B$. We say that $z$ is _correctly joined_ to $A$ and $B$. See Chapter 6 of
[4] and the surveys [8, 9] for additional background on $R$.

In [5], infinite random geometric graphs with analogous properties to $R$ were
introduced. Consider a normed space $X$ with norm $\|\cdot\|$, a countable
subset $V$ of $X$, and $p\in(0,1)$. The Local Area Random Graph
$\mathrm{LARG}(V,p)$ has vertices $V$, and for each pair of vertices $u$ and
$v$ with $\|u-v\|<1$, an edge is added joining $u$ and $v$ independently with
probability $p$. Since $V$ is required to be countable and we will focus on
the case where $V$ is dense in $X$, we require $X$ to be separable. A
countable dense set $V$ in a normed space $X$ is _Rado_ if for all
$p\in(0,1)$, with probability $1$, $\mathrm{LARG}(V,p)$ generates a unique
isomorphism type of graph. For simplicity, we call these _LARG graphs_. For a
real number $1\leq p\leq\infty$ and $d\geq 1$ an integer, the vector space
$\mathbb{R}^{d}$ of dimension $d$ equipped with the metric derived from the
$p$-norm is denoted by $\ell_{p}^{d}$. If $p=\infty$, then in [5] it was shown
that almost all countable dense sets are Rado (here and for the rest of this
section, “almost all” refers to a suitable measure constructed in the paper).
The unique countable limits in the $d$-dimensional case were named $GR_{d}$;
for a fixed $d$, these graphs are all isomorphic regardless of the choice of
$p$. In contrast, it was also shown in [5] that if $p=2$, there are sets in
$\ell_{p}^{2}$ which are strongly non-Rado. The latter result was generalized
in [1], which proved that if $X$ is a finite-dimensional normed space not
isometric to $\ell_{\infty}^{d}$, then almost every random dense set $V$ is
not Rado.

A question posed at the end of [1] was to classify the Rado sets in the
infinite dimensional case. As referenced in [6], even finding examples of Rado
sets in infinite dimensional space was left as an open problem, and this was
settled in [7]. Let $c$ be the space of all convergent, real sequences
equipped with the $\ell_{\infty}$ norm. Let $c_{0}$ denote the subspace of $c$
consisting of sequences converging to 0. It was shown in [7] that
$\mu^{\mathbb{N}}$-almost all countable dense sets in the space of convergent
sequences $c$, and $\mu_{0}^{\mathbb{N}}$-almost all countable subsets of the
subspace $c_{0}$ are Rado, where $\mu$ and $\mu_{0}$ are measures on $c$ and
$c_{0}$, respectively, satisfying certain natural conditions.

We extend our results to the setting of $C[0,1]$, the Banach space of
continuous functions on $[0,1]$. We show that Rado sets exist in $C[0,1]$, and
they are abundant when restricted to certain subspaces including piecewise
linear functions, polynomials, or Brownian motion paths. One of our main tools
is the new notion of smoothly dense sets, which will be defined in Section 2.
As we will prove in Theorems 7 and 8, respectively, there exist measures $\mu$
such that $\mu^{\mathbb{N}}$-almost all countable sets in the subspace of
piecewise linear functions and polynomials are smoothly dense. In Theorem 4,
we show that there is a graph $GR(\rm{SD})$ such that for any smoothly dense
subset $V$ of $C([0,1])$ and any $p\in(0,1)$, $\mathrm{LARG}(V,p)$ is almost
surely isomorphic to $GR(\rm{SD})$.

In Section 3, we prove parallel results for so-called infinite crossing dense
sets. We prove that countable families of Brownian motions are almost surely
infinite crossing dense, and establish the existence of a graph $GR(\rm{ICD})$
such that for any infinite crossing dense subset $V$ of $C([0,1])$ and any
$p\in(0,1)$, $\mathrm{LARG}(V,p)$ is almost surely isomorphic to
$GR(\rm{ICD})$.

We showed in [7] that if a countable dense subset of a Banach space is Rado,
then the almost sure isomorphism type of the local area Rado graph determines
the Banach space. In Section 4, we show that in $C([0,1])$, the Rado graph
“sees” properties of the dense collection of functions and not just the
underlying Banach space. In particular, we show that the graph isomorphism, if
it exists and preserves crossings of pairs of functions, allowing us to prove
that $GR(\rm{SD})$ and $GR(\rm{ICD})$ are non-isomorphic (and are non-
isomorphic to the graphs $GR(X)$ studied in previous papers for other Banach
spaces $X$).

Throughout, all graphs considered are simple, undirected, and countable unless
otherwise stated. We will encounter two distinct notions of distance: metric
distance (derived from a given norm) and graph distance. In a normed space, we
write $\|u-v\|$ for the metric distance of the points. For a graph $G$, we
write $d_{G}(u,v)$ for the graph distance. For a reference on graph theory the
reader is directed to [10, 18], while [3] is a reference on normed spaces.

##  2\. Smoothly dense sets

In this section we define a property called smoothly dense, and show that
there is a graph $GR(\mathrm{SD})$ such that if $V$ is a smoothly dense set,
then for $p\in(0,1)$, a realization of $\mathrm{LARG}(V,p)$ is almost surely
isomorphic to $GR(\mathrm{SD})$. We will show that for suitable measures which
we define, almost all dense sets in the subspace of polynomials and in the
subspace of piecewise linear functions are smoothly dense.

We first give a corollary of Theorem 2.4 in [5] which demonstrates that there
is a close relationship between graph distance and metric distance in any
graph that is a geometric $1$-graph.

######  Corollary 1 ([5]).

Suppose $V$ and $W$ are countable dense subsets of a separable Banach space
$X$ such that graphs $\Gamma$ sampled from $\mathrm{LARG}(V,p)$ and
$\Gamma^{\prime}$ sampled from $\mathrm{LARG}(W,p^{\prime})$ with
$p,p^{\prime}\in(0,1)$ are almost surely isomorphic. If an isomorphism
$f\colon\Gamma\to\Gamma^{\prime}$ almost surely exists, then it has the
property that for every pair of vertices $u,v\in V,$

$\lfloor\|u-v\|\rfloor=\lfloor\|f(u)-f(v)\|\rfloor.$

Corollary 1 suggests the following generalization of isometry. Given metric
spaces $(S,d_{S})$ and $(T,d_{T})$, and subsets $V\subseteq S$ and $W\subseteq
T$, a _step-isometry_ from $V$ to $W$ is a bijective map $f:V\rightarrow W$
with the property that for every pair of vertices $u,v\in V$,

$\lfloor d_{S}(u,v)\rfloor=\lfloor d_{T}(f(u),f(v))\rfloor.$

It is evident that every isometry is a step-isometry. As one would expect, the
converse is false, but surprisingly, the paper [1] shows that for any finite-
dimensional Banach space that is not isometric to $\ell_{\infty}^{d}$, a step-
isometry between a pair of dense subsets is necessarily an isometry. Similar
results probably hold in infinite-dimensional separable Banach spaces, and
certainly hold in a separable Hilbert space.

We first introduce some terminology. For any $f\in C[0,1]$ the _remainder of_
$f$, written $\langle f\rangle$, is defined point-wise by

$\langle f\rangle(x)=\langle f(x)\rangle,$

where $\langle x\rangle=x-\left\lfloor x\right\rfloor$. For functions $f$ and
$g$ in $C[0,1]$, we say $f$ and $g$ _cross_ at $x$ if $\langle
f(x)\rangle=\langle g(x)\rangle$ and we define
$\mathsf{cr}(f,g)=\\{x\colon\langle f(x)\rangle=\langle g(x)\rangle\\}$. If
$A$ and $B$ are finite subsets of $[0,1]$, then we write $A\sim_{\epsilon}B$
if they have the same cardinality, and when comparing elements of the sets in
increasing order, for all $i$, the $i$th element of $A$ is within $\epsilon$
of the $i$th element of $B$.

A subset $\mathcal{F}$ of $C[0,1]$ is _transverse_ if it has the following
properties:

  1. (1)

The sets $\mathsf{cr}(f,g)$ are disjoint for distinct pairs
$f,g\in\mathcal{F}$;

  2. (2)

For any $f,g\in\mathcal{F}$, $\mathsf{cr}(f,g)$ is finite, does not contain 0
or 1, and if $t\in\mathsf{cr}(f,g)$, then $t$ is not a local extremum of
$f-g$.

One consequence of the set being transverse is that no two distinct elements
are at integer distance from each other. In that sense, it is a generalization
of the notion of integer distance free (idf) sets as defined in [5] for sets
in ${\mathbb{R}}^{n}$ and in [7] for sets of sequences.

A countable subset $V$ of $C[0,1]$ is said to be _smoothly dense_ if every
appropriate function in $C[0,1]$ can be approximated in such a way that the
crossing behaviour of the approximation with a given finite set of functions
mimics that of the original function. In addition, the functions in the set
must possess a number of nice qualities. In particular, each member must be
Lipschitz: a function is Lipschitz if there exists $K_{f}>0$ such that
$|f(x)-f(y)|\leq K_{f}|x-y|$ for each $x,y\in[0,1]$).

Precisely, a set $V$ is smoothly dense if it has the following properties:

  1. (1)

The set $V$ is dense in $C[0,1]$;

  2. (2)

The set $V$ is transverse;

  3. (3)

Each $f\in V$ is Lipschitz;

  4. (4)

For each finite subset $\mathcal{F}\subset V$, and each $f\in C[0,1]$ such
that $\mathcal{F}\cup\\{f\\}$ is transverse, and for each $\epsilon>0$, there
exists $g\in V$ such that:

    1. (a)

$\|f-g\|<\epsilon$.

    2. (b)

$\mathsf{cr}(f,h)\sim_{\epsilon}\mathsf{cr}(g,h)$ for all $h\in\mathcal{F}$.

The function $g$ is called a _smooth_ $\epsilon$-_approximation_ of $f$
relative to $\mathcal{F}$.

We will show in the last two subsections that smoothly dense sets not only
exist in $C[0,1]$, but they are abundant in each of the subspaces of piecewise
linear functions and polynomials. More precisely, we will define a measure so
that almost all countable, randomly chosen sets of piecewise linear functions
or polynomials are smoothly dense.

###  2.1. Smoothly dense sets are Rado

We begin with a lemma providing a crucial step in the inductive proof of graph
isomorphism. It states that, in smoothly dense sets, if we can find a smooth
$\epsilon$-approximation of a given function, then we can find infinitely many
such approximations, and at least one of them will have the correct adjacency
pattern with a given finite set of vertices.

######  Lemma 2.

Let $V$ be smoothly dense and $p\in(0,1)$. If $G$ is sampled from
$\mathrm{LARG}(V,p)$ then the following property almost surely holds:

For each finite subset $\mathcal{F}$ of $V$ and $f\in C([0,1])$ such that
$\mathcal{F}\cup\\{f\\}$ is transverse, for all
$\mathcal{G}\subseteq\mathcal{F}$ so that $\|f-h\|<1$ for all
$h\in\mathcal{G}$, for all $\epsilon>0$, there exists $g\in
V\backslash\mathcal{F}$ so that $g$ is a smooth $\epsilon$-approximation of
$f$ with respect to $\mathcal{F}$, and $g$ is adjacent to all vertices in
$\mathcal{G}$ and no vertex in $\mathcal{F}\setminus\mathcal{G}$.

###### Proof.

By the definition of smoothly dense, there exists a smooth
$\epsilon$-approximation of $f$ with respect to $\mathcal{F}$. In fact, by
decreasing $\epsilon$ we may find infinitely many such functions, and we may
ensure that each such function $g$ has the property that $\|g-h\|<1$ for all
$h\in\mathcal{G}$. Then for each such $g$, the probability of being correctly
joined is $p^{k}(1-p)^{\ell}$, where $k=|\mathcal{G}|$ and
$\ell=|\mathcal{F}-\mathcal{G}|$. We then observe that the probability of no
such function $g$ being correctly joined is $0$. ∎

Given functions $f,g\in C[0,1]$ and an interval $I\subseteq[0,1]$, we say that
$f<g$ on $I$ if, for all $x\in I$, $f(x)<g(x)$. Let $f>g$ on $I$ be similarly
defined. Given finite sets $\mathcal{F},\mathcal{G}\subseteq C[0,1]$, a
bijection $\varphi:\mathcal{F}\rightarrow\mathcal{G}$, and intervals
$I,J\subseteq[0,1]$, the map $\varphi$ is _order-preserving_ on $(I,J)$ if for
all $f,g\in\mathcal{F}$ we have that:

  1. (1)

For all $x\in I$ and $y\in J$, we have that $\left\lfloor
f(x)\right\rfloor=\left\lfloor\varphi(f)(y)\right\rfloor$; and

  2. (2)

The remainders of $f$ and $g$ are similarly ordered, i.e. either $\langle
f\rangle<\langle g\rangle$ on $I$ and
$\langle\varphi(f)\rangle<\langle\varphi(g)\rangle$ on $J$, or $\langle
f\rangle>\langle g\rangle$ on $I$ and
$\langle\varphi(f)\rangle>\langle\varphi(g)\rangle$ on $J$.

If a bijection $\varphi$ between sets of functions is given and there is no
ambiguity, then we will use $f^{*}$ to denote $\varphi(f)$.

######  Lemma 3.

Suppose $V\subseteq C[0,1]$ is smoothly dense,
$\mathcal{F},\mathcal{G}\subseteq V$ and we are given a bijection
$\varphi:\mathcal{F}\rightarrow\mathcal{G}$. Let
$X=\bigcup\limits_{f,g\in\mathcal{F}}\mathsf{cr}(f,g)\cup\\{0,1\\}$ and
$Y=\bigcup\limits_{f,g\in\mathcal{F}}\mathsf{cr}(f^{\ast},g^{\ast})\cup\\{0,1\\}$.
Suppose $|X|=|Y|=n+1$, and for $i=1,\dots n$, let $I_{i}=(x_{i-1},x_{i})$ and
$J_{i}=(y_{i-1},y_{i})$, where $x_{i}$, $y_{i}$ denote the $i$-th largest
element of $X$, $Y$, respectively. If for all $i$, $0<i\leq n$, $\varphi$ is
order-preserving on $(I_{i},J_{i})$, then $\varphi$ is a step-isometry.

###### Proof.

Let $x_{\max}$ be chosen so that $(f-g)(x_{\max})=\|f-g\|$. Note that
$x_{\max}$ cannot be in $X$ since $V$ is transverse. Hence, $x_{\max}$ must
lie in some interval $I_{i}$. Now take any point $y_{\max}\in J_{i}$.

For real numbers $a$ and $b$, knowing $\lfloor a\rfloor$, $\lfloor b\rfloor$
and whether $\langle a\rangle<\langle b\rangle$ or $\langle a\rangle>\langle
b\rangle$ is sufficient to determine $\lfloor|a-b|\rfloor$. Hence, from the
order-preserving property,

$\lfloor\|f-g\|\rfloor=\lfloor|f(x_{\max})-g(x_{\max})|\rfloor=\lfloor|f^{*}(y_{\max})-g^{*}(y_{\max})|\rfloor\leq\lfloor\|f^{*}-g^{*}\|\rfloor.$

A similar argument shows that
$\lfloor\|f^{*}-g^{*}\|\rfloor\leq\lfloor\|f-g\|\rfloor$. ∎

We now arrive at our main result of this section, that there is a unique
isomorphism type for LARG graphs on smoothly dense sets.

######  Theorem 4.

There exists a graph $GR(\rm{SD})$ such that for every countable smoothly
dense subset, $V$, of $C[0,1]$, and $p\in(0,1)$, $\mathrm{LARG}(V,p)$ is
almost surely isomorphic to $GR(\rm{SD})$.

###### Proof.

Let $V$ and $W$ be smoothly dense sets and let $p,p^{\prime}\in(0,1)$. Let $G$
be sampled from $\mathrm{LARG}(V,p)$ and $H$ be sampled from
$\mathrm{LARG}(W,p^{\prime})$. Using a back-and-forth argument, we will
construct a sequence of bijections $\varphi_{n}:V_{n}\rightarrow W_{n}$
between finite subsets of $V$ and $W$ such that $\varphi_{n}$ is an
isomorphism from $G[V_{n}]$ to $H[W_{n}]$ and $\varphi_{n+1}$ extends
$\varphi_{n}$.

Let $V=\\{g_{i}:i\geq 0\\}$ and $W=\\{h_{i}:i\geq 0\\}$. Without loss of
generality, assume $g_{0}$ is equal to the constant zero function (we may
achieve this by subtracting one function in $V$ from the remaining ones, which
does not affect any of our conditions). We may similarly assume $h_{0}$ is the
constant zero function.

We proceed by induction on $n\geq 0$. Set $V_{0}=\\{g_{0}\\}$ and
$W_{0}=\\{h_{0}\\}$ and let $\varphi_{0}(g_{0})=h_{0}$. Fix $n\geq 0$, and
assume $\varphi_{n}:V_{n}\rightarrow W_{n}$ is defined. (We use the notation
$f^{\ast}$ to denote $\varphi_{n}(f)$.) Our induction hypothesis consists of
the following items:

  1. (1)

$g_{n}\in V_{n}$ and $h_{n}\in W_{n}$;

  2. (2)

Let $X=\bigcup\limits_{f,g\in V_{n}}\mathsf{cr}(f,g)\cup\\{0,1\\}$ and
$Y=\bigcup\limits_{f,g\in W_{n}}\mathsf{cr}(f^{\ast},g^{\ast})\cup\\{0,1\\}$.
Then $|X|=|Y|$, and for $i=1,\dots m$, where $m+1=|X|$, let
$I_{i}=(x_{i-1},x_{i})$ and $J_{i}=(y_{i-1},y_{i})$, where $x_{i}$, $y_{i}$
denote the $i$th largest elements of $X$ and $Y$ respectively. (Starting at
$x_{0}=y_{0}=0$.) Then for all $i$, $0<i\leq m$, $\varphi_{n}$ is order-
preserving on $(I_{i},J_{i})$,

For the induction step, we go forth. Going back is analogous and so is
omitted. Let $g=g_{n+1}$ and assume $g\notin V_{n}$. Let the sets
$X=\\{x_{0},x_{1},\dots,x_{m}\\}$ and $Y=\\{y_{0},y_{1},\dots,y_{m}\\}$ be as
in item (2) of the induction hypothesis.

We build a continuous target function $t$, working separately on each $J_{i}$.
Fix $i$ such that $1\leq i\leq m$. Let
$q(y)=x_{i-1}+\frac{x_{i}-x_{i-1}}{y_{i}-y_{i-1}}(y-y_{i-1})$, that is the
increasing linear function that maps $J_{i}$ to $I_{i}$. Next, suppose that
$g$ crosses $V_{n}$ inside $I_{i}$ at points $x_{i,1},\ldots,x_{i,k-1}$ with
$x_{i-1}=:x_{i,0}<x_{i,1}<\ldots<x_{i,k-1}<x_{i,k}:=x_{i}$. On each interval,
$I_{i,l}=(x_{i,l-1},x_{i,l})$, let
$\gamma_{l}^{-}+n_{l}^{-}<g<\gamma_{l}^{+}+n_{l}^{+}$, where
$\gamma_{l}^{+},\gamma_{l}^{-}\in V_{n}$, $n_{l}^{+},n_{l}^{-}\in\mathbb{Z}$
and the left side is the maximal element of $V_{n}+\mathbb{Z}$ lying below $g$
on $I_{i,l}$, while the right side is the minimal such function lying above
$g$ on $I_{i,l}$.

Define
$\alpha(x)=(g(x)-(\gamma_{l}^{-}(x)+n_{l}^{-}))/((\gamma_{l}^{+}(x)+n_{l}^{+})-(\gamma_{l}^{-}(x)+n_{l}^{-}))$,
so that $0<\alpha(x)<1$ on $I_{i,l}$. By definition, $g$ crosses either
$\gamma_{l}^{+}+n_{l}^{+}$ or $\gamma_{l}^{-}+n_{l}^{-}$ at $x_{i,l}$ and
$x_{i,l+1}$. Thus, $\alpha(x_{i,l})\in\\{0,1\\}$ and
$\alpha(x_{i,l+1})\in\\{0,1\\}$, and there are four different possibilities
for the crossing behaviour of $g$ with respect to $\gamma^{+}_{l}+n^{+}_{l}$
and $\gamma^{-}_{l}+n_{l}^{-}$. However, in each case,
$g(x)=\alpha(x)(\gamma_{l}^{+}+n_{l}^{+})+(1-\alpha(x))(\gamma_{l}^{-}+n_{l}^{-})$.

Let $J_{i,l}=q^{-1}(I_{i,l})$ We then define the target function on $J_{i,l}$
by

$t(y)=\alpha(q(y))\big{(}{\gamma^{+}_{l}}^{*}(q(y))+n_{l}^{+}\big{)}+(1-\alpha(q(y)))\big{(}{\gamma^{-}_{l}}^{*}(q(y))+n_{l}^{-}\big{)},$

so that $t(y)$ sits between the images of integer translates of
${\gamma^{-}_{l}}^{*},\,{\gamma^{+}_{l}}^{*}$ on $J_{i,l}$ as $g(y)$ sits
between the corresponding integer translates of
$\gamma^{+}_{l},\,\gamma^{-}_{l}$ on $I_{i,l}$. This is illustrated in Figure
1.

$x_{i-1}$$x_{i,1}$$y_{i-1}$$y_{i,1}$$x_{i}$$x_{i,2}$$y_{i,2}$$y_{i}$$\gamma_{1}^{+}+n_{+}$$\gamma_{1}^{-}+n_{-}$${\gamma_{1}^{+}}^{*}+n_{+}$${\gamma_{1}^{-}}^{*}+n_{-}$

Figure 1. Schematic illustrating the new function to be added to
$\mathcal{F}$, $f$ (in bold) on an interval $[x_{i-1},x_{i}]$; and the
function $t$ (also bold) on $[y_{i-1},y_{i}]$ which is a “target” for $f$ to
be matched to.

Define $\tilde{\varphi}\colon V_{n}\cup\\{g\\}\to W_{n}\cup\\{t\\}$. The
construction above ensures that $\tilde{\varphi}$ is order-preserving. Also,
$W_{n}\cup\\{t\\}$ is clearly transverse. Let $\mathcal{G}=\\{g_{j}\in
W_{n}\colon g_{j}\sim g\\}$. Since $W$ is smoothly dense, Lemma 2 ensures for
any $\epsilon>0$, the existence of an $h\in W$ that is a smooth
$\epsilon$-approximation of $t$ with respect to $W_{n}$ that is adjacent to
$\mathcal{G}$ but not to $W_{n}\setminus\mathcal{G}$. By choosing $\epsilon$
sufficiently small, we are guaranteed that $\bar{\varphi}\colon
V_{n}\cup\\{g\\}\to W_{n}\cup\\{h\\}$ is order-preserving. ∎

###  2.2. Piecewise linear functions

Define the set of _piecewise linear functions_ in $[0,1]$, written
$\mathsf{PL}[0,1]$, to be continuous functions with graphs consisting of
finitely many line segments. Note that by a standard argument, the subspace
$\mathsf{PL}[0,1]$ is dense in $C[0,1]$.

A function $f$ in $\mathsf{PL}[0,1]$ is completely defined by a sequence of
_change points_ $(c^{f}_{i})_{i=0}^{n+1}$, which is the collection of points
in the graph of $f$ where the slope of $f$ changes, or meets the boundaries
$x=0$ or $x=1$. Precisely, for all $i$, $i=0,\dots,n+1$,
$c^{f}_{i}\in[0,1]\times{\mathbb{R}}$, and the graph of $f$ consists of the
line segments connecting $c^{f}_{i}$ to $c^{f}_{i+1}$ for all $i$. Thus, we
assume the change points to be ordered according to their $x$-coordinate.
Precisely, $c^{f}_{i}=(x_{i},y_{i})$, where $0=x_{0}<x_{1}<\dots<x_{n+1}=1$.
If $f\in\mathsf{PL}[0,1]$, then we write $\mathsf{CP}(f)$ (for change points)
for the sequence of $x$-coordinates of the change points.

We define a measure on $C[0,1]$ supported on $\mathsf{PL}[0,1]$. For
$n\in\mathbb{N}_{0}$, and sequences $(x_{i})_{i=0}^{\infty}$ of distinct
points in $(0,1)$ and $(y_{i})_{i=0}^{\infty}$ of points in $\mathbb{R}$, let
$\varphi(n,(x_{i}),(y_{i}))$ be the function defined by change points
$(c_{i})_{i=0}^{n+1}$ where $c_{0}=(0,y_{0})$, $c_{n+1}=(1,y_{n+1})$, and, for
all $1\leq i\leq n$, $c_{i}=(\hat{x}_{i},y_{i})$, where $\hat{x}_{i}$ is the
$i$-th largest element of $\\{x_{1},\dots,x_{n}\\}$.

We then equip
$\mathbb{N}_{0}\times[0,1]^{\mathbb{N}}\times\mathbb{R}^{\mathbb{N}}$ with the
probability measure where the first coordinate is Poisson with mean 1; the
middle coordinates are independent and uniform on $[0,1]$ and the remaining
coordinates are independent standard normal. We write $\mathbb{P}$ for this
measure on
$\mathbb{N}_{0}\times[0,1]^{\mathbb{N}}\times\mathbb{R}^{\mathbb{N}}$. Since
$\Phi$ is measurable, this distribution pushes forward to a measure
${\mathbb{P}}_{\mathsf{P}L}$ on $\mathsf{PL}[0,1]$. That is, if $S$ is a
subset of $\mathsf{PL}[0,1]$, then ${\mathbb{P}}_{\mathsf{P}L}(S)$ is defined
to be
$\mathbb{P}\big{(}\\{n,(x_{i});(y_{i})\\}\colon\Phi(n,(x_{i}),(y_{i}))\in
S\big{)}$ (in particular,
${\mathbb{P}}_{\mathsf{P}L}=\mathbb{P}\circ\Phi^{-1}$).

We will prove that, a countable collection of piecewise linear functions, each
sampled independently from ${\mathbb{P}}_{\mathsf{P}L}$ is almost surely
smoothly dense. First we state and prove a simple lemma about real-valued
random variables. A real-valued random variable $X$ is said to be _continuous_
if $\mathbb{P}(X=a)=0$ for each $a\in\mathbb{R}$. It is said to be _absolutely
continuous_ if $\mathbb{P}(X\in A)=0$ for each subset $A$ of $\mathbb{R}$ of
Lebesgue measure 0.

######  Lemma 5.

If $X$ and $Y$ are independent random variables with absolutely continuous
distribution on $\mathbb{R}$, then $\mathbb{P}(X=Y)=0$.

In fact, we prove the stronger statement that even if just $X$ has a
continuous (not necessarily absolutely continuous) distribution, then
$\mathbb{P}(X=Y)=0$.

###### Proof.

For any value $y$, conditioning on the event $\\{Y=y\\}$, since $X$ has a
continuous distribution, we have $\mathbb{P}(X=Y|Y=y)=0$. It follows that the
unconditional probability, $\mathbb{P}(X=Y)$ satisfies

$\mathbb{P}(X=Y)=\int\mathbb{P}(X=y|Y=y)f_{Y}(y)\,dy=0,$

and the proof follows. ∎

We note that the argument above (that if some conditional probability vanishes
whenever one conditions on any value of one of the random variables occurring
in a condition, then that unconditional probability also vanishes) recurs
throughout.

######  Lemma 6.

Let $X_{1},X_{2},X_{3},X_{4}$ be independent absolutely continuously
distributed random variables and $a_{1},a_{2}$ be distinct real numbers. Then
any of $\frac{X_{4}-X_{3}}{X_{2}-X_{1}}$, $\frac{X_{4}-X_{3}}{a_{2}-X_{1}}$,
$\frac{X_{4}-X_{3}}{X_{2}-a_{1}}$, $\frac{X_{4}-X_{3}}{a_{2}-a_{1}}$ are
absolutely continuously distributed on $\mathbb{R}$.

###### Proof.

It is straightforward to see that for $b\neq 0$ and $a\in\mathbb{R}$,
$(X_{4}-a)/b$ has an absolutely continuous distribution. Let $G$ be the almost
sure event where $X_{2}\neq X_{1}$, $X_{2}\neq a_{1}$ and $X_{1}\neq a_{2}$.
On the event $G$, conditioned on $X_{1},X_{2},X_{3}$, the slopes in the
statement of the lemma all have absolutely continuous distributions. Since the
conditional distributions are absolutely continuous, the unconditional
distributions are also absolutely continuous. ∎

For $f\in\mathsf{PL}[0,1]$, let $\textsf{Slope}(f)$ be the (finite) set of
slopes that $f$ assumes. Since the coordinates of the change points of a
function chosen according to ${\mathbb{P}}_{\mathsf{P}L}$ are continuous
random variables, by Lemma 6, for a given function $g\in\mathsf{PL}$ and
randomly chosen $f$, the probability (under ${\mathbb{P}}_{\mathsf{P}L}$) that
$\textsf{Slope}(f)$ intersects $\textsf{Slope}(g)$ is 0.

We now arrive at the main result of this subsection.

######  Theorem 7.

For ${\mathbb{P}}_{\mathsf{P}L}^{\mathbb{N}}$-almost every sequence
$(f_{n})_{n\in\mathbb{N}}$, the set $V=\\{f_{1},f_{2},\ldots\\}$ is smoothly
dense.

###### Proof.

We first show that ${\mathbb{P}}_{\mathsf{P}L}^{\mathbb{N}}$-a.e. $V$ is
dense. Let $f\in C[0,1]$ and let $\epsilon>0$. As mentioned at the beginning
of this section, $\mathsf{PL}[0,1]$ is dense in $C[0,1]$. Let
$\varphi\in\mathsf{PL}[0,1]$ be so that $\|\varphi-f\|<\frac{\epsilon}{2}$.
Let $\mathsf{CP}(\varphi)=(c^{\varphi}_{i})_{i=0}^{n+1}$, where
$c_{i}^{\varphi}=(x_{i},y_{i})$ for $i=0,\dots,n+1$. We have that
$\Phi(n,(\tilde{x}_{i}),(\tilde{y}_{i}))=\varphi$ whenever
$\tilde{y}_{i}=y_{i}$ for $i=0,\dots,n+1$ and $x_{i}$ is the $i$-th largest
element of $\\{\tilde{x}_{1},\dots,\tilde{x}_{n}\\}$, and in particular, if
$\tilde{x}_{i}=x_{i}$ for $i=1,\dots,n$. Now there exists a $\delta>0$ such
that if $|\tilde{x}_{i}-x_{i}|<\delta$ for $i=1,\ldots,n$ and
$|\tilde{y}_{i}-y_{i}|<\delta$ for $i=0,\ldots,n+1$, then
$\|\Phi(n,(\tilde{x}_{i}),(\tilde{y}_{i}))-\varphi\|<\frac{\epsilon}{2}$.
Since the set
$\\{(n,(\tilde{x}_{i}),(\tilde{y}_{i}))\colon|\tilde{x}_{i}-x|<\delta\text{
for $i=1,\ldots,n$ and $|\tilde{y}_{i}-y|<\delta$ for $i=0,\ldots,n+1$}\\}$
has positive measure with respect to
$\mathsf{Pois}(1)\times\mathsf{Unif[0,1]}^{\mathbb{N}}\times\mathsf{Norm(0,1)}^{\mathbb{N}_{0}}$,
$V$ almost surely contains a $g$ such that $\|g-f\|<\epsilon$ by the second
Borel-Cantelli lemma.

Next, we show that $V$ is transverse. Notice that if $f$ and $g$ are piecewise
linear functions, then provided no piece of $f$ has the same slope as a piece
of $g$, then $\langle f\rangle$ and $\langle g\rangle$ have only finitely many
intersections. Now fix a function $f\in\mathsf{PL}[0,1]$. By Lemma 6,
conditional on $\\{f_{i}=f\\}$, the probability that $\textsf{Slope}(f_{j})$
intersects $\textsf{Slope}(f_{i})$ is 0. Hence, the unconditional probability
is also zero, so that with probability 1, all pairs of functions in $V$ have
disjoint slope sets. Hence, almost surely $\mathsf{cr}(f_{i},f_{j})$ is finite
for all $i\neq j$. Since $f_{i}(0)$ and $f_{j}(0)$ are independently normally
distributed, the probability of a crossing at 0 is zero and similarly at 1.
For a fixed $f\in\mathsf{PL}[0,1]$ and for any other $g\in\mathsf{PL}[0,1]$
with distinct slopes, any extremum of $f-g$ occurs at a change point of $f$ or
$g$. By a similar argument to the above, the probability that $g$ differs from
$f$ by an integer at an element of $\mathsf{CP}(f)$ is 0. Likewise, the
probability that $f$ differs from $g$ by an integer at an element of
$\mathsf{CP}(g)$ is 0. Hence, condition (2) of the definition of
transversality is almost surely satisfied.

Similarly, for any finite subsets $A=\\{t_{1},\ldots,t_{l}\\}$ of $[0,1]$ and
$B=\\{s_{1},\ldots,s_{l}\\}$ of $[0,1)$, then
${\mathbb{P}}_{\mathsf{P}L}(\\{\langle f(t_{i})\rangle=s_{i}\text{ for some
$i$}\\})$ is zero. Hence, conditional on $\\{f_{i}=f\\}$ and $\\{f_{j}=g\\}$
where $f,g\in\mathsf{PL}[0,1]$, ${\mathbb{P}}_{\mathsf{P}L}(\\{\langle
f_{k}(t)\rangle=\langle f(t)\rangle\text{ for some
$t\in\mathsf{cr}(f,g)$}\\})=0$. This shows that conditional on $f_{i}$ and
$f_{j}$, the probability that $f_{i}$, $f_{j}$ and $f_{k}$ have a common
crossing is 0. The unconditional probability that three functions have a
common crossing is therefore 0. Similarly conditioned on $f_{i}$ and $f_{j}$,
the probability that $f_{k}$ and $f_{l}$ have a crossing at an element of
$\mathsf{cr}(f_{i},f_{j})$ is 0, so that condition (1) of the definition of
transversality is almost surely satisfied and $V$ is transverse with
probability 1.

Since every piecewise linear function is Lipschitz, smoothly dense condition
(3) is automatically satisfied. We finish the proof by showing that $V$
satisfies smoothly dense condition (4). Let $f\in C[0,1]$ and
$\mathcal{F}=\\{f_{1},\ldots,f_{r}\\}\subset V$ and suppose that
$\mathcal{F}\cup\\{f\\}$ is transverse. Let $K$ be such that each element of
$\mathcal{F}$ is Lipschitz with Lipschitz constant at most $K$. Let
$\epsilon>0$. Let $C_{j}=\mathsf{cr}(f_{j},f)$. By assumption, $C_{j}$ does
not contain any extrema of $f-f_{j}$. Let
$C_{j}=\\{t_{j,1},\ldots,t_{j,n_{j}}\\}$ and let
$f(t_{j,m})-f_{i_{j}}(t_{j,m})=a_{j,m}\in\mathbb{Z}$. For any $m$, by
transversality of $\mathcal{F}\cup\\{f\\}$, we have that $t_{j,m}$ is not an
extremum of $f-f_{j}$, and thus $f-f_{j}-a_{j_{m}}$ is negative on one side of
$t_{j,m}$ and positive on the other. Let $\delta_{j,m}<\epsilon$ be such that:

  1. (1)

$\bigcup_{i=1}^{r}C_{i}\cap[t_{j,m}-2\delta_{j,m},t_{j,m}+2\delta_{j,m}]=\\{t_{j,m}\\}$;

  2. (2)

$f-f_{j}-a_{j,m}$ takes one sign on the entire interval
$[t_{j,m}-\delta_{j,m},t_{j,m}]$ and the opposite sign on the interval
$[t_{j,m},t_{j,m}+\delta_{j,m}]$.

Let $\eta=\frac{1}{2}\min\\{d(f(x)-f_{i}(x),\mathbb{Z}):i\neq j\text{ and
}x\in[t_{j,m}-\delta_{j,m},t_{j,m}+\delta_{j,m}]\\}$. That is, $\eta$ is
chosen so that any function $\tilde{f}$ within distance $\eta$ of $f$ on the
intervals around the $t_{j,m}$ will be so that
$\lfloor\tilde{f}-f_{i}\rfloor=\lfloor f-f_{i}\rfloor$ for all
$f_{i}\in\mathcal{F}\setminus\\{f_{j}\\}$ on these intervals.

We define a target function, $\tilde{f}$ on
$I_{j,m}=[t_{j,m}-\delta_{j,m},t_{j,m}+\delta_{j,m}]$ such that:

  1. (1)

$\tilde{f}$ agrees with $f$ at $t_{j,m}\pm\delta_{j,m}$;

  2. (2)

$\tilde{f}$ is linear with slope $\pm(K+2)$ on a neighbourhood $N_{j,m}$ of
$t_{j,m}$ (so that $\tilde{f}$ crosses $f_{j}$ in the same direction that $f$
does at $t_{j,m}$);

  3. (3)

$\|(\tilde{f}-f)|_{I_{j,m}}\|<\eta$;

  4. (4)

$\tilde{f}-f_{j}-a_{j,m}$ has the same sign as $f-f_{j}-a_{j,m}$ on $I_{j,m}$.

Finally, let $\tilde{f}$ be defined to be equal to $f$ on
$[0,1]\setminus\bigcup_{j,m}I_{j,m}$. Let $\zeta<1$ be such that
$d(\tilde{f}(t)-f_{j}(t),\mathbb{Z})\geq 2\zeta$ for each $j=1,\ldots,r$ and
all $t$ outside $\bigcup_{j,m}N_{j,m}$.

Let $g$ be any function satisfying:

  1. (1)

$\|g-\tilde{f}\|<\zeta$;

  2. (2)

$|g^{\prime}-\tilde{f}^{\prime}|<1$ on $N_{j,m}$ for each $j,m$.

Then we claim that $\mathsf{cr}(g,f_{j})\sim_{\epsilon}\mathsf{cr}(f,f_{j})$
for $j=1,\ldots,r$. To see this, note that the first condition ensures that no
crossings are created outside $\bigcup N_{j,m}$. Since
$|g^{\prime}-\tilde{f}^{\prime}|<1$ on $\bigcup N_{j,m}$ and $\tilde{f}-f_{j}$
is monotone on $N_{j,m}$, we find that $g$ crosses $f_{j}$ at most once on
each $N_{j,m}$. Finally, we observe that since $g$ starts on one side of
$f_{j}$ and ends on the other, the Intermediate Value Theorem ensures that
there is at least one (and thus, exactly one) crossing of $g$ with $f_{j}$ in
each $N_{j,m}$, ensuring that
$\mathsf{cr}(g,f_{j})\sim_{\epsilon}\mathsf{cr}(f,f_{j})$.

Finally, we observe that the above conditions are satisfied for a collection
of piecewise linear functions with change points in a set of positive measure.
Hence, by the second Borel-Cantelli lemma, there are infinitely many $g\in V$
satisfying $\|f-g\|<\epsilon$ and
$\mathsf{cr}(f,h)\sim_{\epsilon}\mathsf{cr}(g,h)$ for all $h\in\mathcal{F}$. ∎

###  2.3. Polynomials

We equip $\mathbb{N}_{0}\times\mathbb{R}^{\mathbb{N}_{0}}$ with the
probability measure
$\mathsf{Pois}(1)\times\mathsf{Norm}(0,1)^{\mathbb{N}_{0}}$ and, for any
sequence $(a_{i})_{i\in\mathbb{N}_{0}}$, let $\Phi(n,(a_{i}))$ be the
polynomial $\varphi(t)=a_{0}+a_{1}t+\ldots+a_{n}t^{n}$. The map $\Phi$ pushes
forward the measure on parameters to a measure $\mathbb{P}_{\text{poly}}$ on
$C[0,1]$.

######  Theorem 8.

For $\mathbb{P}_{\text{poly}}^{\mathbb{N}}$-almost every sequence
$(f_{n})_{n\in\mathbb{N}}$, the set $V=\\{f_{1},f_{2},\ldots\\}$ is smoothly
dense.

###### Proof.

We first show that $V$ is dense. By Weierstrass’s theorem, the collection of
polynomials is uniformly dense in $C[0,1]$. Given $f\in C[0,1]$ and
$\epsilon>0$, let function $\varphi$ given by
$\varphi(t)=a_{0}+a_{1}t+\ldots+a_{n}t^{n}$ satisfy
$\|f-\varphi\|<\frac{\epsilon}{2}$. Now
$\\{(n;(b_{i})_{i\in\mathbb{N}_{0}})\colon|b_{i}-a_{i}|\leq\epsilon/(2(n+1))\text{
for }i=0,\ldots,n\\}$ has positive measure and any polynomial with these
parameters is $\frac{\epsilon}{2}$-close to $\varphi$, and so $\epsilon$-close
to $f$. Hence, as before, $V$ is almost surely dense in $C[0,1]$.

Next, we show that $V$ is transverse. Recall that for any two polynomials
$f_{1}$ and $f_{2}$ that differ in at least one non-constant coefficient,
$\mathsf{cr}(f_{1},f_{2})$ is finite (if $f_{1}$ and $f_{2}$ are both constant
polynomials, then they almost surely have no crossings). Conditional on the
non-constant coefficients of a third polynomial $f_{3}$, the probability that
its fractional part agrees with that of $f_{1}$ and $f_{2}$ at an element of
$\mathsf{cr}(f_{1},f_{2})$ is 0. Similarly, conditioned on $f_{1}$ and
$f_{2}$, the probability that two further polynomials $f_{3}$ and $f_{4}$
cross at an element of $\mathsf{cr}(f_{1},f_{2})$ is 0. Hence, condition (1)
of transversality holds.

Given a polynomial $f$, and the non-constant coefficients of a polynomial $g$,
the conditional probability that $f$ and $g$ cross at 0 or 1 is zero. Hence,
the unconditional probability is also 0, so that almost surely
$\mathsf{cr}(f,g)$ is finite and does not contain 0 or 1. Given the non-
constant coefficients of $g$, provided $f$ and $g$ are not constant
polynomials, $f-g$ has finitely many critical points. Now the conditional
probability that when the constant term is added to $g$, that $f$ and $g$
cross at one of these critical points is 0. Hence, almost surely
$\mathsf{cr}(f,g)$ does not contain any critical points of $f-g$ (in case $f$
and $g$ are constant, $\mathsf{cr}(f,g)$ is almost surely empty). Hence,
condition (2) of transversality holds, so that $V$ is almost surely a
transverse subset of $C[0,1]$.

It is evident all polynomials are Lipschitz on $[0,1]$, and so the smoothly
dense condition (3) is satisfied. The proof that $V$ satisfies smoothly dense
condition (4) is almost exactly the same as that given for piecewise linear
functions above. Namely, we identify neighbourhoods $N_{j,m}$ around the
crossing points $t_{j,m}$ of $f$ with all functions in the given set
$\mathcal{F}$. We define a smooth target function $\tilde{f}$ which has the
same crossing behaviour as $f$, but crosses steeply, with slope exceeding that
of any function in $\mathcal{F}$. We need to show that the conditions:

  1. (1)

$\|g-\tilde{f}\|<\zeta$;

  2. (2)

$|g^{\prime}(x)-\tilde{f}^{\prime}(x)|<1$ for all $x\in\bigcup N_{j,m}$ (with
$N_{j,m}$ as in the previous subsection)

are satisfied by a collection of polynomials in a set of parameters of
positive measure (since all of these functions have the required property that
their crossings with $\mathcal{F}$ are close to those of $f$). To see this,
let $h_{1}$ be a continuously differentiable function agreeing with
$\tilde{f}$ on $\bigcup N_{j,m}$, and differing from $\tilde{f}$ by at most
$\frac{\zeta}{4}$ elsewhere (such functions exist by density of the
continuously differentiable functions in the continuous functions). Now, let
$h_{2}(x)=a_{1}+a_{2}x+\ldots a_{n}x^{n-1}$ be a polynomial differing from
$h_{1}^{\prime}$ by at most $\frac{\zeta}{4}$. Finally, we claim that any
polynomial $g(x)=b_{0}+b_{1}x+\ldots b_{n}x^{n}$ satisfies the required
conditions if $|b_{0}-\tilde{f}(0)|<\frac{\zeta}{4}$ and
$|kb_{k}-a_{k}|<\frac{\zeta}{4n}$ for $k=1,\ldots n$. To see this, notice that
if these conditions are satisfied, then
$|g^{\prime}(x)-h_{2}(x)|\leq\frac{\zeta}{4}$ for each $x\in[0,1]$, so that
$|g^{\prime}(x)-h_{1}^{\prime}(x)|\leq\frac{\zeta}{2}$ for each $x$. Since
$|g(0)-h_{1}(0)|\leq\frac{\zeta}{4}$, we derive that
$|g(x)-h_{1}(x)|\leq\frac{3\zeta}{4}$ for each $x$ and so
$|g(x)-\tilde{f}(x)|\leq\zeta$ for each $x$.

On $\bigcup N_{j,m}$, we have $h_{1}^{\prime}=\pm(K+2)$ and
$\|h_{1}^{\prime}-g^{\prime}\|<\frac{\zeta}{2}$ so that $|h_{1}^{\prime}|>K+1$
on $\bigcup N_{j,m}$. This is sufficient to ensure that $g$ crosses
$f_{i_{j}}$ at most once and the intermediate value theorem ensures that $g$
crosses $f_{i_{j}}$ on $N_{j,m}$.

As before, these conditions are satisfied by a collection of polynomials with
parameters lying in a set of positive measure. It follows by the second Borel-
Cantelli lemma that $V$ contains infinitely many polynomials with the correct
crossings. Hence, $V$ is almost surely smoothly dense. ∎

######  Corollary 9.

If $V$ is a countable set of independently sampled functions from
$\mathbb{P}_{\text{poly}}$ or $\mathbb{P}_{\mathsf{PL}}$, then for all
$p\in(0,1)$, a graph sampled form $\mathrm{LARG}(V,p)$ is almost surely
isomorphic to $GR(\mathrm{SD})$.

##  3\. IC-dense sets and Brownian motion

By definition, smoothly dense sets must contain functions that are relatively
smooth, have finitely many extrema, and cross finitely often with other
functions in the set. In this section, we extend our results to functions in
$C[0,1]$ that exhibit the opposite type of behaviour: pairs of functions cross
infinitely often. We will call sets of such functions _infinite crossing
dense_ (IC-dense). An example of such functions is formed by Brownian motions.
We will first show that any two LARG graphs with IC-dense vertex sets are
almost surely isomorphic. Then, we will define a natural probability measure
on the set of Brownian motions, and show that under this measure almost all
countable sets of Brownian motions are IC-dense.

A countable subset $V$ of $C[0,1]$ will be called _IC-dense_ if it has the
following properties:

  1. (1)

The set $V$ is dense in $C[0,1]$;

  2. (2)

The sets $\mathsf{cr}(f,g)$ are disjoint for distinct pairs $f,g\in V$;

  3. (3)

For any $f,g\in V$, $\mathsf{cr}(f,g)$ does not contain 0 or 1;

  4. (4)

For each distinct pair $f,g\in V$, if $\langle f(x)\rangle=\langle
g(x)\rangle$ for $x\in(0,1)$, then there exists a sequence of points $x_{n}$
converging to $x$ monotonically such that $\langle f(x_{2n})\rangle<\langle
g(x_{2n})\rangle$ and $\langle f(x_{2n+1})\rangle>\langle g(x_{2n+1})\rangle$
for each $n$.

Note that the fact that the functions are continuous implies that
$\mathsf{cr}(f,g)$ is closed for each $f,g\in V$.

###  3.1. IC-dense sets are Rado

We will now show that IC-dense sets are Rado. As in the case for smoothly
dense sets, the proof is based on the inductive construction of a graph
isomorphism. But whereas in the smoothly dense case we required that the
isomorphism exactly preserves the crossing behaviour of the functions, here we
wish to preserve the decomposition of the interval $[0,1]$ into subintervals
where pairs of functions cross infinitely often. Before we state the main
theorem, we give definitions and useful lemmas.

Given finite sequences of real numbers $x_{1},\ldots,x_{k}$; and
$y_{1},\ldots,y_{k}$, we say they have the same _circular order_ if for any
$a$, $b$, $c$ in $\\{1,\ldots,k\\}$, the orientation of $\langle
x_{a}\rangle$, $\langle x_{b}\rangle$ and $\langle x_{c}\rangle$ on the circle
is the same as that of $\langle y_{a}\rangle$, $\langle y_{b}\rangle$ and
$\langle y_{c}\rangle$. We write $x_{a}\prec x_{b}\prec x_{c}\prec x_{a}$ if
$\langle x_{a}\rangle$, $\langle x_{b}\rangle$ and $\langle x_{c}\rangle$
occur in a positive orientation on the circle.

It is easy to see that a function $f$ defined by $f(x_{i})=y_{i}$ for
$i=1,\dots,k$ is a step-isometry if $\lfloor x_{i}\rfloor=\lfloor
y_{i}\rfloor$ and $x_{1},\ldots,x_{k}$ and $y_{1},\ldots,y_{k}$ have the same
circular order. In the induction step of the isomorphism proof we will
preserve the circular orders of the functions that have already been mapped.

Crossing partitions. If $\mathcal{F}$ is a finite IC-dense subset of $C[0,1]$,
then we build a finite partition of $[0,1]$ into open and closed sub-intervals
by the following procedure. Let

$a_{1}=\min\\{x\in[0,1]\colon\langle g(x)\rangle=\langle h(x)\rangle\text{ for
some distinct }g,h\in\mathcal{F}\\}.$ (1)

Suppose $a_{1},\ldots,a_{n}$ have been found, and let
$(g_{i},h_{i})_{i=1}^{n}$ be pairs of distinct elements of $\mathcal{F}$ so
that $\langle g_{i}(a_{i})\rangle=\langle h_{i}(a_{i})\rangle$ for each $1\leq
i\leq n$. Then define

$\displaystyle a_{n+1}=\min\big{\\{}x\in(a_{n},1]\colon$ $\displaystyle\langle
h(x)\rangle=\langle g(x)\rangle\text{ for some }g,h\in{\mathcal{F}}$ (2)
$\displaystyle\text{such that }\\{g,h\\}\neq\\{g_{n},h_{n}\\}\big{\\}}.$ (3)

If $a_{n+1}$ is defined (that is, the set is not empty), then set $g_{n+1}=g$
and $h_{n+1}=h$. If not, then the procedure terminates with $a_{n}$.

######  Lemma 10.

The procedure to generate the sequence $(a_{n})$ as defined in (1) and (2)
terminates in a finite number of steps.

###### Proof.

Suppose for a contradiction that there are infinitely many $a_{n}$’s. Since
$(a_{n})$ is an increasing sequence lying in $[0,1]$, let its limit be $a$. By
the Pigeonhole Principle, there are functions $f^{1}$, $f^{2}$, $f^{3}$ and
$f^{4}$ in $\mathcal{F}$ (not necessarily distinct, but such that $f^{1}\neq
f^{2}$, $f^{3}\neq f^{4}$ and $\\{f_{1},f_{2}\\}\neq\\{f_{3},f_{4}\\}$) and a
subsequence $(n_{j})$ such that $\\{g_{n_{j}},h_{n_{j}}\\}=\\{f^{1},f^{2}\\}$
and $\\{g_{n_{j}+1},h_{n_{j}+1}\\}=\\{f^{3},f^{4}\\}$ for all $j$. We have
$\langle f^{1}(a_{n_{j}})\rangle=\langle f^{2}(a_{n_{j}})\rangle$ and $\langle
f^{3}(a_{n_{j}+1})\rangle=\langle f^{4}(a_{n_{j}+1})\rangle$ for each $j$.
Taking a limit, and using continuity of the functions involved, we see that
$\langle f^{1}(a)\rangle=\langle f^{2}(a)\rangle$ and $\langle
f^{3}(a)\rangle=\langle f^{4}(a)\rangle$. That is,
$a\in\mathsf{cr}(f^{1},f^{2})\cap\mathsf{cr}(f^{3},f^{4})$. This contradicts
the IC-dense condition (2), establishing the above procedure terminates as
required. ∎

Now for each $i$ such that $a_{i}$ is defined, let
$b_{i}=\max\\{x\in[a_{i},a_{i+1}]\colon\langle g_{i}(x)\rangle=\langle
h_{i}(x)\rangle\\}$. Note that, since $\mathsf{cr}(g_{i},h_{i})$ is closed,
this maximum is defined, and since $h_{i}$ and $g_{i}$ cross at $b_{i}$ and a
different pair $h_{i+1},g_{i+1}$ crosses at $a_{i+1}$, we have that
$b_{i}<a_{i+1}$. The _crossing partition_ $\mathcal{P}(\mathcal{F})$ is then
given by

$\mathcal{P}(\mathcal{F})=\\{[0,a_{1}),[a_{1},b_{1}],(b_{1},a_{2}),[a_{2},b_{2}],\ldots,[a_{n},b_{n}],(b_{n},1]\\},$

so that on the (relatively) open sets $[0,a_{1})$, $(b_{1},a_{2})$, …,
$(b_{n-1},a_{n})$ and $(b_{n},1]$, there are no crossings and the functions in
$\mathcal{F}$ maintain a fixed circular order, while on $[a_{i},b_{i}]$, the
order between $g_{i}$ and $h_{i}$ switches infinitely many times (on any
neighbourhood of $a_{i}$ or $b_{i}$), while the circular order of
$\mathcal{F}\setminus\\{g_{i}\\}$ and $\mathcal{F}\setminus\\{h_{i}\\}$
remains fixed. The closed intervals $[a_{i},b_{i}]$ are called the crossing
intervals.

Given infinite graphs $G$ and $H$ on vertex sets $V$ and $W$, respectively,
and sets $\mathcal{F}=\\{F_{1},\ldots,F_{n}\\}\subseteq V$ and
$\mathcal{G}=\\{G_{1},\ldots,G_{n}\\}\subseteq W$ are _suitably matched_ if:

  1. (1)

For each $i$ and $j$, $F_{i}$ and $F_{j}$ are joined by an edge if and only if
$G_{i}$ and $G_{j}$ are joined by an edge;

  2. (2)

For each $i$ and $j$,
$\lfloor|F_{i}(0)-F_{j}(0)|\rfloor=\lfloor|G_{i}(0)-G_{j}(0)|\rfloor$ and
$F_{i}(0)<F_{j}(0)$ if and only if $G_{i}(0)<G_{j}(0)$;

  3. (3)

    1. (a)

If the crossing partition $\mathcal{P}(\mathcal{F})$ consists of $2n+1$
intervals of the form
$\\{[0,a_{1}),[a_{1},b_{1}],(b_{1},a_{2}),[a_{2},b_{2}],\ldots,[a_{n},b_{n}],(b_{n},1]\\}$,
then $\mathcal{P}(\mathcal{G})$ also consists of $2n+1$ intervals of the same
form. Call them

$\\{[0,a^{\prime}_{1}),[a^{\prime}_{1},b^{\prime}_{1}],(b^{\prime}_{1},a^{\prime}_{2}),[a^{\prime}_{2},b^{\prime}_{2}],\ldots,[a^{\prime}_{n},b^{\prime}_{n}],(b^{\prime}_{n},1]\\};$

    2. (b)

$F_{i}$ and $F_{j}$ cross on interval $[a_{k},b_{k}]$ if and only if $G_{i}$
and $G_{j}$ cross on $[a^{\prime}_{k},b^{\prime}_{k}]$;

    3. (c)

the circular order of $F_{i}$, $F_{j}$ and $F_{k}$ on any interval of
$\mathcal{P}(\mathcal{F})$ agrees with that of $G_{i}$, $G_{j}$ and $G_{k}$ on
the corresponding interval of $\mathcal{P}(\mathcal{G})$ (provided that the
interval is not a crossing interval of two of $F_{i}$, $F_{j}$ and $F_{k}$).

If $\varphi:\mathcal{F}\rightarrow\mathcal{G}$ is so that
$\varphi(F_{i})=G_{i}$ for $i=1,\dots n$, then we say that $\mathcal{F}$ and
$\mathcal{G}$ are suitably matched via $\varphi$. From condition (1), it
follows immediately that $\varphi$ is an isomorphism from $G[{\mathcal{F}}]$
to $H[{\mathcal{G}}]$.

######  Lemma 11.

, Let $\mathcal{F}$ and $\mathcal{G}$ be finite subsets of IC-dense sets. If
$\mathcal{F}$ and $\mathcal{G}$ are suitably matched via $\varphi$, then
$\varphi$ is a step-isometry.

###### Proof.

We claim that if $\mathcal{F}$ and $\mathcal{G}$ are suitably matched, and
$\mathcal{F}=\\{F_{1},\dots,F_{n}\\}$ and $\varphi(F_{i})=G_{i}$ for
$i=1,\dots,n$, then they have the additional property that
$\lfloor\|F_{i}-F_{j}\|\rfloor=\lfloor\|G_{i}-G_{j}\|\rfloor$ for each $i,j$.
To see this, notice that by condition (2)
$\lfloor|F_{i}(0)-F_{j}(0)|\rfloor=\lfloor|G_{i}(0)-G_{j}(0)|\rfloor$. Since
$F_{i}$ and $F_{j}$ then have the same crossings and the same circular order
as $G_{i}$ and $G_{j}$ (replacing crossing intervals of $F_{i}$ and $F_{j}$
and of $G_{i}$ and $G_{j}$ by points), we deduce that
$\lfloor\|F_{i}-F_{j}\|\rfloor=\lfloor\|G_{i}-G_{j}\|\rfloor$ as required. ∎

######  Theorem 12.

There exists a graph $GR(\mathrm{ICD})$ such that if $V$ is IC-dense, and
$p\in(0,1)$, then $\mathrm{LARG}(V,p)$ is almost surely isomorphic to
$GR(\mathrm{ICD})$.

###### Proof.

Let $V$ and $W$ be infinite crossing dense subsets of $C([0,1])$ and let
$p,p^{\prime}\in(0,1)$. We show that a realization of $\mathrm{LARG}(V,p)$ is
almost surely isomorphic to a realization of $\mathrm{LARG}(W,p^{\prime})$. As
in the proof of Theorem 4 for smoothly dense sets, we construct an isomorphism
via a back-and-forth argument. The key step of the proof is to show that if
finite sets $\mathcal{F}$ and $\mathcal{G}$ are suitably matched finite
subsets of $V$ and $W$, then given any additional $f\in V$, there is almost
surely a $g\in W$ such that $\mathcal{F}\cup\\{f\\}$ and
$\mathcal{G}\cup\\{g\\}$ are suitably matched.

We focus on a single step in one direction. Let
$\mathcal{F}=\\{F_{1},\dots,F_{n}\\}\subseteq V$ and
$\mathcal{G}=\\{G_{1},\ldots,G_{n}\\}\subseteq W$ be suitably matched via an
isomorphism $\varphi$, so that $F_{l}$ and $G_{l}$ correspond in the suitable
matching. We show that we can extend the isomorphism by adding the next
element in $V$ to $\mathcal{F}$, finding a suitable image for it, and adding
this image to $\mathcal{G}$.

Let $f\in V\setminus\mathcal{F}$ and let the crossing partitions of $[0,1]$ of
$\mathcal{F}$ and $\mathcal{G}$ be

$\displaystyle\mathcal{P}(\mathcal{F})$
$\displaystyle=\\{[0,a_{1}),[a_{1},b_{1}],(b_{1},a_{2}),[a_{2},b_{2}],\ldots,[a_{N},b_{N}],(b_{N},1]\\}\text{
and}$ $\displaystyle\mathcal{P}(\mathcal{G})$
$\displaystyle=\\{[0,a^{\prime}_{1}),[a^{\prime}_{1},b^{\prime}_{1}],(b^{\prime}_{1},a^{\prime}_{2}),[a^{\prime}_{2},b^{\prime}_{2}],\ldots,[a^{\prime}_{N},b^{\prime}_{N}],(b^{\prime}_{N},1]\\}.$

Consider $\mathcal{P}(\mathcal{F}\cup\\{f\\})$. This partition is a refinement
of $\mathcal{P}(\mathcal{F})$: the open sub-intervals of
$\mathcal{P}(\mathcal{F})$ may be sub-divided in
$\mathcal{P}(\mathcal{F}\cup\\{f\\})$ due to intersections of $f$ with
elements of $\mathcal{F}$. On the closed intervals $[a_{j},b_{j}]$, two
functions $F_{l}$ and $F_{m}$ in $\mathcal{F}$ cross infinitely often, and, by
construction, no other functions of $\mathcal{F}$ cross. When the
intersections with $f$ are used to refine the partition, one obtains a sub-
partition of $[a_{j},b_{j}]$ consisting of closed intervals in which $F_{l}$
and $F_{m}$ cross infinitely often; open intervals (with no crossings); and
closed intervals in which $f$ crosses an element of $\mathcal{F}$ (possibly
$F_{l}$ or $F_{m}$), again infinitely often. In each closed interval, there
are crossings between exactly one pair of functions. If there are no crossings
of $f$ and $\mathcal{F}$, the sub-partition is trivial; otherwise there are
sub-intervals of all three types. The situation is illustrated schematically
in Figure 2.

We shall build a target function $g$ such that all functions $h$ in a suitable
neighbourhood of $g$ satisfy suitable matching conditions (2) and (3). This
function is built sub-interval by sub-interval, interpolating various convex
combinations of the $(G_{i})$.

We first deal with the (harder) case of the sub-partition of one of the closed
intervals $[a_{j},b_{j}]\in\mathcal{P}(\mathcal{F})$. Suppose that the
functions crossing in the interval are $F_{l}$ and $F_{m}$. In
$\mathcal{P}(\mathcal{F}\cup\\{f\\})$, let $[a_{j},b_{j}]$ be refined as

$\mathcal{P}^{\prime}=\\{[a_{j},\beta_{0}],(\beta_{0},\alpha_{1}),[\alpha_{1},\beta_{1}],(\beta_{1},\alpha_{2}),[\alpha_{2},\beta_{2}],\ldots,[\alpha_{M-1},\beta_{M-1}],(\beta_{M-1},\alpha_{M}),[\alpha_{M},b_{j}]\\}.$

Since the refinement is obtained by adding $f$ to $\mathcal{F}$, at each of
$\alpha_{1},\dots,\alpha_{M}$, there is a crossing of $f$ and an element of
$\mathcal{F}$, or a crossing of $F_{l}$ and $F_{m}$.

$\beta_{3}$$b_{j}$$\alpha_{4}$$\alpha_{3}$$\beta_{2}$$\beta_{1}$$\alpha_{1}$$\beta_{0}$$a_{j}$$\alpha_{2}$

Figure 2. Schematic indicating the refinement of an interval $[a_{j},b_{j}]$
in which the two central functions, $F_{l}$ and $F_{m}$ are crossing when a
new function $f$ (in bold) is added to the collection. The closed sub-
intervals in the refinement are indicated below.

Let $[a_{j}^{\prime},b_{j}^{\prime}]$ be the corresponding interval to
$[a_{j},b_{j}]$ in $\mathcal{P}(\mathcal{G})$. We say a sub-interval
$[\alpha^{\prime},\beta^{\prime}]$ of $[a_{j}^{\prime},b_{j}^{\prime}]$ is a
_crossing sub-interval_ for $G_{l}$ and $G_{m}$ if $G_{l}$ and $G_{m}$ cross
at $\alpha^{\prime}$ and $\beta^{\prime}$, but not on small open intervals
$(\alpha^{\prime}-\eta,\alpha^{\prime})$ and
$(\beta^{\prime},\beta^{\prime}+\eta)$, for some $\eta>0$. Such a crossing
sub-interval is of _type_ $<<$, $<>$, $><$ or $>>$ if respectively, $\langle
G_{l}\rangle$ is below $\langle G_{m}\rangle$ to the left and the right of the
interval; $\langle G_{l}\rangle$ is below $\langle G_{m}\rangle$ to the left
and above to the right; $\langle G_{l}\rangle$ is above $\langle G_{m}\rangle$
to the left and below to the right; or $\langle G_{l}\rangle$ is above
$\langle G_{m}\rangle$ to the left and right of the interval. Condition (3)
ensures that there are infinitely many crossing sub-intervals of each type in
any sub-interval $[a_{j}^{\prime},a_{j}^{\prime}+\delta)$ or
$(b_{j}^{\prime}-\delta,b^{\prime}_{j}]$.

We now proceed to define a “target sub-partition” of
$\mathcal{P}(\mathcal{G})$ which corresponds to the restriction of
$\mathcal{P}(\mathcal{F}\cup\\{f\\})$ to $[a_{j}^{\prime},b_{j}^{\prime}]$. We
will subsequently construct a target function $g$ such that any sufficiently
nearby function $\tilde{g}$ in $W$ has the property that
$\mathcal{P}(\mathcal{G}\cup\\{\tilde{g}\\})$ is close to
$\mathcal{P}(\mathcal{G})$.

First, let $[a_{j},\beta_{0}]$, $[\alpha_{k_{i}},\beta_{k_{i}}]$ for
$i=1,\ldots,L$ and $[\alpha_{M},b_{j}]$ be the sub-intervals in
$\mathcal{P}(\mathcal{F}\cup\\{f\\})$ where $F_{l}$ and $F_{m}$ cross (or just
$[a_{j},b_{j}]$ if $f$ does not intersect $\mathcal{F}$ on $[a_{j},b_{j}]$).
For each, pick a crossing sub-interval
$[\alpha^{\prime}_{k_{i}},\beta^{\prime}_{k_{i}}]$ of
$[a_{j}^{\prime},b_{j}^{\prime}]$ for $G_{l}$ and $G_{m}$ of the same type,
arranged in the same order on the interval. This is possible by the above
observation that there are infinitely many crossing sub-intervals of each type
near $a_{j}^{\prime}$ and $b_{j}^{\prime}$. Between each pair,
$[\alpha^{\prime}_{k_{i}},\beta^{\prime}_{k_{i}}]$ and
$[\alpha^{\prime}_{k_{i+1}},\beta^{\prime}_{k_{i+1}}]$, pick a sub-interval
$O_{i}$ on which $G_{l}$ and $G_{m}$ do not cross and have the same ordering
as $F_{l}$ and $F_{m}$ have on $(\beta_{k_{i}},\alpha_{k_{i+1}})$.

Next, for the remaining sub-intervals $[\alpha_{k},\beta_{k}]$ between
$[\alpha_{k_{i}},\beta_{k_{i}}]$ and $[\alpha_{k_{i+1}},\beta_{k_{i+1}}]$
where $f$ crosses some $F_{j}$, arbitrarily pick disjoint sub-intervals
$[\alpha^{\prime}_{k},\beta^{\prime}_{k}]$ of $O_{i}$ that respect the left-
to-right ordering.

Finally, write

$\mathcal{Q}^{\prime}=\\{[a^{\prime}_{j},\beta_{0}^{\prime}],(\beta_{0}^{\prime},\alpha^{\prime}_{1}),[\alpha^{\prime}_{1},\beta^{\prime}_{1}],(\beta^{\prime}_{1},\alpha^{\prime}_{2}),[\alpha^{\prime}_{2},\beta^{\prime}_{2}],\ldots,[\alpha^{\prime}_{M-1},\beta^{\prime}_{M-1}],(\beta^{\prime}_{M-1},\alpha_{M}),[\alpha_{M},b^{\prime}_{j}]\\},$

This process gives a partition of the closed sub-intervals that has similar
behaviour, with respect to the functions in $\mathcal{G}$, as the functions in
$\mathcal{F}$ have on the sub-intervals induced by introducing $f$ to the
crossing partition of $\mathcal{F}$. We will now do the same for the open sub-
intervals.

In the case that one is sub-partitioning one of the open sub-intervals
$(b_{j},a_{j+1})$, things are easier as the only crossings that occur in the
sub-interval are those between $f$ and the $F_{j}$’s. In this case, as before
write

$\mathcal{P}^{\prime}=\\{(b_{j},\alpha_{1}),[\alpha_{1},\beta_{1}],(\beta_{1},\alpha_{2}),[\alpha_{2},\beta_{2}],\ldots,[\alpha_{M},\beta_{M}],(\beta_{M},a_{j+1})\\}.$

Recall that, by construction, in each of the open intervals no functions
cross, while in each closed intervals, $f$ crosses infinitely often with
exactly one of the functions in $\mathcal{F}$. Define an arbitrary set of
division points $\alpha^{\prime}_{i}$ and $\beta^{\prime}_{i}$ such that
$b^{\prime}_{j}<\alpha^{\prime}_{1}<\beta^{\prime}_{1}<\ldots<\beta^{\prime}_{M}<a^{\prime}_{j+1}$,
and let

$\mathcal{Q}^{\prime}=\\{(b^{\prime}_{j},\alpha^{\prime}_{1}),[\alpha^{\prime}_{1},\beta^{\prime}_{1}],(\beta^{\prime}_{1},\alpha^{\prime}_{2}),[\alpha^{\prime}_{2},\beta^{\prime}_{2}],\ldots,[\alpha^{\prime}_{M},\beta^{\prime}_{M}],(\beta^{\prime}_{M},a^{\prime}_{j+1}]\\}.$

Given an interval $I$ of $\mathcal{P}^{\prime}$ in which $f$ does not cross
any of the $F_{j}$’s, let $F_{p}$ be the function immediately below $f$ in the
circular ordering on $I$ and $F_{q}$ be the function immediately above. Let
the integers $r$ and $s$ be chosen so that $F_{p}+r<f<F_{q}+s$ on $I$ and $r$
and $s$ are respectively, the largest and smallest integers with that
property. Let $J$ be the interval in $\mathcal{Q}^{\prime}$ corresponding to
$I$. We then define $g$ on $J$ to be $\frac{1}{2}((G_{p}+r)+(G_{q}+s))$. If
$I\in\mathcal{P}^{\prime}$ is such that $f$ crosses the function $F_{j}$, then
let the circular predecessor and successor of $F_{j}$ be $F_{p}$ and $F_{q}$
respectively, and as above, let $F_{p}+r<f<F_{q}+s$. Also, suppose that the
integer $t$ is chosen so that $F_{j}+t$ intersects $f$ (in $\mathbb{R}$; not
just in the circle), so that $F_{j}+t$ satisfies the same inequality at $f$ on
$I$: $F_{p}+r<F_{j}+t<F_{q}+s$. We then define $g$ by interpolating between
midpoints of pairs of $F_{p}+r$, $F_{j}+t$ and $F_{q}+s$. In particular, if
$J=[\alpha^{\prime},\beta^{\prime}]$ is the corresponding interval to $I$ and
the intersection between $f$ and $F_{j}$ on $I$ is of type $<>$ for example,
then we define $g$ restricted to $J$ by

$g(x)=\frac{\beta^{\prime}-x}{2(\beta^{\prime}-\alpha^{\prime})}(G_{p}+r+G_{j}+t)+\frac{x-\alpha^{\prime}}{2(\beta^{\prime}-\alpha^{\prime})}(G_{j}+t+G_{q}+s),$

so that $g$ crosses from the midpoint below $G_{j}$ to the midpoint above
$G_{j}$. For a second example, if $f$ is of type $<<$, we set
$\gamma^{\prime}=\frac{\alpha^{\prime}+\beta^{\prime}}{2}$ and define

$g(x)=\begin{cases}\frac{\gamma^{\prime}-x}{2(\gamma^{\prime}-\alpha^{\prime})}(G_{p}+r+G_{j}+t)+\frac{x-\alpha^{\prime}}{2(\gamma^{\prime}-\alpha^{\prime})}(G_{j}+t+G_{q}+s)&x\in[\alpha^{\prime},\gamma^{\prime}],\\\
\frac{\beta^{\prime}-x}{2(\beta^{\prime}-\gamma^{\prime})}(G_{j}+t+G_{q}+s)+\frac{x-\gamma^{\prime}}{2(\beta^{\prime}-\gamma^{\prime})}(G_{p}+r+G_{j}+t)&x\in[\gamma^{\prime},\beta^{\prime}]\end{cases},$

so that $g$ crosses from the midpoint below $G_{j}$ to the midpoint above and
back down again. The piecewise interpolated function, $g$, defined on all of
[0,1] interval by interval in this way is continuous, and has the same pattern
of crossings with $\mathcal{G}$ that $f$ has with $\mathcal{F}$.

Note that for each crossing interval of $f$ with one of the functions $F_{k}$,
$g$ likely crosses $G_{k}$ infinitely often, but this is not guaranteed from
the definition. Nonetheless, when $g$ is approximated by a $\tilde{g}$
belonging to $W$, crossings between $\tilde{g}$ and the $G_{k}$ do occur with
infinite multiplicity.

Let $C$ be the union of all of the sub-intervals
$[\alpha^{\prime},\beta^{\prime}]$ in [0,1] on which $g$ crosses
$\mathcal{G}$, and let $\epsilon$ be smaller than half the distance between
two consecutive sub-intervals in $C$, and also smaller than $a_{1}^{\prime}$
and $b_{N}^{\prime}$. Let $\mathcal{N}$ be the $\epsilon$-neighbourhood of
$C$, so that it consists of disjoint open intervals, one for each of the
closed sub-intervals forming $C$. There exists a $\delta_{1}>0$ such that
$|g(x)-\big{(}G_{j}(x)+m\big{)}|\geq\delta_{1}$ for all
$x\in[0,1]\setminus\mathcal{N}$, all $j=1,\ldots,n$ and all $m\in\mathbb{Z}$.
Also, there exists $\delta_{2}>0$ such that in each of the sub-intervals in
$\mathcal{P}^{\prime}$ where $g$ crosses any $G_{j}+m$, it attains values less
than $G_{j}+m-\delta_{2}$ and values greater than $G_{j}+m+\delta_{2}$.
Finally, there exists a $\delta_{3}>0$ such that if
$\|\tilde{g}-g\|<\delta_{3}$,
$\lfloor|f(0)-F_{j}(0)|\rfloor=\lfloor|\tilde{g}(0)-G_{j}(0)|\rfloor$. Now if
$\|\tilde{g}-g\|<\delta=\min(\delta_{1},\delta_{2},\delta_{3})$, we see that
$\mathcal{F}\cup\\{f\\}$ and $\mathcal{G}\cup\\{\tilde{g}\\}$ satisfy
conditions (2) and (3) of suitable matching. By Lemma 11, for any $\tilde{g}$
such that $\|\tilde{g}-g\|<\delta$, we have
$\lfloor\|\tilde{g}-G_{j}\|\rfloor=\lfloor\|f-F_{j}\|\rfloor$ for each $1\leq
j\leq n$. In particular, for each $j$ such that $f$ is adjacent to $F_{j}$, we
have $\|\tilde{g}-G_{j}\|<1$. Hence, since $\\{g_{n}\\}$ is dense, there are
infinitely many $k$’s such that $\|g_{k}-g\|<\delta$ and $g_{k}$ has the
correct adjacencies to $\mathcal{G}$. Thus, $\mathcal{F}\cup\\{f\\}$ is
suitably matched to $\mathcal{G}\cup\\{g_{k}\\}$. This completes the inductive
step, and hence, the proof. ∎

###  3.2. Brownian motion

We consider the following procedure to select random functions: a starting
point (the value at 0) is chosen from a standard normal distribution and from
there the function follows a standard Brownian path. Formally, let
$(N_{n})_{n\in\mathbb{N}}$ be a family of countably many independent standard
normal random variables and let $(X_{n}(t))_{n\in\mathbb{N}}$ be a family of
countably many independent standard Brownian motions (with $X_{n}(0)=0$,
$\mathbb{E}X_{n}(t)=0$ and $\operatorname{Var}X_{n}(t)=t$ for each
$n\in\mathbb{N}$ and $t\in[0,1]$). Let $f_{n}(t)=N_{n}+X_{n}(t)$ be a random
function obtained in this manner, which we refer to as a shifted Brownian
motion.

######  Theorem 13.

If $(f_{n})_{n\in\mathbb{N}}$ is a family of countably many independent
shifted Brownian motions sampled from the above distribution, then the
collection is almost surely IC-dense.

###### Proof.

Let $\epsilon>0$ be given. Let $f$ be a continuous function. There exists a
piecewise linear function $g$ with change points at
$(0,y_{0}),(x_{1},y_{1}),\ldots,(x_{n-1},y_{n-1}),(1,y_{n})$ such that
$\|g-f\|<\frac{\epsilon}{2}$. By standard properties of Brownian motion, it is
known that $\mathbb{P}(|N-y_{0}|<\frac{\epsilon}{2n})>0$ and that
$\mathbb{P}(|X(x_{j})-X(x_{j-1})-(y_{j}-y_{j-1})|<\frac{\epsilon}{2n}\,|\,X(x_{1}),\ldots,X(x_{j-1}))>0$.
Finally, it is known that conditioned on the values of
$X(x_{1}),\ldots,X(x_{n})$, the probability that $X$ never strays by more than
$\frac{\epsilon}{2}$ from the linear function joining $X(x_{i})$ and
$X(x_{i+1})$ is positive (the distribution of $(X(t))_{x_{i}\leq t\leq
x_{i+1}}$ conditioned on $X(x_{i})$ and $X(x_{i+1})$ is a so-called _Brownian
bridge_). Multiplying these probabilities together, we note that the
probability that $\|f_{j}-f\|<\epsilon$ is positive, and is the same for each
$j$. Hence, by the second Borel-Cantelli lemma, there almost surely exists a
$j$ such that $\|f_{j}-f\|<\epsilon$. Since $C([0,1])$ is separable, the above
argument shows that $(f_{n})$ is almost surely dense.

IC-dense Condition (2) follows from a corollary of Lévy’s theorem (Corollary
2.23 in Mörters and Peres [15]) which states that for any non-zero point $p$
in $\mathbb{R}^{2}$, the standard 2-dimensional Brownian motion almost surely
does not pass through $p$. To see this, we deal with two cases: we first show
that there are no three functions all crossing at a single $x$ value; and then
show that there are not two distinct pairs of functions with both pairs
crossing at a single $x$ value. For the first of these, it suffices (since
there are countably many triples) to show that with probability 1, $f_{1}$,
$f_{2}$ and $f_{3}$ do not all cross at any $x$. That is, it suffices to show
that for any integers $m$ and $n$, with probability 1, there does not exist an
$x$ such that $f_{2}(x)-f_{1}(x)=m$ and $f_{3}(x)-f_{1}(x)=n$. Conditional on
$N_{1}=y_{1}$, $N_{2}=y_{2}$ and $N_{3}=y_{3}$, the values at $x=0$, we
therefore have to show that

$\mathbb{P}(\exists x\colon X_{2}(x)-X_{1}(x)=m+y_{2}-y_{1}\text{ and
}X_{3}(x)-X_{1}(x)=n+y_{3}-y_{1})=0.$

This does not immediately follow from the theorem mentioned above about
2-dimensional Brownian motion since $((X_{2}-X_{1})(x),(X_{3}-X_{1})(x))$ is
not a standard Brownian motion: the coordinates are correlated. It is,
however, expressible as a fixed linear transformation of a standard Brownian
motion (see, for example, [15] page 14) and hence, the previous theorem
applies.

Similarly, to show that $f_{1}$, $f_{2}$, $f_{3}$ and $f_{4}$ do not have the
property that $f_{1}$ and $f_{2}$ cross at some $x$ and $f_{3}$ and $f_{4}$
cross at the same $x$, we need to show that

$\mathbb{P}(\exists x\colon X_{2}(x)-X_{1}(x)=m+y_{1}-y_{2}\text{ and
}X_{4}(x)-X_{3}(x)=n+y_{3}-y_{4})=0.$

This follows directly from the quoted theorem since
$((X_{2}-X_{1})(x),(X_{4}-X_{3})(x))$ is a scaled copy of the standard
Brownian motion (by a scale factor of $\sqrt{2}$).

To see that $f_{1}$ and $f_{2}$ do not cross at 0, we observe that
$\mathbb{P}(N_{2}=N_{1}+n|N_{1}=x)=0$ and so integrating over $x$, the
probability of a crossing at 0 is 0, similar to the argument in Lemma 5. A
similar argument involving $N_{1}$, $N_{2}$, $X_{1}(1)$ and $X_{2}(1)$ shows
that the probability of a crossing at 1 is 0, and this proves (3).

To verify the last condition, notice that
$f_{2}(x)-f_{1}(x)=X_{2}(x)-X_{1}(x)+N_{2}-N_{1}$. By Theorem 2.11 of [15], a
Brownian motion has countably many local extrema and by Theorem 5.14 of [15],
no local points of increase or decrease (a point of local increase for a
Brownian motion $Z(x)$ is an $x_{0}$ such that for some $\delta>0$, on
$(x_{0},x_{0}+\delta)$, $Z(x)>Z(x_{0})$ and on $(x_{0}-\delta,x_{0})$,
$Z(x)<Z(x_{0})$, with a point of local decrease being defined similarly).
Given $X_{1}$ and $X_{2}$, the probability that $N_{2}-N_{1}$ is such that
value taken at one of the countably many local extrema of $f_{2}-f_{1}$ is an
integer is 0 (since this only occurs for countably many values of
$N_{2}-N_{1}$ and $N_{1}$ and $N_{2}$ have continuous distributions). Hence,
we have that almost surely, each crossing point of $f_{2}-f_{1}$ is not a
local extremum or a point of local increase or decrease. Since these
possibilities are ruled out, the remaining possibility is IC-density condition
(4). ∎

######  Corollary 14.

If $V$ is a countable collection of independent samples of shifted Brownian
motion, then for all $p\in(0,1)$, $\mathrm{LARG}(V,p)$ is almost surely
isomorphic to $GR(\mathrm{ICD})$.

###### Proof.

By Theorem 13, a countable collection of realizations of Brownian motions with
random starting points is almost surely IC-dense. By Theorem 12, if one builds
a LARG graph from such a realization, it is almost surely isomorphic to
$GR(\mathrm{ICD})$. ∎

##  4\. Non-isomorphism

In the previous sections we showed that LARG graphs on smoothly dense sets are
almost surely isomorphic to $GR(\mathrm{SD})$, while LARG graphs on IC-dense
sets are almost surely isomorphic to $GR(\mathrm{ICD})$. In this section, we
will show that these two graphs are not isomorphic, and that they are not
isomorphic to the infinite graphs obtained from LARG graphs obtained from some
other metric spaces.

A central tool in this discussion is a corollary of a theorem of Dilworth
(Theorem 16 of [7]), which states that for every step-isometry $\theta$
between dense subsets $V$ and $W$ of a normed space $X$, there is a true
isometry $\tilde{\theta}$ such that $\|\tilde{\theta}(v)-\theta(v)\|<K$ for
all $v\in V$. Recall that any isomorphism between LARG graphs must be a step-
isometry.

We first focus on $GR(\mathrm{SD})$. In [7] it was shown that for suitable
random subsets of $c$, the LARG graphs are Rado with isomorphism type $GR(c)$
and similarly for random subsets of $c_{0}$, the isomorphism type is
$GR(c_{0})$. Using the fact that $c$ and $c_{0}$ are not isometric, we We
showed in [7] that the graphs $GR(c)$ and $GR(c_{0})$ are non-isomorphic. Our
first result is derived similarly to the results in [7].

######  Corollary 15.

The graphs $GR(\mathrm{SD})$ and $GR(\mathrm{ICD})$ are not isomorphic to
either $GR(c)$ or $GR(c_{0})$.

This follows from the fact that $C[0,1]$ is not isometric to either $c_{0}$ or
$c$ (for example, its dual is not separable).

We next consider $GR(\mathrm{ICD})$, the almost-sure isomorphism type of
shifted Brownian motions (as shown in Corollary 14.) We show that
$GR(\mathrm{SD})$ and $GR(\mathrm{ICD})$ are not isomorphic.

Before we give this theorem, we present some classical results which will be
used in the proof. A theorem of Mazur and Ulam [14] states that a surjective
isometry of real normed spaces is necessarily affine. Dilworth [11] extended
this by showing that an approximate surjective isometry of Banach spaces may
be uniformly approximated by a linear isometry. Recall that any isomorphism
between LARG graphs must almost surely be a step-isometry (see Corollary 5 of
[5]). The following corollary of Dilworth’s result states that any step-
isometry gives rise to a surjective linear isometry that bounds the distance
between pre-image and image.

######  Theorem 16.

([7]) Suppose $(f_{n})$ and $(g_{n})$ are dense sequences in separable Banach
spaces $X$ and $Y$ and
$\lfloor\|f_{i}-f_{j}\|\rfloor=\lfloor\|g_{i}-g_{j}\|\rfloor$ for each $i,j$.
Then there exists a surjective linear isometry, $L$, from $X$ to $Y$ and a
constant $\kappa>0$ such that $\|g_{i}-L(f_{i})\|<\kappa$ for all $i$.

A classical result then shows that the existence of a surjective linear
isometry implies that there exists a homeomorphism with certain nice
properties.

######  Theorem 17 (Banach–Stone).

Let $X$ and $Y$ be compact Hausdorff spaces and $L$ be a surjective linear
isometry from $C(X,\mathbb{R})$ to $C(Y,\mathbb{R})$. Then there exists a
homeomorphism $\varphi\colon Y\to X$ and a function $g\in C(Y,\mathbb{R})$
with $|g(y)|=1$ for all $y$ such that

$L[f](y)=g(y)f(\varphi(y))\text{ for all $f\in C(X,\mathbb{R})$ and $y\in
Y$.}$

We apply this in the special case that $X$ and $Y$ are both the closed unit
interval, so that $g$ is a constant function, either $g\equiv 1$ or
$g\equiv-1$. This will lead to necessary conditions for two sets to give rise
to isomorphic graphs, as stated in the following theorem.

######  Theorem 18.

Let $(f_{n})$ and $(g_{n})$ be countable dense sets in $C([0,1])$ and suppose
that the LARG graphs on $(f_{n})$ and on $(g_{n})$ are almost surely
isomorphic. Then there exists a homeomorphism $\psi$ from $[0,1]$ to itself
and a permutation of $\mathbb{N}$, $i\mapsto n_{i}$, such that one of the
following holds:

  1. (1)

(Order-preserving case) For each $x\in[0,1]$, if $f_{i}(x)>f_{j}(x)$ then
$g_{n_{i}}(\psi(x))\geq g_{n_{j}}(\psi(x))$;

  2. (2)

(Order-reversing case) For each $x\in[0,1]$, if $f_{i}(x)>f_{j}(x)$ then
$g_{n_{i}}(\psi(x))\leq g_{n_{j}}(\psi(x))$.

###### Proof.

Let $(f_{n})$ and $(g_{n})$ be as described. Fix LARG graphs $G_{1}$ and
$G_{2}$ on $(f_{n})$ and $(g_{n})$, respectively, and suppose that they are
isomorphic. We may re-label $(g_{n})$ so that for each $n$, $f_{n}$ is
identified with $g_{n}$ in the isomorphism. By Corollary 1, such an
isomorphism must almost surely be a step-isometry:
$\lfloor\|f_{i}-f_{j}\|\rfloor=\lfloor\|g_{i}-g_{j}\|\rfloor$ for each $i,j$.
Then by Theorems 16 and 17, there exist a self-homeomorphism $\varphi$ of
$[0,1]$, a constant $\rho=\pm 1$ and a $\kappa>0$ such that

$\|g_{i}-\rho f_{i}\circ\varphi\|<\kappa\text{ for all $i$.}$ (4)

We deal with the order-preserving case, $\rho=1$, although the case $\rho=-1$
is analogous. Let $\psi=\varphi^{-1}$.

Let $x_{0}\in[0,1]$ and suppose that $f_{i}(x_{0})>f_{j}(x_{0})$. We let
$\Delta=f_{i}(x_{0})-f_{j}(x_{0})$. For any positive numbers, $l\in\mathbb{N}$
and $M\in\mathbb{R}$, define
$h_{l,M}(x)=\max(f_{i},f_{j}+\Delta)-M+l|x-x_{0}|$.

Now given $l\in\mathbb{N}$, Let $M_{l}$ be of the form $N+\frac{\Delta}{2}$,
where $N\in\mathbb{N}$ is chosen sufficiently large that

$h_{l,M_{l}}<\min(f_{i},f_{j})-2\kappa-\Delta.$ (5)

We write $h$ for $h_{l,M_{l}}$. We now have that, for each $x\in[0,1]$,

$\displaystyle f_{i}-h(x)$ $\displaystyle\leq M-l|x-x_{0}|$ $\displaystyle
f_{j}-h(x)$ $\displaystyle\leq M-\Delta-l|x-x_{0}|,$

where both inequalities are equalities at $x=x_{0}$. In particular, we see
$\|f_{i}-h\|=N+\frac{\Delta}{2}$ and $\|f_{j}-h\|=N-\frac{\Delta}{2}$ and
$\lfloor\|f_{i}-h\|\rfloor\geq N$ while $\|\lfloor f_{j}-h\|\rfloor<N$.

Let $f_{k}$ be an element such that $\|f_{k}-h\|<\frac{\Delta}{2}$. This
implies that $\lfloor\|f_{i}-f_{k}\|\rfloor\geq N$ and
$\lfloor\|f_{j}-f_{k}\|\rfloor<N$. By Corollary 1, we have
$\lfloor\|g_{i}-g_{k}\|\rfloor\geq N$ and $\lfloor\|g_{j}-g_{k}\|\rfloor<N$
also.

By(4), we have that

$\displaystyle-\kappa$ $\displaystyle<g_{n}-f_{n}\circ\varphi<\kappa\text{ for
all $n$; and so}$ $\displaystyle-\kappa-\tfrac{\Delta}{2}$
$\displaystyle<g_{k}-h\circ\varphi<\kappa+\tfrac{\Delta}{2}$

Combining this with (5), it follows that $g_{i}-g_{k}$ and $g_{j}-g_{k}$ are
non-negative.

We also see that

$\displaystyle g_{i}(x)-g_{k}(x)$ $\displaystyle\leq
f_{i}(\varphi(x))-h(\varphi(x))+2\kappa+\tfrac{\Delta}{2}$ $\displaystyle\leq
N+\Delta+2\kappa-l|\varphi(x)-x_{0}|$

In particular, $g_{i}(x)-g_{k}(x)<N$ whenever
$|\varphi(x)-x_{0}|>(\Delta+2\kappa)/l$. Since $\|g_{i}-g_{k}\|\geq N$, it
follows that there exists $y_{l}$ such that
$|\varphi(y_{l})-x_{0}|\leq(\Delta+2\kappa)/l$ with
$g_{i}(y_{l})-g_{k}(y_{l})\geq N$. On the other hand, since
$\|g_{j}-g_{k}\|<N$, we see $g_{j}(y_{l})-g_{k}(y_{l})<N$. In particular, we
deduce that $g_{i}(y_{l})>g_{j}(y_{l})$. We now have a sequence of points
$y_{l}$ where $g_{i}(y_{l})>g_{j}(y_{l})$. We also have
$|\varphi(y_{l})-x_{0}|\to 0$ as $l\to\infty$, which implies $y_{l}\to
y_{0}=\psi(x_{0})$. By continuity of $g_{i}$ and $g_{j}$, we deduce that
$g_{i}(\psi(x_{0}))\geq g_{j}(\psi(x_{0}))$. ∎

######  Corollary 19.

The graphs $GR(\mathrm{ICD})$ and $GR(\mathrm{SD})$ are non-isomorphic.

###### Proof.

Let $(f_{n})$ be IC-dense and $(g_{n})$ be a smoothly dense sequence of
polynomials (such a sequence exists by Theorem 8). Let $G_{1}$ and $G_{2}$ be
LARG graphs with vertices $(f_{n})$ and $(g_{n})$, respectively, so that
$G_{1}$ is almost surely isomorphic to $GR(\mathrm{ICD})$ and $G_{2}$ is
almost surely isomorphic to $GR(\mathrm{SD})$. Suppose for a contradiction
that $G_{1}$ and $G_{2}$ are isomorphic.

We now apply Theorem 18, and assume without loss of generality that we are in
the orientation-preserving case. Thus, there exists a permutation $i\mapsto
n_{i}$ of $\mathbb{N}$ and a homeomorphism $\psi$ of $[0,1]$ such that
$f_{i}(x)>f_{j}(x)$ implies $g_{n_{i}}(\psi(x))\geq g_{n_{j}}(\psi(x))$ for
all $x$. By the infinite crossing dense condition, there must be two functions
that intersect. That is, there exist $i\neq j$ so that $f_{i}(x)=f_{j}(x)$ for
some $x\in(0,1)$. By the IC-dense property (4), there exists a strictly
monotonic sequence $x_{m}\to x$ such that $f_{i}(x_{m})=f_{j}(x_{m})$ and
between any pair $x_{m}$ and $x_{m+1}$, there exist $y_{m}$ and $z_{m}$ such
that $f_{i}(y_{m})>f_{j}(y_{m})$ and $f_{i}(z_{m})<f_{j}(z_{m})$. It follows
that $g_{n_{i}}(\psi(y_{m}))\geq g_{n_{j}}(\psi(y_{m}))$ and
$g_{n_{i}}(\psi(z_{m}))\geq g_{n_{j}}(\psi(z_{m}))$. In particular, by the
Intermediate Value Theorem, there exists $w_{m}$ between $y_{m}$ and $z_{m}$
such that $g_{n_{i}}(\psi(w_{m}))=g_{n_{j}}(\psi(w_{m}))$. Hence, the two
polynomials $g_{n_{i}}$ and $g_{n_{j}}$ agree at infinitely many points, and
so are equal, which is a contradiction.∎

## References

  * [1] P. Balister, B. Bollobás, K. Gunderson, I. Leader, M. Walters, Random geometric graphs and isometries of normed spaces, Preprint 2018.
  * [2] P. Balister, B. Bollobás, A. Sarkar, M. Walters, Highly connected random geometric graphs, _Discrete Applied Mathematics_ 157 (2009) 309–320.
  * [3] B. Bollobás, _Linear Analysis, An Introductory Course, Second Edition_ , Cambridge University Press, 1999.
  * [4] A. Bonato, _A Course on the Web Graph_ , American Mathematical Society Graduate Studies Series in Mathematics, Providence, Rhode Island, 2008.
  * [5] A. Bonato, J. Janssen, Infinite random geometric graphs, _Annals of Combinatorics_ 15 (2011) 597-617.
  * [6] A. Bonato, J. Janssen, Infinite geometric graphs and properties of metrics, book chapter In: _Recent Trends in Combinatorics_ , Editors: A. Beveridge, J.R. Griggs, L. Hogben, G. Musiker, P. Tetali, Springer, 2016 pp.257–272.
  * [7] A. Bonato, J. Janssen, A. Quas, Geometric random graphs and Rado sets in sequence spaces, Preprint 2018.
  * [8] P.J. Cameron, The random graph, In: _Algorithms and Combinatorics_ 14 (R.L. Graham and J. Nešetřil, eds.), Springer Verlag, New York (1997) 333-351.
  * [9] P.J. Cameron, The random graph revisited, In: _European Congress of Mathematics_ Vol. I (C. Casacuberta, R. M. Miró-Roig, J. Verdera and S. Xambó-Descamps, eds.), Birkhauser, Basel (2001) 267-274.
  * [10] R. Diestel, _Graph theory_ , Springer-Verlag, New York, 2000.
  * [11] S. Dilworth, _Bull. London Math. Soc._ 31 (1999) 471–476.
  * [12] R. Ellis, X. Jia, C.H. Yan, On random points in the unit disk, _Random Algorithm and Structures_ 29 (2006) 14–25.
  * [13] P. Erdős, A. Rényi, Asymmetric graphs, _Acta Mathematica Academiae Scientiarum Hungaricae_ 14 (1963) 295–315.
  * [14] S. Mazur, S. Ulam, Sur les transformationes isométriques d´espaces vectoriels normés, _C. R. Acad. Sci. Paris_ 194 (1932) 946–948.
  * [15] P. Mörters,Y. Peres, _Brownian Motion_ , Cambridge University Press, Cambridge, 2010.
  * [16] M. Penrose, _Random Geometric Graphs_ , Oxford University Press, Oxford, 2003.
  * [17] M. Walters, Random geometric graphs, In: _Surveys in Combinatorics 2011_ , edited by Robin Chapman, London Mathematical Society Lecture Note Series, 392 Cambridge University Press, Cambridge, 2011.
  * [18] D.B. West, _Introduction to Graph Theory, 2nd edition_ , Prentice Hall, 2001.