# Dense and nondense limits
for uniform random intersection graphs

Frédérique Bassino  Université Sorbonne Paris Nord, LIPN, CNRS UMR 7030,
F-93430 Villetaneuse, France<EMAIL_ADDRESS>,  Mathilde Bouvel
Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
<EMAIL_ADDRESS>,  Valentin Féray  Université de Lorraine, CNRS,
IECL, F-54000 Nancy, France<EMAIL_ADDRESS>,  Lucas Gerin
CMAP, École Polytechnique, CNRS, Route de Saclay, 91128 Palaiseau Cedex,
France<EMAIL_ADDRESS>and  Adeline Pierrot  LISN, Université
Paris-Saclay, Bat. 650 Ada Lovelace, 91405 Orsay Cedex, France
<EMAIL_ADDRESS>
###### Abstract.

We obtain the scaling limits of random graphs drawn uniformly in three
families of intersection graphs: permutation graphs, circle graphs, and unit
interval graphs. The two first families typically generate dense graphs, in
these cases we prove a.s. convergence to an explicit deterministic graphon.
Uniform unit interval graphs are nondense and we prove convergence in the
sense of Gromov–Prokhorov after normalization of the distances: the limiting
object is the interval $[0,1]$ endowed with a random metric defined through a
Brownian excursion. Asymptotic results for the number of cliques of size $k$
($k$ fixed) in a uniform random graph in each of these three families are also
given.
In all three cases, an important ingredient of the proof is that, for
indecomposable graphs in each class (where the notion of indecomposability
depends on the class), the combinatorial object defining the graph
(permutation, matching, or intervals) is essentially unique.

###### Key words and phrases:

intersection graphs, scaling limits, graphons, permutations, matchings, Dyck
paths

###### 2020 Mathematics Subject Classification:

05C62, 05C80

##  1\. Introduction

###  1.1. Background: random graphs in classes defined by intersections.

For a collection of sets $\mathcal{C}$ and a $n$-tuple
$S=(s_{1},s_{2},\dots,s_{n})$ of elements in $\mathcal{C}$ (called seed), the
_intersection graph_ associated with ${s_{1},s_{2},\dots,s_{n}}$ is the graph
with vertex set $\left\\{v_{1},v_{2},\dots,v_{n}\right\\}$ in which two
vertices $v_{i}\neq v_{j}$ are joined by an edge if and only if $s_{i}\cap
s_{j}\neq\varnothing$.

Families of intersection graphs associated to natural geometric or
combinatorial collections $\mathcal{C}$ have been the object of particular
interest. Among other, the following graph classes have been studied in the
literature:

  * •

_interval graphs_ : $\mathcal{C}$ is the collection of intervals on the real
line;

  * •

_unit interval graphs_ (also called _proper interval graphs_ or _indifference
graphs_): $\mathcal{C}$ is the collection of intervals of length one on the
real line;

  * •

_circle graphs_ : $\mathcal{C}$ is the collection of chords of a given circle;

  * •

_circular arc graphs_ : $\mathcal{C}$ is the collection of arcs of a given
circle;

  * •

_string graphs_ : $\mathcal{C}$ is the collection of curves in the plane;

  * •

_permutation graphs_ : $\mathcal{C}$ is the collection of straight line
segments whose endpoints lie on two parallel lines. (This last definition is
equivalent to defining permutation graphs as the _inversion graphs_ of
permutations).

Figure 1. Illustration of the three families studied in this article. From top
to bottom on the right: a permutation graph, a circle graph, a unit interval
graph. In each case one of its representatives $(s_{1},s_{2},\dots,s_{n})$ is
shown on the left.

We refer the reader to Fig. 1 for examples of intersection graphs in three of
these families. The Wikipedia page on the topic [Wik24] contains a longer list
of graph classes defined by intersection. Intersection graphs have many
applications and have been studied in details from an algorithmic point of
view, one problem being to recognize whether a graph is in a given family,
another one to improve the complexity of classical problems knowing that the
input is in the family. We refer the reader to the books [Gol80, MM99] for
many such examples.

Intersection graph models have also been of interest in the random graph
community. Here is a selection of references on the topic.

  * •

Random interval graphs have been introduced and studied by Scheinerman [Sch88]
in the 80’s – see also Justicz, Scheinerman and Winkler [JSW90]. The model
considered is the “uniform” model on intervals, _i.e._ the extremities
$a_{i}$, $b_{i}$ of the intervals are taken i.i.d. uniformly at random in
$[0,1]$, conditionally to $a_{i}<b_{i}$. We refer also to [DHJ13] for a
discussion on graphon limits of such models and further references on random
interval graphs.

  * •

The inversion graph of a uniform random permutation of size $n$ has been
recently studied: see Bhattacharya and Mukherjee [BM17] for results on the
degree sequence and Gürerk, Işlak and Yıldız [GIY19] for results on the degree
distributions, isolated vertices, cliques and connected components. We also
refer to Acan and Pittel [AP13] for an analysis of inversion graphs of uniform
random permutations with a fixed number of inversions (thus fixing the number
of edges).

  * •

In a similar spirit, Acan has studied various properties of the intersection
graph of a uniform random chord diagram in [Aca17]; see also Acan and Pittel
[AP17] for an analysis of intersection graphs of uniform random chord diagrams
with a fixed number of crossings (fixing again the number of edges in the
graph).

  * •

The graphon limit of a uniform random string graph has been considered by
Janson and Uzzell [JU17], who identified a set of possible limit points, and
conjectured the actual graphon limit.

  * •

In a slightly different direction, there is an important literature around a
model called random intersection graphs, see [BGJ+15] and references therein;
here a random set is attached to each vertex (most of the time a uniform
random subset with a fixed number of elements of a given set) and two vertices
are connected if their associated sets have a nonempty intersection. This
model is different from the ones cited above in that all graphs can be
obtained this way, and not only graphs from a given family.

###  1.2. Uniform seeds versus uniform graphs and overview of the results

A noticeable fact in the literature review above is that, in most cases, the
authors consider a natural distribution on the set of _seeds_ (most of the
time the uniform one, or the uniform one subject to some size constraint).
This induced a distribution on intersection graphs which is not uniform on the
corresponding class. (An exception to that is the work of Janson and Uzzell on
string graphs [JU17].) In contrast, there is a growing literature on uniform
random graphs in other classes (planar graphs [Noy14] or graphs embeddable in
a given surface [DKS17], subcritical block-stable classes [PSW16], perfect
graphs [MY19], cographs [BBF+22b, Stu21, BBF+22a], …). For families of
intersection graphs however, studying (or sampling) a uniform graph in the
family is often harder than a uniform seed.

It is therefore natural to try to transfer results obtained from the uniform
seed model to the uniform graph one, and this is the main purpose of our work.
To this effect, we rely on some known results that, in many families of
intersection graphs, there exists some notion of indecomposable graphs, for
which indecomposable graphs can be represented by a unique seed (up to some
trivial symmetries). Such uniqueness results have typically been discovered in
the graph algorithm literature (they are helpful to design recognition
algorithms), and will be useful as well for our purposes.

In this article, we illustrate this approach on three of the families of
intersection graphs listed in the previous section, namely permutation graphs,
circle graphs, and unit interval graphs. Interestingly, we need to use a
different notion of indecomposability for each family: prime for the modular
decomposition for permutation graphs, prime for the split decomposition for
circle graphs, and connected for unit interval graphs.

For each of these three families, we obtain a “scaling limit” result for a
uniform random graph in the class. Asymptotic results for the number of
cliques of size $k$ ($k$ fixed) in a uniform random graph in each of these
three families are also given.

Permutation graphs and circle graphs are typically dense, in the sense that
the number of edges is quadratic with respect to the number of vertices. We
thus use the notion of dense graph limits, a.k.a. graphon convergence.
(Definitions and necessary background on graphons will be given in Section
3.1.) Namely, we prove that a uniform random permutation (resp. circle) graph
tends almost surely (a.s. for short) towards a deterministic limiting graphon
$W^{(\mathrm{perm})}$ (resp. $W^{(\mathrm{circle})}$). The asymptotic result
for the number of cliques of size $k$ ($k$ fixed) follows as a corollary.

On the other hand, uniform random unit interval graphs with $n$ vertices
typically have $\Theta(n^{3/2})$ edges. We study their limit for the so-called
Gromov–Prokhorov (GP) topology, which encodes typical distances between
randomly sampled vertices. (GP convergence is rewiewed in Section 3.2.) We
prove that, with respect to this topology, a uniform random unit interval
graph converges towards the unit interval $[0,1]$, endowed with a random
metric computed from a Brownian excursion. The asymptotics of the number of
cliques can also been related to Brownian excursions (though this is not a
direct consequence of the GP convergence). The limiting object and the
limiting random variables for renormalized numbers of cliques are here random,
while they are deterministic for permutation and circle graphs.

######  Remark 1.1.

It would be interesting to study uniform random interval graphs and compare
them with the interval graphs constructed from uniform random intervals
considered by Scheinerman and collaborators [Sch88, JSW90]. Interval graphs
are naturally encoded by matchings of the set $\\{1,\dots,2n\\}$ (the numbers
represent the extremities of all intervals in increasing order, and the
endpoints of a given interval are matched together). A criterion for unique
representability has been given in [Han82, Theorem 1], but it is intricate and
not naturally amenable to the methods of this paper.

Another interesting family of intersection graphs is that of string graphs: as
mentioned above, a conjecture regarding the graphon limit of a uniform random
string graph has been formulated by Janson and Uzzell [JU17]. But in the case
of string graphs, we are not aware of an encoding through purely combinatorial
objects.

Together with interval and string graphs, the three families of intersection
graphs studied here – permutation, circle and unit interval graphs – are the
most studied, explaining our choice to consider them here.

###  1.3. Outline of the article

  * •

Section 2 gives more background on the graph classes studied in this paper.
All the results of the paper are then stated precisely.

  * •

Section 3 reviews the notions of graphon convergence and Gromov–Prokhorov
convergence.

  * •

Then we separately deal with each family:

    * –

Section 4 is devoted to permutation graphs;

    * –

Section 5 is devoted to circle graphs (for ease of reading, the proofs of two
technical results are postponed to the Appendix A);

    * –

Section 6 is devoted to unit interval graphs.

##  2\. Results

###  2.1. Permutation graphs

Permutation graphs have been introduced by Even, Lempel and Pnueli in [PLE71,
EPL72]. For a permutation $\sigma$, we denote by $G^{\ell}_{\sigma}$ the graph
with $|\sigma|$ vertices obtained by the following construction:

  * •

$G^{\ell}_{\sigma}$ has vertex set $\left\\{1,\dots,|\sigma|\right\\}$ ;

  * •

put an edge $i\leftrightarrow j$ if and only if $\\{i,j\\}$ is an inversion of
$\sigma$, _i.e._ $\left(\sigma(i)-\sigma(j)\right)(i-j)<0$.

We denote $G_{\sigma}$ the unlabeled version of $G^{\ell}_{\sigma}$. It is
called the _inversion graph_ of $\sigma$. A _permutation graph_ is a
(unlabeled) graph $G$ such that $G=G_{\sigma}$ for some permutation $\sigma$.
Such a permutation $\sigma$ is then said to _realize_ $G$, or is called a
realizer of $G$.

Permutation graphs have been intensively studied from an algorithmic point of
view, see, _e.g._ , [CP10] and references therein, or [BBC+07] for an
application to genomics.

We obtain the following scaling limit result for a uniform random graph in
this class, with an explicit deterministic limit in the sense of graphons.

######  Theorem 2.1.

For each $n\geq 1$, let ${\bm{G}}_{n}$ be a uniform random unlabeled
permutation graph with $n$ vertices. In the space of graphons,

${\bm{G}}_{n}\,\stackrel{{\scriptstyle
n\to+\infty}}{{\longrightarrow}}\,W^{(\mathrm{perm})},\ \text{a.s.},$

where $W^{(\mathrm{perm})}$ is defined in Definition 4.1 and Proposition 4.2.

Figure 2. Left: The adjacency matrix of the permutation graph $G_{\sigma_{n}}$
of a uniform random permutation $\sigma_{n}$ of size $n=1000$, where vertices
are ordered by decreasing degrees. Note that $G_{\sigma_{n}}$ is not a uniform
permutation graph but Proposition 4.2 ensures that this is a fair
approximation of the graphon $W^{(\mathrm{perm})}$. Right: The average of $50$
independent adjacency matrices of graphs $G_{\sigma_{n}}$ for $n=1000$, all
ordered by decreasing degrees.

To illustrate Theorem 2.1, we plot in Fig. 2 the adjacency matrix of a large
random permutation graph (informally, graphon convergence can be seen as the
convergence of the rescaled adjacency matrix with a well-chosen order of
vertices).

An interesting feature of graphon convergence is that it encodes the
convergence of all subgraph counts, correctly renormalized (see, _e.g._ ,
[Lov12, Chapter 11]). In the present case, the density of cliques of size $k$
(for all fixed $k$) in the limiting graphon $W^{(\mathrm{perm})}$ can be
easily determined (see Proposition 4.8). As a consequence of Theorem 2.1 we
obtain the following estimates:

$\frac{\\#\left\\{\text{edges of
}{\bm{G}}_{n}\right\\}}{\binom{n}{2}}\to\frac{1}{2}\
\text{a.s.},\qquad\frac{\\#\left\\{\text{triangles of
}{\bm{G}}_{n}\right\\}}{\binom{n}{3}}\to\frac{1}{6}\ \text{a.s.},$

and more generally for all $k\geq 1$,
$\displaystyle\frac{\\#\left\\{\text{cliques of size $k$ in
}{\bm{G}}_{n}\right\\}}{\binom{n}{k}}\to\frac{1}{k!}\ $a.s..

###  2.2. Circle graphs

The second family considered in this article is the one of circle graphs,
introduced by Even and Itai [EI71]. Circle graphs are intersection graphs of
chords in a disk. These chords can be seen as a matching between points
(corresponding to the endpoints of the chords) along a circle. Circle graphs
have been extensively studied from an algorithmic point of view, see the
survey [DGS14] and references therein. The complexity of their recognition
posed in [Gol80] has received considerable attention, see _e.g_ [Naj85, Bou88,
GSH89], and has finally been shown to be subquadratic in [GPT+14]. Among other
things, circle graphs appear naturally in some routing problems, see [She95].

As for permutation graphs, we obtain an explicit deterministic limit in the
sense of graphons for a uniform random graph in the class.

######  Theorem 2.2.

For each $n\geq 1$, let ${\bm{G}}_{n}$ be a uniform random unlabeled circle
graph with $n$ vertices. In the space of graphons,

${\bm{G}}_{n}\,\stackrel{{\scriptstyle
n\to+\infty}}{{\longrightarrow}}\,W^{(\mathrm{circle})},\ \text{a.s.},$

where $W^{(\mathrm{circle})}$ is defined in Definition 5.1 and Proposition
5.2.

Figure 3. Left: The adjacency matrix of the intersection graph $G_{M_{n}}$ of
a uniform matching $M_{n}$ of size $n=1000$, where vertices are ordered by
decreasing degrees. Note that $G_{M_{n}}$ is not a uniform circle graph but
Proposition 5.2 ensures that this is a fair approximation of the graphon
$W^{(\mathrm{circle})}$. Right: The average of $50$ independent adjacency
matrices of graphs $G_{M_{n}}$ for $n=1000$, all ordered by decreasing
degrees.

Theorem 2.2 is illustrated in Fig. 3. As for $W^{(\mathrm{perm})}$, densities
of cliques in $W^{(\mathrm{circle})}$ can be computed easily (see Proposition
5.15), and Theorem 2.2 has the following concrete corollary:

$\frac{\\#\left\\{\text{edges of
}{\bm{G}}_{n}\right\\}}{\binom{n}{2}}\to\frac{1}{3}\
\text{a.s.},\qquad\frac{\\#\left\\{\text{triangles of
}{\bm{G}}_{n}\right\\}}{\binom{n}{3}}\to\frac{1}{15}\ \text{a.s.},$

and more generally for all $k\geq 1$,
$\displaystyle\frac{\\#\left\\{\text{cliques of size $k$ in
}{\bm{G}}_{n}\right\\}}{\binom{n}{k}}\to\frac{2^{k}\,k!}{(2k)!}\ $a.s..

###  2.3. Unit interval graphs

The third family studied in this article is the one of unit interval graphs.
Unit interval graphs are intersection graphs of intervals of unit length. From
[Rob69] they are equivalent to proper interval graphs, which are intersection
graphs of sets of intervals, where no interval contains another one, and also
to claw-free interval graphs (the claw, also denoted $K_{1,3}$, is the graph
with $4$ vertices and $3$ edges such that $1$ vertex is linked with the $3$
other ones). It is possible to test whether a given graph is a unit interval
graph in linear time [LO93]. We refer the reader to [SZ04] for other
equivalent characterizations and algorithmic results on unit interval graphs.

We prove the convergence of unit interval graphs with a renormalized distance
function in the sense of the Gromov–Prokhorov topology. To this end, for a
finite graph $G$ with vertex set $V_{G}$, we denote $d_{G}$ the associated
graph distance and $m_{V_{G}}$ the uniform distribution on $V_{G}$. We recall
that a _metric measure space_ (called mm-space for short) is a triple
$(X,d,\mu)$, where $(X,d)$ is a metric space and $\mu$ a probability measure
on $X$ (for the Borel $\sigma$-algebra induced by $d$). In the following,
$\operatorname{Leb}$ denotes the Lebesgue measure on $[0,1]$.

######  Theorem 2.3.

Let $\bm{G}_{n}$ be a uniform random unlabeled unit interval graph with $n$
vertices. The following convergence of random mm-spaces holds in distribution
in the Gromov–Prokhorov topology:

$(V_{\bm{G}_{n}},\tfrac{1}{\sqrt{n}}\,d_{\bm{G}_{n}},m_{V_{\bm{G}_{n}}})\longrightarrow([0,1],\tfrac{1}{\sqrt{2}}\,d_{\mathbb{e}},\operatorname{Leb}),$

where $\mathbb{e}$ is a random Brownian excursion of length 1 and
$d_{\mathbb{e}}$ is defined by the formula: for $x<y$ in $[0,1]$, we have

(1) $d_{\mathbb{e}}(x,y)=\int_{x}^{y}\frac{dt}{\mathbb{e}(t)}.$

Theorem 2.3 is illustrated on Fig. 4.

Figure 4. Two samples of uniform connected unit interval graphs with $n=150$
vertices. Plots of adjacency matrices are not relevant for nondense graphs so
we rather show geometric embeddings of graphs (they were obtained with the
python library networkx). These graph drawings illustrate the fact that the
limiting object is one-dimensional with a variable density of vertices.

In particular, graph distances in $\bm{G}_{n}$ are typically of order
$\sqrt{n}$. The intuition behind the nice form of (1) is given in Lemma 6.5:
this combinatorial lemma indeed rewrites the distances in $\bm{G}_{n}$ in
terms of a sum of inverses of some kind of height function of a Dyck path
encoding the graph structure.

Though this does not follow from Gromov-Prokhorov convergence, we are also
able to describe the asymptotic behavior of the number of cliques of size $k$
($k$ fixed) in $\bm{G}_{n}$. We obtain the following theorem.

######  Theorem 2.4.

Let $\bm{G}_{n}$ be a uniform random unit interval graph with $n$ vertices.
Let also $\mathbb{e}$ be a Brownian excursion and
$X_{k}=\int_{0}^{1}\mathbb{e}(t)^{k}dt$. Then for any $K\geq 1$, we have the
following joint convergence in distribution:

$\left( \frac{\\#\left\\{\text{cliques of size $k$ in
}\bm{G}_{n}\right\\}}{n^{\frac{k+1}{2}}}\right)_{2 \leq k\leq
K}\,\stackrel{{\scriptstyle
n\to+\infty}}{{\longrightarrow}}\,\left(\frac{2^{\frac{k-1}{2}}}{(k-1)!}
X_{k-1}\right)_{2 \leq k\leq K},$

where the $X_{k}$ in the right-hand side are computed from the same
realization of the excursion $\mathbb{e}$.

Observe that the renormalization factor differs from the case of permutation
graphs and circle graphs. In particular for $k=2$, Theorem 2.4 says that
$\bm{G}_{n}$ has typically $\Theta(n^{3/2})$ edges and thus confirms that it
is nondense.

The random variables $(X_{k})_{k}$ have been studied in the probabilistic
literature: we refer to the survey [Jan07] for an extensive study and many
bibliographic pointers regarding $X_{1}$, to [Ngu04] for formulas for the
joint Laplace transform and joint moments of $(X_{1},X_{2})$ and finally to
[Ric09] for the computation of joint moments of $(X_{1},\dots,X_{K})$ for
general $K$. Unlike in the case of permutation and circle graphs, these
limiting random variables are not deterministic, _i.e._ there is no
concentration of the number of cliques of size $k$ in $\bm{G}_{n}$ around its
mean.

##  3\. Preliminary: convergence of random graphs

In this section, we present the two notions of convergence for random graphs
used in this paper, namely graphon convergence and Gromov–Prokhorov
convergence. The necessary material for the proofs of our main theorems is
recalled.

###  3.1. Dense graph limits and graphons

Recall that a function $\phi:[0,1]\to[0,1]$ is Lebesgue-preserving, if, for
any uniform random variable $U$ on $[0,1]$, the variable $\phi(U)$ is also
uniform on $[0,1]$.

######  Definition 3.1.

A graphon is an equivalence class of symmetric functions $[0,1]^{2}\to[0,1]$,
under the equivalence relation $\sim$, where $w\sim u$ if there exists an
invertible Lebesgue-preserving function $\phi:[0,1]\to[0,1]$ such that
$w(\phi(x),\phi(y))=u(x,y)$ for almost every $x,y\in[0,1]$.

Intuitively, a graphon is a continuous analogue of the adjacency matrix of a
graph, viewed up to relabeling of its continuous vertex set. Finite graphs are
naturally embedded into graphons as follows.

######  Definition 3.2.

The graphon $W_{G}$ associated to a labeled graph $G$ with $n$ vertices
(labeled from $1$ to $n$) is the equivalence class of the function
$w_{G}:[0,1]^{2}\to[0,1]$ where

$w_{G}(x,y)=A_{\lceil nx\rceil,\lceil ny\rceil}\in\\{0,1\\}$

and $A$ is the adjacency matrix of the graph $G$.

Since any relabeling of the vertex set of $G$ gives the same graphon $W_{G}$,
the above definition immediately extends to unlabeled graphs. The space of
graphons is endowed with a pseudo-metric $\delta_{\Box}$ called the cut metric
(see all definitions in [Lov12, Ch.8]). Denote by
$\widetilde{\mathcal{W}_{0}}$ the space of graphons where we identify
$W,W^{\prime}$ whenever $\delta_{\Box}(W,W^{\prime})=0$. The metric space
$(\widetilde{\mathcal{W}_{0}},\delta_{\Box})$ is compact [Lov12, Theorem
9.23]. In the sequel, we think of graphons as elements in
$\widetilde{\mathcal{W}_{0}}$ and convergences of graphons are to be
understood with respect to the distance $\delta_{\Box}$.

Accordingly, given a sequence of graphs $(H_{n})_{n}$, we say that
$(H_{n})_{n}$ converges to a graphon $W$ when $(W_{H_{n}})_{n}$ converges to
$W$.

#### Sampling from graphons and subgraph densities

Consider a graphon $W$ and one of its representatives $w:[0,1]^{2}\to[0,1]$.
Denote by $\operatorname{Sample}_{k}(W)$ the unlabeled random graph built as
follows: $\operatorname{Sample}_{k}(W)$ has vertex set
$\\{v_{1},v_{2},\dots,v_{k}\\}$ and, letting $\vec{X}^{k}=(X_{1},\dots,X_{k})$
be i.i.d. uniform random variables in $[0,1]$, we connect vertices $v_{i}$ and
$v_{j}$ with probability $w(X_{i},X_{j})$ (these events being independent,
conditionally on $(X_{1},\cdots,X_{k})$).

Then the density of a graph $g$ with $k$ vertices in a graphon $W$ is defined
as

$\displaystyle\operatorname{Dens}(g,W)$
$\displaystyle=\mathbb{P}(\operatorname{Sample}_{k}(W)=g).$

As briefly mentioned in the introduction, a remarkable aspect of graphon
convergence is that it is equivalent to the convergence of all subgraph
densities, see, _e.g._ , [Lov12, Chapter 11].

In the present article, we will use the fact that for large $k$ a graphon is
well approximated by $\operatorname{Sample}_{k}(W)$, w.r.t. the distance
$\delta_{\Box}$. More precisely we have the following.

######  Lemma 3.3.

For every graphon $W$ and every $\varepsilon>0$, we have

(2)
$\sum_{k=1}^{+\infty}\mathbb{P}(\delta_{\Box}(\operatorname{Sample}_{k}(W),W)\geq\varepsilon)<+\infty.$

Consequently, the sequence of random graphs
$(\operatorname{Sample}_{k}(W))_{k}$ converges a.s. to $W$ in the sense of
graphons, and any graphon $W$ is uniquely determined by the distribution of
its samples.

###### Proof.

From [Lov12, Lemma 10.16], there exists a constant $c>0$ such that for every
graphon $W$ and every $k\geq 1$,

(3)
$\mathbb{P}\bigg{[}\delta_{\Box}(\operatorname{Sample}_{k}(W),W)\geq\frac{c}{\sqrt{\log
k}}\bigg{]}\leq\exp\left(\frac{-k}{2\log(k)}\right).$

Using this, for any fixed $\varepsilon>0$, we have, for $k$ large enough,

$\mathbb{P}\big{[}\delta_{\Box}(\operatorname{Sample}_{k}(W),W)\geq\varepsilon\big{]}\leq\mathbb{P}\bigg{[}\delta_{\Box}(\operatorname{Sample}_{k}(W),W)\geq\frac{c}{\sqrt{\log
k}}\bigg{]}\leq\exp\left(\frac{-k}{2\log(k)}\right),$

so that
$\mathbb{P}(\delta_{\Box}(\operatorname{Sample}_{k}(W),W)\geq\varepsilon)$ is
summable in $k$, as claimed.

The almost sure convergence of $(\operatorname{Sample}_{k}(W))_{k}$ to $W$ can
be found, e.g., in [Lov12, Proposition 11.32], but let us explain how to
deduce it from (2), since we will reuse this (classical) argument later. Using
Borel–Cantelli lemma, (2) implies that $\mathbb{P}(A_{\varepsilon})=1$, where
$A_{\varepsilon}$ is the event “$\exists K,\forall k\geq
K,\delta_{\Box}(\operatorname{Sample}_{k}(W),W)<\varepsilon$”. Taking a
countable intersection, we have
$\mathbb{P}(\bigcap_{\varepsilon\in\mathbb{Q}_{+}^{*}}A_{\varepsilon})=1$,
implying that $\delta_{\Box}(\operatorname{Sample}_{k}(W),W)$ converges a.s.
to $0$. ∎

###  3.2. Metric measure spaces and the Gromov–Prokhorov topology

We now formally introduce the Gromov–Prokhorov topology used in Theorem 2.3.
Note that the material below will only be used in Section 6.

######  Definition 3.4.

A metric measure space (called mm-space for short) is a triple $(X,d,\mu)$,
where $(X,d)$ is a complete and separable metric space and $\mu$ a Borel
probability measure on $X$.

A finite connected graph $G$ can be seen as a mm-space
$(V_{G},d_{G},m_{V_{G}})$, where $V_{G}$ is the vertex set of the graph,
$d_{G}$ is the graph distance, and $m_{V_{G}}$ the uniform distribution on
$V_{G}$.

We let $\mathbb{M}$ be the set of all mm-spaces111To avoid Russell’s paradox,
throughout the section, we actually take the set of mm-spaces whose elements
are not themselves metric spaces., modulo the following relation:
$(X,d,\mu)\sim(X^{\prime},d^{\prime},\mu^{\prime})$ if there is an isometric
embedding $\Phi:X\to X^{\prime}$ such that the pushforward222Recall that
$\Phi_{*}$ is defined as follows: $\forall A\subseteq X^{\prime}$,
$\Phi_{*}(\mu)(A)=\mu(\Phi^{-1}(A))$ where $\Phi^{-1}(A)=\\{x\in
X\mid\Phi(x)\in~{}A\\}$. measure $\Phi_{*}(\mu)$ satisfies
$\Phi_{*}(\mu)=\mu^{\prime}$. Note that $\Phi$ does not need to be invertible,
so that we need to consider the closure of that relation by symmetry and
transitivity.

On the set $\mathbb{M}$, one can define a distance as follows. First we recall
the notion of Prokhorov distance. For Borel probability measures $\mu$ and
$\nu$ on the same metric space $Y$, we set

$d_{P}(\mu,\nu)=\inf\big{\\{}\varepsilon>0:\,\mu(A)\leq\nu(A^{\varepsilon})+\varepsilon\text{
and }\nu(A)\leq\mu(A^{\varepsilon})+\varepsilon\text{ for all measurable
}A\subseteq Y\big{\\}},$

where $A^{\varepsilon}$ is the $\varepsilon$-halo of $A$, _i.e._ the set of
all points at distance at most $\varepsilon$ of $A$. It is well-known that
this distance metrizes the weak convergence of probability measures.

Next we define the Gromov–Prokhorov (GP) distance which induces a topology on
mm-spaces. Given two mm-spaces $(X,d,\mu)$ and
$(X^{\prime},d^{\prime},\mu^{\prime})$, we set

$d_{\text{GP}}\big{(}(X,d,\mu),(X^{\prime},d^{\prime},\mu^{\prime})\big{)}=\inf_{(Y,d_{Y}),\Phi,\Phi^{\prime}}d_{P}\big{(}\Phi_{*}(\mu),\Phi^{\prime}_{*}(\mu^{\prime})\big{)},$

where the infimum is taken over isometric embeddings $\Phi:X\to Y$ and
$\Phi^{\prime}:X^{\prime}\to Y$ into a common metric space $(Y,d_{Y})$. One
can prove [GPW09, Section 5] that $d_{\text{GP}}$ is a distance on
$\mathbb{M}$ and that the resulting metric space $(\mathbb{M},d_{\text{GP}})$
is complete and separable.

A nice property (which we will however not use in this paper) is that the
convergence of a sequence of mm-spaces $(X_{n},d_{n},\mu_{n})$ for the
$d_{\text{GP}}$ distance is equivalent to the convergence, for any $k$, of the
matrix $(d_{n}(x_{i},x_{j}))_{1\leq i,j\leq k}$ recording the distances
between $k$ independent random elements of $X_{n}$, having distribution
$\mu_{n}$ (see [GPW09, Th.5] or [Jan20, Sec.4]).

Instead of $d_{\text{GP}}$ we will use in our proof another distance, which
has been shown by Löhr [Loh13] to induce the same topology.

######  Definition 3.5 (Box distance).

The box distance $\Box$ between two mm-spaces is defined as

$\Box((X,d,\mu),(X^{\prime},d^{\prime},\mu^{\prime}))=\inf_{(R,\nu)}\ \
\max(\operatorname{disc}(R),1-\nu(R))$

where

  * •

the infimum is taken over all pairs $(R,\nu)$ where

    * –

$R$ is a Borel subset of $X\times X^{\prime}$

    * –

$\nu$ is a coupling of $\mu$ and $\mu^{\prime}$, _i.e._ a Borel measure on
$X\times X^{\prime}$ whose marginals are $\mu$ and $\mu^{\prime}$;

  * •

$\operatorname{disc}(R)$ is the _discrepancy_ defined by

$\operatorname{disc}(R)=\sup_{(x_{1},x^{\prime}_{1}),(x_{2},x^{\prime}_{2})\in
R}\left|d(x_{1},x_{2})-d^{\prime}(x^{\prime}_{1},x^{\prime}_{2})\right|.$

As said above, we have the following result.

######  Theorem 3.6 (Corollary 3.2 in [Loh13], see also [Jan20]).

Distances $\Box$ and $d_{\text{GP}}$ induce the same topology on $\mathbb{M}$.

Finding a good upper bound on the distance $\Box$ requires to construct a pair
$(R,\nu)$ with $\nu(R)$ large and a small discrepency. This is often easier
than constructing isometric embedding $\Phi$ and $\Phi^{\prime}$ of $X$ and
$X^{\prime}$ into a common metric space $Y$, as required to find an upper
bound for $d_{\text{GP}}$. This explains that Theorem 3.6 is often useful to
prove GP convergence, and our proof of Theorem 2.3 follows this path.

##  4\. Permutation graphs

The main goal of this section is to prove Theorem 2.1: uniform random
permutation graphs $(\bm{G}_{n})$ converge to the graphon
$W^{(\mathrm{perm})}$ defined in Definition 4.1 and Proposition 4.2 below.

Our proof starts by observing that the inversion graph of a uniform random
permutation (which is _not_ a uniform random permutation graph) converges to
$W^{(\mathrm{perm})}$ (see again Proposition 4.2). In order to transfer this
result onto uniform permutation graphs, we will go through _modular-prime_
permutation graphs (introduced in Section 4.2 below). Indeed, one can control
the number of realizers of a modular-prime permutation graph (Proposition
4.6). We combine all this in Section 4.3 to prove Theorem 2.1. Finally,
Section 4.4 deduces from Theorem 2.1 an asymptotic estimate of the number of
cliques of size $k$ in a uniform permutation graph.

###  4.1. Graphon limit of the inversion graph of a uniform random permutation

For any $n$, let $\sigma_{n}$ denote a uniform random permutation of size $n$.
In this section we determine the limit in the sense of graphons of its
inversion graph $G_{\sigma_{n}}$.

######  Definition 4.1.

Let

$\begin{array}[]{r c c c}\Psi:&[0,1]&\to&[0,1]^{2}\\\
&x&\mapsto&(\Psi_{1}(x),\Psi_{2}(x))\end{array}$

be any Lebesgue-preserving measurable function, meaning
$\Psi_{*}(\mathrm{Lebesgue}_{[0,1]})=\mathrm{Lebesgue}_{[0,1]^{2}}$ . The
graphon $W^{(\mathrm{perm})}_{\Psi}$ is defined as (the equivalence class of)

$W^{(\mathrm{perm})}_{\Psi}(x,y)=\mathbb{1}_{(\Psi_{1}(x)-\Psi_{1}(y))(\Psi_{2}(x)-\Psi_{2}(y))<0}\qquad\text{
for all }x,y\in[0,1].$

In words, $W^{(\mathrm{perm})}_{\Psi}$ takes values in $\\{0,1\\}$ and is such
that $W^{(\mathrm{perm})}_{\Psi}(x,y)=1$ exactly when the two points
$\Psi(x),\Psi(y)$ form an inversion in the unit square, _i.e._ when one of the
two points is at the bottom right of the other.

######  Proposition 4.2.

The equivalence class of $W^{(\mathrm{perm})}_{\Psi}$ is independent of the
choice of the Lebesgue-preserving function $\Psi$. Moreover, let us consider,
for every $n\geq 1$, a uniform random permutation $\sigma_{n}$ of size $n$.
Then

$G_{\sigma_{n}}\stackrel{{\scriptstyle\text{a.s.}}}{{\to}}W^{(\mathrm{perm})},$

where $W^{(\mathrm{perm})}:=W^{(\mathrm{perm})}_{\Psi}$ for an arbitrary
Lebesgue-preserving function $\Psi$.

###### Proof.

We first identify for every $n$ the distribution of
$\mathrm{Sample}_{n}(W^{(\mathrm{perm})}_{\Psi})$. By definition, it is
constructed by taking $X_{1}$, …, $X_{n}$ independently and uniformly in
$[0,1]$, and by connecting $v_{i}$ and $v_{j}$ if and only if
$W^{(\mathrm{perm})}_{\Psi}(X_{i},X_{j})=1$ (recall that
$W^{(\mathrm{perm})}_{\Psi}$ is $\\{0,1\\}$-valued). Let
$(a_{i},b_{i})=\Psi(X_{i})$. Since $\Psi$ is Lebesgue-preserving, the $n$
points $(a_{1},b_{1}),\dots,(a_{n},b_{n})$ are i.i.d. uniform points in
$[0,1]^{2}$. Up to relabeling simultaneously $(X_{i})_{i\leq n}$,
$(a_{i})_{i\leq n}$ and $(b_{i})_{i\leq n}$, we assume $a_{1}<\dots<a_{n}$.
Then there exists a unique permutation $\pi$ such that

$b_{\pi^{-1}(1)}<\dots<b_{\pi^{-1}(n)}.$

The permutation $\pi$ is a uniform permutation of size $n$. Then we have

$W^{(\mathrm{perm})}_{\Psi}(X_{i},X_{j})=1\Longleftrightarrow(a_{i}-a_{j})(b_{i}-b_{j})<0\Longleftrightarrow(i-j)(\pi(i)-\pi(j))<0,$

_i.e._ $(i,j)$ is an inversion of $\pi$. Thus
$\mathrm{Sample}_{n}(W^{(\mathrm{perm})}_{\Psi})$ is the inversion graph of
$\pi$. Since $\pi$ is uniform,

(4)
$\mathrm{Sample}_{n}(W^{(\mathrm{perm})}_{\Psi})=G_{\pi}\stackrel{{\scriptstyle\text{(d)}}}{{=}}G_{\sigma_{n}}.$

In particular, we see that, for any $n\geq 1$, the distribution of
$\mathrm{Sample}_{n}(W^{(\mathrm{perm})}_{\Psi})$ is independent of $\Psi$.
Since a graphon is determined by the distribution of its samples,
$W^{(\mathrm{perm})}_{\Psi}$ is indeed independent of $\Psi$, as claimed.

Using Eq. 4, we get that for every fixed $\varepsilon>0$

$\mathbb{P}(\delta_{\Box}(G_{\sigma_{n}},W^{(\mathrm{perm})})\geq\varepsilon)=\mathbb{P}(\delta_{\Box}(\mathrm{Sample}_{n}(W^{(\mathrm{perm})}),W^{(\mathrm{perm})})\geq\varepsilon),$

and the right-hand side is summable by Lemma 3.3. Using the Borel–Cantelli
Lemma as in the proof of Lemma 3.3, we get that
$G_{\sigma_{n}}\stackrel{{\scriptstyle\text{a.s.}}}{{\to}}W^{(\mathrm{perm})}$,
concluding the proof. ∎

######  Remark 4.3.

One can more generally define graphons as (equivalence classes) of measurable
functions $\mathcal{S}\times\mathcal{S}\to[0,1]$, where $\mathcal{S}$ is any
probability space, see, e.g., [Lov12, Chapter 13]. With this convention, the
graphon $W^{(\mathrm{perm})}$ has a simple representative $W$, using
$\mathcal{S}=[0,1]^{2}$, namely

$W((x,x^{\prime}),(y,y^{\prime}))=\mathbb{1}_{(x-y)(x^{\prime}-y^{\prime})<0}.$

A similar remark holds for the limit $W^{(\mathrm{circle})}$ of circle graphs
defined later in Definition 5.1.

###  4.2. Modular-prime permutation graphs, simple permutations and number of
realizers

The random permutation graph $G_{\sigma_{n}}$ is not a uniform random graph
taken among all permutation graphs with $n$ vertices, since some permutation
graphs have more permutations realizing them than others. Our next goal is to
transfer the convergence result for $G_{\sigma_{n}}$ (Proposition 4.2) to a
uniform random permutation graph $\bm{G}_{n}$ on $n$ vertices. To do that, we
use the notion of modular-prime graphs, and show that the number of realizers
is well-controlled for these graphs.

######  Definition 4.4.

A module $M$ in a graph $G$ is a subset of vertices of $G$ such that for all
$m$, $m^{\prime}$ in $M$, and $u$ not in $M$ we have that, either both
$\\{m,u\\}$ and $\\{m^{\prime},u\\}$ are edges of $G$, or none of them is.

A graph $G$ is called modular-prime if it contains no nontrivial modules,
_i.e._ no modules other than $\emptyset$, $V_{G}$ and the singletons $\\{v\\}$
(for $v\in V_{G}$).

There exists a corresponding notion for permutations, introduced by Albert and
Atkinson in [AA05]. We use the standard notation $[n]:=\\{1,\dots,n\\}$.

######  Definition 4.5.

An interval $I$ in a permutation $\sigma$ is a set of contiguous indices $I$,
whose image $\sigma(I)$ by $\sigma$ is also contiguous.

A permutation $\sigma$ of size $n$ is called simple if it has no nontrivial
intervals, _i.e._ no intervals other than $\emptyset$, $[n]$ and the
singletons $\\{i\\}$ (for $i\in[n]$).

For example, $I=\left\\{3,4,5\right\\}$ and $I^{\prime}=\left\\{6,7\right\\}$
are a nontrivial intervals of the permutation $\sigma$ defined by

$\begin{array}[]{r c c c c c c c}i:&1&2&3&4&5&6&7\\\
\sigma(i):&7&1&4&6&5&2&3\end{array}$

It is easily seen that if $I$ is an interval in $\sigma$, then the
corresponding vertices form a module in $G_{\sigma}$. The converse is not true
in general but it holds that $G_{\sigma}$ is modular-prime if and only if
$\sigma$ is simple. (This observation is due to F. de Montgolfier [Mon03], see
also [HP10, Lemma 20].)

Moreover, we have the following remarkable property.

######  Proposition 4.6.

For any modular-prime permutation graph $G$, there are at most $4$
permutations $\tau$, all simple, such that $G=G_{\tau}$.

This result is not explicitly stated in the literature, but follows easily
combining various results on comparability and permutation graphs, all
recalled in [Gol80]. In the remaining part of this section, we explain how
results in [Gol80] imply Proposition 4.6. We also refer to [CP10] for a
general discussion on how to construct the set of realizers of a permutation
graph using its modular decomposition.

We first state a useful characterization of permutation graphs given in
[Gol80]. For this, recall that the complement of a graph $G=(V,E)$ is
$\bar{G}=(V,\bar{E})$ where $\\{u,v\\}\in\bar{E}$ if and only if $u\neq v$ and
$\\{u,v\\}\notin E$. Recall also that a graph $G=(V,E)$ is a comparability
graph if and only if there exists a partial order $\prec$ on $V$ such that
$\\{u,v\\}$ is an edge of $G$ if and only if $u\prec v$ or $v\prec u$.
Equivalently, a graph $G=(V,E)$ is a comparability graph if its edges admit a
transitive orientation. It is known [Gol80, Theorem 7.1] that a graph $G$ is a
permutation graph if and only if $G$ and $\bar{G}$ are comparability graphs.

In addition, in the proof of [Gol80, Theorem 7.1], it is shown that, from each
pair $(F,\bar{F})$ of transitive orientations of $G$ and $\bar{G}$, we can
build a realizer $\pi$ of $G$.

Moreover, it easy to see that any realizer $\pi$ can be obtained in this way.
Indeed, let $G$ be a permutation graph, and $\pi$ be a realizer of $G$. Then
there is a labeling $v_{1},...,v_{n}$ of the vertices of $G$ such that
$\\{v_{i},v_{j}\\}\in V_{G}\Leftrightarrow\left(\pi(i)-\pi(j)\right)(i-j)<0$.
Hence $\\{v_{i},v_{j}\\}\in
V_{\bar{G}}\Leftrightarrow\left(\pi(i)-\pi(j)\right)(i-j)>0$. We build the
orientation $F$ (resp. $\bar{F}$) by orienting any edge $\\{v_{i},v_{j}\\}$ in
$G$ (resp. in $\bar{G}$) from $v_{i}$ to $v_{j}$ if and only if $i<j$. Then it
is straightforward to check that $F$ (resp. $\bar{F}$) is transitive and that
this construction is the inverse of the one in the proof of [Gol80, Theorem
7.1].

Finally, it is known [Gol80, Corollary 5.13] that a modular-prime
comparability graph has exactly two transitive orientations, one being the
inverse of the other.

###### Proof of Proposition 4.6.

Let $G$ be a modular-prime permutation graph. Then $\bar{G}$ is also modular-
prime. By [Gol80, Corollary 5.13], both $G$ and $\bar{G}$ have exactly two
transitive orientations. Since realizers of $G$ are built from pairs
$(F,\bar{F})$ of transitive orientations of $G$ and $\bar{G}$, the graph $G$
has at most 4 realizers. ∎

######  Remark 4.7.

We note that a modular-prime permutation graph may have less than 4 realizers
since different pairs $(F,\bar{F})$ may yield the same realizer $\pi$ of $G$.
This happens in fact when some/all realizers $\pi$ of $G$ has/have some
dihedral symmetry.

###  4.3. Limit of a uniform permutation graph

In this section, we prove Theorem 2.1, which states that the sequence of
uniform random permutation graphs $(\bm{G}_{n})_{n}$ converges almost surely
to $W^{(\mathrm{perm})}$ in the space of graphons.

###### Proof of Theorem 2.1.

We denote by $\mathcal{G}^{\text{perm}}_{n}$ the set of permutation graphs
with $n$ vertices. Let $\varepsilon>0$. We have

$\mathbb{P}\big{[}\delta_{\Box}(\bm{G}_{n},W^{(\mathrm{perm})})\geq\varepsilon\big{]}=\frac{\\#\left\\{G\in\mathcal{G}^{\text{perm}}_{n}:\delta_{\Box}(G,W^{(\mathrm{perm})})\geq\varepsilon\right\\}}{\\#\,\mathcal{G}^{\text{perm}}_{n}}.$

By definition, a permutation graph $G$ with $n$ vertices is equal to
$G_{\sigma}$ for at least one permutation $\sigma$. Hence, the numerator can
be bounded by

$\\#\left\\{G\in\mathcal{G}^{\text{perm}}_{n}:\delta_{\Box}(G,W^{(\mathrm{perm})})\geq\varepsilon\right\\}\leq\\#\left\\{\sigma\in
S_{n}:\delta_{\Box}(G_{\sigma},W^{(\mathrm{perm})})\geq\varepsilon\right\\},$

where $S_{n}$ denotes, as usual, the set of permutations of size $n$. On the
other hand using that modular-prime permutation graphs $G$ write as
$G_{\sigma}$ for at most $4$ permutations, all simple (Proposition 4.6), we
have

$\\#\,\mathcal{G}^{\text{perm}}_{n}\geq\\#\big{\\{}G\in\mathcal{G}^{\text{perm}}_{n}:G\text{
modular-prime}\\}\big{\\}}\geq\frac{1}{4}\,\\#\left\\{\sigma\in
S_{n}:\sigma\text{ simple }\right\\}.$

From [AAK03], we know that, as $n\to\infty$, the number of simple permutations
is asymptotically $e^{-2}\,n!$. Thus, for $n$ large enough, using $4e^{2}<30$,
we get $\\#\,\mathcal{G}^{\text{perm}}_{n}\geq\frac{n!}{30}$. Bringing
everything together we have, for $n$ large enough

$\mathbb{P}\big{[}\delta_{\Box}(\bm{G}_{n},W^{(\mathrm{perm})})\geq\varepsilon\big{]}\leq\frac{30}{n!}\,\\#\big{\\{}\sigma\in
S_{n}:\delta_{\Box}(G_{\sigma},W^{(\mathrm{perm})})\geq\varepsilon\big{\\}}\\\
=30\,\mathbb{P}\big{[}\delta_{\Box}(G_{\sigma_{n}},W^{(\mathrm{perm})})\geq\varepsilon\big{]},$

where, in the last equation, $\sigma_{n}$ is a uniform random permutation of
size $n$. As in the proof of Proposition 4.2, we know that the upper bound in
the above equation is summable as $n$ tends to $+\infty$. Since this holds for
any $\varepsilon>0$, we have proved the theorem, again using the
Borel–Cantelli Lemma. ∎

###  4.4. Clique density in $W^{(\mathrm{perm})}$

######  Proposition 4.8.

Denote by $K_{k}$ the clique of size $k$. For every $k\geq 1$,

${\operatorname{Dens}}(K_{k},W^{(\mathrm{perm})})=\frac{1}{k!}.$

Consequently, for every $k\geq 1$,

$\frac{1}{\binom{n}{k}}\ \\#\left\\{\text{cliques of size $k$ in
}\bm{G}_{n}\right\\}\ \to\ \frac{1}{k!}\ \text{ a.s.}.$

###### Proof.

By definition, ${\operatorname{Dens}}(K_{k},W^{(\mathrm{perm})})$ is the
probability that $\operatorname{Sample}_{k}(W^{(\mathrm{perm})})$ is a clique
$K_{k}$. Recall from (4) p.4 that
$\operatorname{Sample}_{k}(W^{(\mathrm{perm})})$ is distributed as the
inversion graph $G_{\pi}$ of a uniform random permutation $\pi$ of size $k$.
Moreover, $G_{\pi}=K_{k}$ if and only if $\pi$ is the decreasing permutation
$d_{k}:=k\ (k\\!-\\!1)\cdots 1$. Summing up,

${\operatorname{Dens}}(K_{k},W^{(\mathrm{perm})})=\mathbb{P}\big{(}\operatorname{Sample}_{k}(W^{(\mathrm{perm})})=K_{k}\big{)}=\mathbb{P}(G_{\pi}=K_{k})=\mathbb{P}(\pi=d_{k})=\frac{1}{k!}.\qed$

##  5\. Circle graphs

The main goal of this section is to prove Theorem 2.2: a sequence of uniform
random circle graphs converges to the graphon $W^{(\mathrm{circle})}$ defined
below in Definition 5.1 and Proposition 5.2.

The strategy of the proof is similar to the one used in the previous section
for permutation graphs. We start by observing that the intersection graph of a
uniform random matching (which is a _non_ uniform circle graph) converges to
$W^{(\mathrm{circle})}$ (see Proposition 5.2). Then, in order to transfer this
result to uniform circle graphs, we will go through _split-prime_ circle
graphs (a notion reviewed in Section 5.2 below). Indeed, one can control the
number of realizers of a split-prime circle graph (see Corollary 5.13).

A noticeable difference with the previous section comes from the enumeration
of combinatorial objects corresponding to a prime graph. Indeed, in our proof
for permutation graphs, we used previously known results on the enumeration of
simple permutations (which correspond to modular-prime permutation graphs).
However, for circle graphs, we need to define (in Definition 5.3 below) the
analogous notion of _indecomposable_ matchings (which correspond to split-
prime circle graphs), and then to estimate the number of these indecomposable
matchings. This additional step of the proof is dealt with in Section 5.2.

###  5.1. Limit of the intersection graph of a uniform matching

We need to introduce some combinatorial objects and a bit of notation.

We define a matching of size $n$ as a fixed-point free involution on the set
$[2n]$. (They are sometimes called _perfect matchings_ or _chord diagrams_ in
the literature.) Denote by $\mathcal{C}$ the unit circle centered at the
origin, and set $\omega_{n}=e^{2\mathbf{i}\pi/(2n)}$. For $\mathfrak{m}$ a
matching of size $n$, the circular representation of $\mathfrak{m}$, denoted
${\sf Ci}(\mathfrak{m})$, is the chord configuration of $\mathcal{C}$ in which
we put the $n$ chords333Chords are intended as straight lines, but for better
readability we draw them curvy in pictures, being careful not to introduce
unnecessary intersections. of the form

$(\omega_{n})^{i}\leftrightarrow(\omega_{n})^{\mathfrak{m}(i)}.$

By abuse of notation, we often identify a matching and its circular
representation. The size of a matching is then its number of chords.

As explained in the introduction, a graph $G$ with $n$ vertices is a _circle
graph_ if $G$ is the (unlabeled) intersection graph of ${\sf
Ci}(\mathfrak{m})$ for a certain matching $\mathfrak{m}$ of size $n$. Then
$\mathfrak{m}$ is called a _realizer_ of $G$ and we write
$G=G_{\mathfrak{m}}$.

For any $n\geq 1$ let $\mathcal{M}_{n}$ be the set of matchings of size $n$.
It will be useful for later purposes to observe that

(5)
$m_{n}:=\\#\mathcal{M}_{n}=(2n-1)!!=\frac{(2n)!}{2^{n}\,n!}\stackrel{{\scriptstyle
n\to+\infty}}{{\sim}}\sqrt{2}(2n/e)^{n}.$

Let $M_{n}$ be a uniform element in $\mathcal{M}_{n}$. In this subsection we
compute the graphon limit of $G_{M_{n}}$. We first need the notion of crossing
of two pairs of reals. Let $x_{A},x_{B},y_{A},y_{B}$ be four reals in $[0,1]$,
identified to the points $e^{2\mathbf{i}\pi x_{A}}$, $e^{2\mathbf{i}\pi
x_{B}}$, $e^{2\mathbf{i}\pi y_{A}}$ and $e^{2\mathbf{i}\pi y_{B}}$ on the unit
circle. We say that $(x_{A},x_{B})$ and $(y_{A},y_{B})$ are _crossing_ if
$x_{A},x_{B},y_{A},y_{B}$ are pairwise distinct and if the chords
$e^{2\mathbf{i}\pi x_{A}}\leftrightarrow e^{2\mathbf{i}\pi x_{B}}$ and
$e^{2\mathbf{i}\pi y_{A}}\leftrightarrow e^{2\mathbf{i}\pi y_{B}}$ intersect
(_i.e._ $x$’s and $y$’s alternate in the circular order).

######  Definition 5.1.

Let

$\begin{array}[]{r c c c}\Psi:&[0,1]&\to&[0,1]^{2}\\\
&x&\mapsto&(\Psi_{A}(x),\Psi_{B}(x))\end{array}$

be any measurable function which is Lebesgue-preserving. The graphon
$W^{(\mathrm{circle})}_{\Psi}$ is defined by (the equivalence class of)

$W^{(\mathrm{circle})}_{\Psi}(x,y)=\mathbb{1}\left[(\Psi_{A}(x),\Psi_{B}(x))\text{
and }(\Psi_{A}(y),\Psi_{B}(y))\text{ are crossing}\right]\quad\text{ for all
}x,y\in[0,1].$

As for $W^{(\mathrm{perm})}$, we can avoid the use of a Lebesgue-preserving
function $\Psi$ by using a more general formalism for graphons, see Remark
4.3.

######  Proposition 5.2.

The equivalence class of $W^{(\mathrm{circle})}_{\Psi}$ is independent of the
choice of the Lebesgue-preserving function $\Psi$. Moreover, let us consider,
for each $n$, a uniform random matching $M_{n}$ of size $n$. Then its
intersection graph $G_{M_{n}}$ satisfies

$G_{M_{n}}\stackrel{{\scriptstyle\text{a.s.}}}{{\to}}W^{(\mathrm{circle})},$

where $W^{(\mathrm{circle})}:=W^{(\mathrm{circle})}_{\Psi}$ for an arbitrary
Lebesgue-preserving function $\Psi$.

###### Proof.

As in the proof of Proposition 4.2 we first identify the distribution of
$\mathrm{Sample}_{n}(W^{(\mathrm{circle})}_{\Psi})$ (for $n\geq 1$). This
random graph on vertex set $[n]$ is constructed by taking i.i.d. uniform
random variables $X_{1}$, …, $X_{n}$ in $[0,1]$ and by connecting vertices $i$
and $j$ if and only if the chords $(\Psi_{A}(X_{i}),\Psi_{B}(X_{i}))$ and
$(\Psi_{A}(X_{j}),\Psi_{B}(X_{j}))$ are crossing.

For all $i$ in $[n]$, let $(u_{2i-1},u_{2i})=\Psi(X_{i})$. Since $\Psi$ is
Lebesgue-preserving, the $2n$ numbers $u_{1},\dots,u_{2n}$ are i.i.d. uniform
in $[0,1]$. Let $\tau$ be the unique permutation on $[2n]$ such that

$u_{\tau(1)}<\dots<u_{\tau(2n)}.$

Then, $\mathrm{Sample}_{n}(W^{(\mathrm{circle})}_{\Psi})$ is the intersection
graph $G_{\mathfrak{m}}$ of the matching $\mathfrak{m}$ of size $n$ defined by

$\mathfrak{m}=(\tau^{-1}(1),\tau^{-1}(2))(\tau^{-1}(3),\tau^{-1}(4))\dots(\tau^{-1}(2n-1),\tau^{-1}(2n)).$

Moreover, the permutation $\tau$ is a uniform permutation of size $2n$ (and so
is $\tau^{-1}$). So, the matching $\mathfrak{m}$ is a uniform matching of size
$n$, implying

(6)
$\mathrm{Sample}_{n}(W^{(\mathrm{circle})}_{\Psi})=G_{\mathfrak{m}}\stackrel{{\scriptstyle\text{(d)}}}{{=}}G_{M_{n}}.$

We conclude as in the proof of Proposition 4.2: for every fixed
$\varepsilon>0$

(7)
$\mathbb{P}\big{[}\delta_{\Box}(G_{M_{n}},W^{(\mathrm{circle})}_{\Psi})\geq\varepsilon\big{]}=\mathbb{P}\big{[}\delta_{\Box}(\mathrm{Sample}_{n}(W^{(\mathrm{circle})}_{\Psi}),W^{(\mathrm{circle})}_{\Psi})\geq\varepsilon\big{]},$

which is summable by Lemma 3.3. The Borel–Cantelli Lemma yields
$G_{M_{n}}\stackrel{{\scriptstyle\text{a.s.}}}{{\to}}W^{(\mathrm{circle})}_{\Psi}$.
∎

###  5.2. (In)decomposability of matchings

####  5.2.1. Indecomposable matchings

We first define indecomposable matchings, which will be an analog of simple
permutations for matchings. They enjoy the nice property that split-prime
circle graphs (whose definition is reviewed below) are represented by
indecomposable matchings (see Proposition 5.5).

######  Definition 5.3.

Let $\mathfrak{m}$ be a matching of size $n$. We say that $\mathfrak{m}$ is
$k$-decomposable if there exists a partition of $[2n]$ into four (possibly
empty) parts $C_{1},C_{2},C_{3},C_{4}$ such that

  * •

each $C_{i}$ is a circular interval (_i.e._ an interval of
$\\{1,2,\dots,2n\\}\mod 2n$);

  * •

$C_{1}$ contains $1$, and the nonempty parts among $C_{2}$, $C_{3}$ and
$C_{4}$ are ordered according to their smallest element;

  * •

all chords have either both extremities in $C_{1}\cup C_{3}$ or both
extremities in $C_{2}\cup C_{4}$;

  * •

$C_{2}\cup C_{4}$ contains exactly $k$ chords.

A matching of size $n$ is decomposable if it is $k$-decomposable for some $k$
with $2\leq k\leq n-2$.
A matching is indecomposable if it is not decomposable.

Observe that a matching can be $k$-decomposable for several $k$. An example of
decomposable matching is given in Fig. 5 (left).

######  Remark 5.4.

  * •

If $\mathfrak{m}$ is decomposable then, as indicated above, $C_{i}$ may be
empty for some $i\in\\{2,3,4\\}$. But then, from the last item of Definition
5.3 and the bounds on $k$, for $j\equiv i+2\mod 4$, $C_{j}$ should contain at
least four points of the matchings (two chords).

  * •

We warn the reader that other notions of indecomposable matchings have
appeared in the literature see, e.g., [Jef15]. In the latter reference, two
notions of weakly and strongly indecomposable matchings are considered, both
being weaker than the one considered here.

Figure 5. Left: The circular representation of a $k$-decomposable matching for
$k=\\#\left\\{c,d,f,g\right\\}=4$. Right: the corresponding intersection graph
with the cut $\left\\{a,b,e\right\\}\uplus\left\\{c,d,f,g\right\\}$ induced by
$C_{1},\dots,C_{4}$. The corresponding cut-set
$\left\\{b,e\right\\}\times\left\\{c,d,g\right\\}$ is a complete bipartite
graph and the split is depicted with the dashed line.

We now introduce the necessary terminology to relate indecomposable matchings
to split-prime circle graphs.

Recall that a _cut_ of a graph is a partition of the vertices into two
nonempty subsets $V_{1}$ and $V_{2}$, called the sides of the cut. The subset
of edges that have one endpoint in each side of the cut is called a _cut-set_
, and a cut whose cut-set forms a (possibly empty) complete bipartite graph is
called a _split_. By extension, the two sets of vertices in the complete
bipartite graph defining a split will be refered to as cut vertex sets (this
shall not be confused with the notion of cut vertices, not relevant here). An
equivalent definition is to say that a cut $V_{1}$ and $V_{2}$ form a split if
and only if they contain subsets $V_{1}^{cut}$ and $V_{2}^{cut}$ (possibly
empty) such that:

  * •

there is no edge between $V_{1}\setminus V_{1}^{cut}$ and $V_{2}$, and
similarly no edge between $V_{2}\setminus V_{2}^{cut}$ and $V_{1}$;

  * •

any vertex in $V_{1}^{cut}$ is linked to any vertex in $V_{2}^{cut}$.

A split is trivial when one of its two sides has only one vertex in it. A
graph is said to be prime for the split decomposition, or _split-prime_ for
short, if it has no nontrivial splits ; otherwise it is _split-decomposable_.

######  Proposition 5.5.

Let $G$ be a circle graph and $\mathfrak{m}$ be a matching that represents
$G$. Then $G$ is split-prime if and only if $\mathfrak{m}$ is indecomposable.

###### Proof.

The proof is technical and postponed to Section A.1. ∎

####  5.2.2. Enumeration of decomposed matchings

Our goal is to prove that a positive proportion of matchings are
indecomposable (in Proposition 5.11 below). To this end we define a
$k$-decomposed matching as a pair formed by a $k$-decomposable matching
$\mathfrak{m}$ and a decomposition $(C_{1},C_{2},C_{3},C_{4})$ of
$\mathfrak{m}$ as in Definition 5.3. We first study the number of
$k$-decomposed matchings.

######  Lemma 5.6.

For any $2\leq k\leq n-2$, let $d_{n}^{k}$ be the number of $k$-decomposed
matchings of size $n$. Then

$d_{n}^{k}=(n-k)\,m_{k+1}\,m_{n-k+1},$

where $m_{n}$ is the number of matchings of size $n$.

###### Proof.

Let $\mathcal{M}^{\bullet}_{k}$ be the set of matchings of size $k$ with a
marked chord such that the marked chord is not the one containing $1$. Then
$\\#\mathcal{M}^{\bullet}_{k}=(k-1)\,m_{k}$. We prove the lemma by giving a
one-to-one correspondence $\varphi$ between the set $\mathcal{D}_{n}^{k}$ of
$k$-decomposed matchings of size $n$ and
$\mathcal{M}^{\bullet}_{n-k+1}\times\mathcal{M}_{k+1}$. This construction is
illustrated on Fig. 6.

Figure 6. Notation of the proof of Lemma 5.6. Left: A $k$-decomposed matching.
Right: The corresponding matchings $\mathfrak{m}$ of size $n-k+1$ (marked at
the dashed chord) and $\mathfrak{m}^{\prime}$ of size $k+1$.

Let $(C_{1},C_{2},C_{3},C_{4})\in\mathcal{D}_{n}^{k}$. To obtain a matching
$\mathfrak{m}$ in $\mathcal{M}^{\bullet}_{n-k+1}$, we glue $C_{1}$ and $C_{3}$
together and add a marked chord separating the two parts (to remember where it
has been cut; in Fig. 6 this chord is depicted by a dashed line). Then we
relabel the points on the circle so that the $1$ of $C_{1}$ remains $1$ in
$\mathfrak{m}$, and the other points are labeled by increasing order starting
from $1$. Similarily, to obtain a matching $\mathfrak{m}^{\prime}$ in
$\mathcal{M}_{k+1}$, we glue $C_{2}$ and $C_{4}$ together and add a chord
separating the two parts. To remember the added chord, we label by $1$ the
point of the added chord in $\mathfrak{m}^{\prime}$ that is next to the
smallest number of $C_{2}$, and the remaining points are labeled by increasing
order starting from $1$. If $C_{2}$ is empty then extremities of the added
chord are labeled $1,2$, and the remaining points are also labeled in
increasing order. We set
$\varphi(C_{1},C_{2},C_{3},C_{4})=(\mathfrak{m},\mathfrak{m}^{\prime})$.

To see that $\varphi$ is a bijection, we construct its inverse. Let
$\mathfrak{m},\mathfrak{m}^{\prime}$ be a pair of matchings in
$\mathcal{M}^{\bullet}_{n-k+1}\times\mathcal{M}_{k+1}$. We cut $\mathfrak{m}$
along the marked chord (hence deleting this chord). This gives two circular
arcs: we call $C_{1}$ the one containing $1$ and $C_{3}$ the other one. Then
we cut $\mathfrak{m}^{\prime}$ along the chord containing $1$ (this chord is
also deleted). This gives two circular arcs. We call $C_{2}$ the one
containing the $2$ of $\mathfrak{m}^{\prime}$ (unless $\mathfrak{m}^{\prime}$
contains a chord from $1$ to $2$, in which case $C_{2}$ is empty). We call
$C_{4}$ the other one. We build a $k$-decomposed matching of size $n$ by
gluing these four circular arcs, in increasing order of their indices, and
preserving the orientations of the circular arcs. Finally we label the points
in increasing order so that the $1$ of the new matching is the $1$ of
$\mathfrak{m}$. It should be clear that applying $\varphi$ to the four
circular arcs defined above gives $(\mathfrak{m},\mathfrak{m}^{\prime})$. ∎

In the sequel we will estimate $d_{n}^{k}$ for every $2\leq k\leq n-2$. As we
will see, the case $k=2$ is quite different from $k>2$.

####  5.2.3. Probability of $k$-decomposability for $k>2$

Recall that $M_{n}$ is a random matching taken uniformly at random among the
$m_{n}$ matchings of size $n$.

######  Lemma 5.7.

As $n$ tends to $+\infty$, we have

(8)
$\sum_{k=3}^{n-2}\frac{d_{n}^{k}}{m_{n}}=\mathcal{O}\left(\frac{1}{n}\right).$

Consequently,

$\mathbb{P}(M_{n}\text{ is $k$-decomposable for some }k>2)\to 0.$

###### Proof.

Recall that for all $n$, we have $m_{n}=(2n-1)m_{n-1}$, and that, from Lemma
5.6, we have $d_{n}^{k}=(n-k)\,m_{k+1}\,m_{n-k+1}$. We set
$e_{n}^{k}=m_{k+1}\,m_{n-k+1}$. Trivially,

$\frac{e^{k+1}_{n}}{e^{k}_{n}}=\frac{m_{k+2}\,m_{n-k}}{m_{k+1}\,m_{n-k+1}}=\frac{2k+3}{2n-2k+1}.$

Hence, for fixed $n$, the map $k\mapsto{e^{k}_{n}}$ is decreasing for
$k\leq\frac{n-1}{2}$, and increasing for $k\geq\frac{n-1}{2}$. In particular,
using $d_{n}^{k}\leq ne_{n}^{k}$ after isolating some terms in the sum, we
have the bound

(9)
$\sum_{k=3}^{n-2}\frac{d_{n}^{k}}{m_{n}}\leq\frac{d_{n}^{3}+d_{n}^{n-3}+d_{n}^{n-2}}{m_{n}}+n\,\sum_{k=4}^{n-4}\frac{e_{n}^{k}}{m_{n}}\leq\frac{d_{n}^{3}+d_{n}^{n-3}+d_{n}^{n-2}}{m_{n}}+n^{2}\frac{\max(e_{n}^{4},e_{n}^{n-4})}{m_{n}}.$

Trivially, for fixed $k$,

$\frac{e_{n}^{k}}{m_{n}}=\frac{e_{n}^{n-k}}{m_{n}}=\frac{m_{k+1}}{(2n-1)\dots(2n-2k+3)}=O(n^{-k+1}),$

implying

$\frac{d_{n}^{k}}{m_{n}}=(n-k)\,\frac{e_{n}^{k}}{m_{n}}=O(n^{-k+2})\text{ and
}\frac{d_{n}^{n-k}}{m_{n}}=k\frac{e_{n}^{k}}{m_{n}}=O(n^{-k+1}).$

Using these bounds in (9) ends the proof of (8). The probabilistic consequence
is immediate, since the number of $k$-decomposable matchings is at most that
of $k$-decomposed matchings. ∎

####  5.2.4. Probability of $2$-decomposability

######  Lemma 5.8.

As above, let $M_{n}$ be a uniform random matching of size $n$. We have

$\mathbb{P}(M_{n}\text{ is not $2$-decomposable})\stackrel{{\scriptstyle
n\to\infty}}{{\to}}e^{-3}.$

The remainder of Section 5.2.4 is devoted to the proof of Lemma 5.8. To this
end, we introduce the following quantities. For a matching $\mathfrak{m}$, let
$x(\mathfrak{m})=\sum_{i=1}^{2n}\bm{1}[\mathfrak{m}(i)\equiv i+1]$ be the
number of chords between adjacent points, where $\equiv$ stands for equality
mod $2n$. Similarly we set
$y(\mathfrak{m})=\sum_{j=1}^{2n}\bm{1}[\mathfrak{m}(j)\equiv j+2]$. Finally
let

$z(\mathfrak{m})=\sum_{\begin{subarray}{c}1\leq k<\ell\leq 2n\\\
\ell-k\not\equiv\pm
1\end{subarray}}\bm{1}\big{[}\left\\{\mathfrak{m}(k),\mathfrak{m}(k+1)\right\\}\equiv\left\\{\ell,\ell+1\right\\}\big{]};$

_i.e._ $z(\mathfrak{m})$ counts pairs of consecutive points matched to another
pair of consecutive points. The definitions of $x(\mathfrak{m})$,
$y(\mathfrak{m})$ and $z(\mathfrak{m})$ are illustrated on Fig. 7.

Figure 7. Sub-configurations of a matching $\mathfrak{m}$ counted by
$x(\mathfrak{m})$, $y(\mathfrak{m})$, $z(\mathfrak{m})$.

######  Lemma 5.9.

For a matching $\mathfrak{m}$, whose size we denote $n$, we have
$x(\mathfrak{m})=y(\mathfrak{m})=z(\mathfrak{m})=0$ if and only if
$\mathfrak{m}$ is neither $2$-decomposable nor $(n-2)$-decomposable.

###### Proof.

We shall prove that if one of $x(\mathfrak{m})$, $y(\mathfrak{m})$ or
$z(\mathfrak{m})$ is positive, then $\mathfrak{m}$ is either $2$-decomposable
or $(n-2)$-decomposable. The proof of the converse statement is easy and left
to the reader.

  * •

Assume first that $z(\mathfrak{m})>0$, _i.e._ there exists $k<\ell$ such that

$\left\\{\mathfrak{m}(k),\mathfrak{m}(k+1)\right\\}\equiv\left\\{\ell,\ell+1\right\\}.$

Then the set $[2n]$ can be split into four (possibly empty) circular intervals

$\\{k,k+1\\},\\{k+2,\dots\ell-1\\},\\{\ell,\ell+1\\},\\{\ell+2,\dots,k-1\\},$

such that all chords have both extremities in the same interval or in
diagonally facing intervals. Note that $\\{k,k+1\\}\cup\\{\ell,\ell+1\\}$
contains exactly two chords. The labeling of these circular intervals as
$C_{1}$, $C_{2}$, $C_{3}$ and $C_{4}$ depends on whether $k=1$ or $\ell=n$, or
none of those, so that either $C_{1}\cup C_{3}$ or $C_{2}\cup C_{4}$ contains
2 chords. Thus $z(\mathfrak{m})>0$ implies that the matching $\mathfrak{m}$ is
either $2$ or $(n-2)$-decomposable.

  * •

Assume now that $y(\mathfrak{m})>0$, _i.e._ there exists $j$ such that
$\mathfrak{m}(j)=j+2$. Letting $k=\mathfrak{m}(j+1)$, the following partition
of $[2n]$ into four (possibly empty) circular intervals

$\\{j,j+1,j+2\\},\\{j+3,\dots k-1\\},\\{k\\},\\{k+1,\dots,j-1\\}$

shows that $\mathfrak{m}$ is either $2$ or $(n-2)$-decomposable.

  * •

The same conclusion holds true if $x(\mathfrak{m})>0$; the proof is similar,
except that we set $k=\mathfrak{m}(i+2)$.∎

Recalling that $M_{n}$ denotes a uniform random matching of size $n$, let us
define $X_{n}=x(M_{n})$, $Y_{n}=y(M_{n})$ and $Z_{n}=z(M_{n})$.

######  Lemma 5.10.

The triple $(X_{n},Y_{n},Z_{n})$ converges in distribution towards a triple of
independent Poisson random variables with mean 1.

###### Proof.

The proof is technical and postponed to Section A.2. ∎

###### Proof of Lemma 5.8.

Using Lemma 5.7 for $k=n-2$, we have

$\mathbb{P}(M_{n}\text{ is not $2$-decomposable})=\mathbb{P}(M_{n}\text{ is
neither $2$ nor $n-2$-decomposable})+\mathrm{o}(1).$

But Lemma 5.9 asserts that the latter event is the same as
“$X_{n}=Y_{n}=Z_{n}=0$”. Therefore

$\mathbb{P}(M_{n}\text{ is not
$2$-decomposable})=\mathbb{P}(X_{n}=Y_{n}=Z_{n}=0)+\mathrm{o}(1),$

and the latter tends to $e^{-3}$ by Lemma 5.10. ∎

####  5.2.5. Probability of indecomposability

Bringing together Lemmas 5.7 and 5.8, we can give a lower bound on the
probability for a uniform matching to be indecomposable.

######  Proposition 5.11.

Let $M_{n}$ be a uniform matching of size $n$. Then for $n$ large enough,

$\mathbb{P}(M_{n}\text{ is indecomposable})>e^{-4}.$

###### Proof.

We write

$\mathbb{P}(M_{n}\text{ is decomposable})\leq\mathbb{P}(M_{n}\text{ is
$2$-decomposable})\\\ +\mathbb{P}(M_{n}\text{ is $k$-decomposable for some
}k>2).$

From Lemmas 5.7 and 5.8, the latter converges to $1-e^{-3}$ as $n$ tends to
$+\infty$, implying the proposition. ∎

###  5.3. On the number of matchings that represent a given circle graph

Let $\mathfrak{m}$ be a matching. Then the shift of $\mathfrak{m}$ is the
matching obtained by replacing each chord $(i,j)$ of $\mathfrak{m}$ by the
chord $(i+1,j+1)$ (where $2n+1$ is identified with $1$). This operation
corresponds to a rotation of the circular representation of $\mathfrak{m}$.
Moreover, the reversal of $\mathfrak{m}$ is the matching obtained by replacing
each chord $(i,j)$ of $\mathfrak{m}$ by the chord $(2n+1-i,2n+1-j)$. This
operation corresponds to a symmetry of the circular representation of
$\mathfrak{m}$ (specifically, to the reflexion with respect to the diameter
passing between points labeled $1$ and $2n$ on one side, and between points
labeled $n$ and $n+1$ on the other side).

Let $G$ be a circle graph and $\mathfrak{m}$ be a matching that represents
$G$. Then every matching obtained from $\mathfrak{m}$ by a sequence of shifts
and reversals also represents $G$. It has been proved that when $G$ is split-
prime, this is the unique source for the lack of uniqueness of the
representative:

######  Proposition 5.12 (Corollary in Section 8 of [GSH89]).

Let $G$ be a split-prime circle graph with at least five vertices. Then there
is a unique (up to shifts and reversals) matching $\mathfrak{m}$ such that
$G=G_{\mathfrak{m}}$.

######  Corollary 5.13.

Let $G$ be a split-prime circle graph with $n\geq 5$ vertices. The number of
matchings $\mathfrak{m}$ such that $G=G_{\mathfrak{m}}$ is between $1$ and
$4n$.

######  Proposition 5.14.

The proportion of matchings of size $n$ whose associated circle graphs have
strictly less than $4n$ representatives is $o(n^{-n/3})$.

As we will see in the proof, this bound is far from optimal but sufficient for
our purposes.

###### Proof.

The circle graph associated to a matching of the numbers $\\{1,\dots,2n\\}$
may have less than $4n$ representatives only if the matching is fixed by some
nontrivial symmetry $s$ of a regular $2n$-gon.

Let us fix some symmetry $s$ of a regular $2n$-gon. We consider the set
$\mathcal{M}^{s}_{n}$ of matchings fixed by $s$, and denote by $m^{s}_{n}$ its
cardinality. The cases where $s$ is a rotation of order $2$ and where $s$ is a
reflection lead to the same enumeration sequence – too see this, simply switch
$2n-i$ and $n+i$ for $i\leq n/2$; this turns a rotation-invariant matching
into a reflection-invariant one. Hence we assume that $s$ is a rotation.
Denote its order by $d$. We have $2n=dk$ for some integer $k$. An element $M$
in $\mathcal{M}^{s}_{n}$ is uniquely encoded by a partition $\pi$ of the
numbers $\\{1,\dots,k\\}$ into singletons and pairs with the following
constraints and interpretation.

  * •

Singletons are allowed only if $d$ is even (_i.e._ when $n$ is a multiple of
$k$); a singleton $\\{i\\}$ represent the chord $\\{i,i+n\\}$ and its
rotations ($\\{i+k,i+k+n\\}$, …, $\\{i+n-k,i+2n-k\\}$). Having $d$ even and
containing these chords is the only possibility for a rotation-invariant
matching $M$ to contain a chord joining $i$ to some integer in the same class
mod. $k$; hence singletons in $\pi$ encode all chords of $M$ joining integers
within the same modulo class.

  * •

Pairs $\\{i,j\\}$ are decorated with a number $h$ in $\\{0,\dots,d-1\\}$ and
represent the chord $\\{i,j+h\,k\\}$ and its rotations
($\\{i+k,j+(h+1)\,k\\}$, …, $\\{i+(d-1)k,j+(h+d-1)\,k\\}$, working mod. $2n$).
These pairs in $\pi$ encode all chords of $M$ joining integers in different
classes modulo $k$.

Using the formalism of labeled combinatorial classes [FS09, Chapter II], this
yields the following expression for an exponential generating series of
$\mathcal{M}^{s}_{n}$. For fixed $d\geq 2$,

$\sum_{k\geq 1}m^{s}_{dk/2}\frac{z^{k}}{k!}=\exp\big{(}z\delta_{d\text{
even}}+d\tfrac{z^{2}}{2}\big{)}.$

With Cauchy formula, we get

$m^{s}_{dk/2}=\frac{k!}{2\pi\,i}\oint\frac{\exp\big{(}z\delta_{d\text{
even}}+d\tfrac{z^{2}}{2}\big{)}}{z^{k+1}}dz, $

where we integrate over any counterclockwise contour around $0$. We choose
this contour to be the circle $\\{z:|z|=\sqrt{k/d}\\}$. Recalling that
$k^{k}/e^{k-1}\leq k!\leq k^{k+1}/e^{k-1}$ for all $k\geq 1$, we get the
following upper bound:

$m_{n}^{s}=m^{s}_{dk/2}\leq
k!\sqrt{k/d}\,\frac{\exp(\sqrt{k/d}+\tfrac{k}{2})}{\sqrt{k/d}^{k+1}}\\\ \leq
k\,(kd)^{k/2}\exp\big{(}\sqrt{k/d}-k/2+1\big{)}.$

For $d,k\geq 2$, we have $\exp\big{(}\sqrt{k/d}-k/2)\leq 1$. Recalling that
$2n=dk$, we have in particular $m_{n}^{s}\leq e(2n)^{\frac{n}{d}+1}$. For
unconstrained matchings, we have

$m_{n}=\frac{(2n)!}{2^{n}n!}\geq\frac{(2n)^{2n}\,e^{n-1}}{e^{2n-1}\,2^{n}\,n^{n+1}}=\frac{2^{n}\,n^{n-1}}{e^{n}}.$

Comparing both bounds yields that for $n$ large enough, for any symmetry $s$
of order $d\geq 2$, we have $\frac{m_{n}^{s}}{m_{n}}=o(n^{-n/3-1})$, uniformly
on $s$. Since there are $4n$ possible symmetries $s$, this proves the
proposition. ∎

###  5.4. Proof of Theorem 2.2: limit of a uniform circle graph

In this section, we prove Theorem 2.2 which states that the sequence of
uniform random circle graphs $(\bm{G}_{n})_{n}$ converges to
$W^{(\mathrm{circle})}$ almost surely in the space of graphons.

###### Proof.

We denote by $\mathcal{G}^{\text{circle}}_{n}$ the set of circle graphs with
$n$ vertices. Let $\varepsilon>0$. We have

(10)
$\mathbb{P}\big{[}\delta_{\Box}(\bm{G}_{n},W^{(\mathrm{circle})})\geq\varepsilon\big{]}=\frac{\\#\left\\{G\in\mathcal{G}^{\text{circle}}_{n}:\delta_{\Box}(G,W^{(\mathrm{circle})})\geq\varepsilon\right\\}}{\\#\
\mathcal{G}^{\text{circle}}_{n}}\ .$

By definition, a circle graph $G$ with $n$ vertices is equal to
$G_{\mathfrak{m}}$ for at least one matching $\mathfrak{m}$. We denote by
$\mathcal{G}^{<4n}_{n}$ (resp. $\mathcal{G}^{\geq 4n}_{n}$) the set of circle
graphs with $n$ vertices that have less than $4n$ representatives (resp. at
least $4n$ representatives). Moreover, we denote by $\mathcal{M}^{<4n}_{n}$
(resp. $\mathcal{M}^{\geq 4n}_{n}$) the set of matchings $\mathfrak{m}$ such
that $G_{\mathfrak{m}}\in\mathcal{G}^{<4n}_{n}$ (resp.
$G_{\mathfrak{m}}\in\mathcal{G}^{\geq 4n}_{n}$). Then,

(11)
$\displaystyle\begin{split}&\\#\left\\{G\in\mathcal{G}^{\text{circle}}_{n}:\delta_{\Box}(G,W^{(\mathrm{circle})})\geq\varepsilon\right\\}\\\
&=\\#\left\\{G\in\mathcal{G}^{\geq
4n}_{n}:\delta_{\Box}(G,W^{(\mathrm{circle})})\geq\varepsilon\right\\}+\\#\left\\{G\in\mathcal{G}^{<4n}_{n}:\delta_{\Box}(G,W^{(\mathrm{circle})})\geq\varepsilon\right\\}\\\
&\leq\frac{1}{4n}\\#\left\\{\mathfrak{m}\in\mathcal{M}^{\geq
4n}_{n}:\delta_{\Box}(G_{\mathfrak{m}},W^{(\mathrm{circle})})\geq\varepsilon\right\\}+\\#\left\\{\mathfrak{m}\in\mathcal{M}^{<4n}_{n}:\delta_{\Box}(G_{\mathfrak{m}},W^{(\mathrm{circle})})\geq\varepsilon\right\\}\\\
&\leq\frac{1}{4n}\\#\left\\{\mathfrak{m}\in\mathcal{M}_{n}:\delta_{\Box}(G_{\mathfrak{m}},W^{(\mathrm{circle})})\geq\varepsilon\right\\}+\\#\left\\{\mathfrak{m}\in\mathcal{M}^{<4n}_{n}\right\\}.\end{split}$

On the other hand, using that split-prime circle graphs $G$ correspond to
indecomposable matchings (Proposition 5.5) and that each split-prime graph is
represented by at most $4n$ indecomposable matchings (Corollary 5.13), we have

$\\#\,\mathcal{G}^{\text{circle}}_{n}\geq\\#\left\\{G\in\mathcal{G}^{\text{circle}}_{n}:G\text{
split-
prime}\right\\}\geq\frac{1}{4n}\,\\#\left\\{\mathfrak{m}\in\mathcal{M}_{n}:\mathfrak{m}\text{
indecomposable}\right\\}$

From Proposition 5.11, we know that, for $n$ large enough, the number of
indecomposable matchings of size $n$ is asymptotically greater than
$e^{-4}m_{n}$ where $m_{n}$ is the number of matchings of size $n$. Thus, for
$n$ large enough,

(12) $\\#\,\mathcal{G}^{\text{circle}}_{n}\geq\frac{e^{-4}m_{n}}{4n}.$

Bringing (10), (11) and (12) together, we have

$\displaystyle\mathbb{P}\big{(}\delta_{\Box}(\bm{G}_{n},W^{(\mathrm{circle})})\geq\varepsilon\big{)}$
$\displaystyle\leq\frac{e^{4}}{m_{n}}\,\\#\left\\{\mathfrak{m}\in\mathcal{M}_{n}:\delta_{\Box}(G_{\mathfrak{m}},W^{(\mathrm{circle})})\geq\varepsilon\right\\}+4e^{4}\,n\,\frac{\\#\left\\{\mathfrak{m}\in\mathcal{M}^{<4n}_{n}\right\\}}{m_{n}}$
$\displaystyle\leq
e^{4}\mathbb{P}\big{(}\delta_{\Box}(G_{M_{n}},W^{(\mathrm{circle})})\geq\varepsilon\big{)}+4e^{4}\,n\,\frac{\\#\left\\{\mathfrak{m}\in\mathcal{M}^{<4n}_{n}\right\\}}{m_{n}}.$

We saw in the proof of Proposition 5.2 (see in particular (7) and Lemma 3.3)
that the first term in the right-hand side is summable. Proposition 5.14 tells
that the second term is a $\mathrm{o}(n\times n^{-n/3})$. Using the
Borel–Cantelli Lemma (as in the proof of Lemma 3.3), this concludes the proof
of the theorem. ∎

###  5.5. Clique density in $W^{(\mathrm{circle})}$

######  Proposition 5.15.

Denote by $K_{k}$ the clique of size $k$. For every $k\geq 1$

${\operatorname{Dens}}(K_{k},W^{(\mathrm{circle})})=\frac{1}{m_{k}}=\frac{2^{k}k!}{(2k)!}.$

In particular the density of edges
${\operatorname{Dens}}(K_{2},W^{(\mathrm{circle})})$ equals $1/3$ and the
density of triangles ${\operatorname{Dens}}(K_{3},W^{(\mathrm{circle})})$
equals $1/15$.

###### Proof.

By definition,
${\operatorname{Dens}}(K_{k},W^{(\mathrm{circle})})=\mathbb{P}[\operatorname{Sample}_{k}(W^{(\mathrm{circle})})=K_{k}]$.
From Eq. 6, we know that $\operatorname{Sample}_{k}(W^{(\mathrm{circle})})$ is
distributed as $G_{M_{k}}$, where $M_{k}$ is a uniform random matching of size
$k$. It is easy to see that the only matching ${\mathfrak{m}}$ such that
$G_{\mathfrak{m}}=K_{k}$ is the matching
$\mathfrak{m}_{0}=\\{\\{1,k+1\\},\\{2,k+2\\},\dots,\\{k,2k\\}\\}$. Hence,

${\operatorname{Dens}}(K_{k},W^{(\mathrm{circle})})=\mathbb{P}[\operatorname{Sample}_{k}(W^{(\mathrm{circle})})=K_{k}]=\mathbb{P}[M_{k}=\mathfrak{m}_{0}]=\frac{1}{m_{k}}.$

We conclude using Equation (5). ∎

##  6\. Unit interval graphs

The main goal of this section is to prove Theorem 2.3: a sequence of uniform
random unit interval graphs with a renormalized distance function converges in
the sense of the Gromov–Prokhorov topology towards the unit interval $[0,1]$,
endowed with a random metric defined through a Brownian excursion.

An important difference with the previous sections is that the convergence is
in the Gromov–Prokhorov topology and not in the sense of graphons.
Nevertheless, we similarly focus a large part of our study on indecomposable
combinatorial objects (irreducible Dyck paths here), which represent by an
essentially unique way _connected_ unit interval graphs (playing the role of
modular-prime permutation graphs or split-prime circle graphs). In this
section, and unlike in the previous ones, our intermediate statement consists
in establishing a limit result for the graph associated to a uniform
_indecomposable_ combinatorial object, while we proved such results for
uniform combinatorial objects in previous sections.

We start by observing in Section 6.1 how connected unit interval graphs can be
encoded by irreducible Dyck paths. Then in Section 6.2 we prove that the unit
interval graph obtained from a uniform random irreducible Dyck path converges
in the sense of the Gromov–Prokhorov topology towards the unit interval
$[0,1]$, endowed with a random metric defined through a Brownian excursion
(the proof of a technical lemma is postponed to Section 6.3). In Section 6.4
we transfer this result to uniform circle graphs. Finally, an asymptotic
result for the number of cliques of size $k$ ($k$ fixed) in a uniform random
unit interval graph is given in Section 6.5.

###  6.1. Combinatorial encoding of unit interval graphs

An (unlabeled) graph $G$ is a unit interval graph if there exists a collection
$\mathcal{I}=(I_{1},...,I_{n})$ of intervals of $\mathbb{R}$ with unit length
such that a labeled version $G^{\ell}$ of $G$ is the intersection graph
associated with ${I_{1},...,I_{n}}$. The collection $\mathcal{I}$ of intervals
is then called an interval representation of $G$.

As we shall see, unit interval graphs are naturally encoded by Dyck words (or
Dyck paths). We recall that a word $w$ in $\\{U,D\\}$ is a Dyck word if it
contains as many $U$’s as $D$’s and if all its prefixes have at least as many
U’s as D’s. A Dyck word is irreducible if all its proper prefixes have
strictly more $U$’s than $D$’s. Besides, the mirror of a Dyck word $w$ is the
word $\overline{w}$ obtained by reading $w$ from right to left, changing $U$
into $D$ and $D$ into $U$. Finally, a Dyck word $w$ is called palindromic if
$w=\overline{w}$. Dyck words can be represented as lattice paths, called Dyck
paths, by interpreting $U$’s as up steps $(1,1)$ and $D$’s as down steps
$(1,-1)$, and we will use both points of view interchangeably.

Let us now explain the encoding of unit interval graphs by Dyck paths. Let $G$
be a unit interval graph, and $\mathcal{I}=(I_{1},...,I_{n})$ be an interval
representation of $G$. We write $I_{j}=[a_{j},b_{j}]$, with $b_{j}=a_{j}+1$.
Assume without loss of generality that $a_{1}<\dots<a_{n}$ (and hence
$b_{1}<\dots<b_{n}$). Let us consider the natural order on the set
$\\{a_{1},\dots,a_{n},b_{1},\dots,b_{n}\\}$, _i.e._ we consider
$c_{1}<\dots<c_{2n}$ such that

$\\{c_{1}\dots,c_{2n}\\}=\\{a_{1},\dots,a_{n},b_{1},\dots,b_{n}\\}.$

We then define a Dyck path $w=(w_{1},\dots,w_{2n})$ by

(13) $w_{i}=\begin{cases}U&\text{if }c_{i}=a_{k}\text{ for some $k$;}\\\
D&\text{if }c_{i}=b_{k}\text{ for some $k$.}\end{cases}$

This construction is illustrated in Fig. 8. Note that in this construction
$a_{i}$, resp. $b_{i}$, corresponds to the $i$-th up step, resp. $i$-th down
step in $w$.

Figure 8. Top: A collection $\mathcal{I}$ of unit intervals and the associated
interval graph $G_{\mathcal{I}}$. Bottom: the order on the collection of
starting and ending points of the intervals in $\mathcal{I}$ and the
associated the Dyck path.

Given a Dyck path $w$, we can always find real numbers $(a_{j})_{1\leq j\leq
n}$ and $(b_{j})_{1\leq j\leq n}$ with $b_{j}=a_{j}+1$ such that (13) holds
(with $c_{i}$ the $i$-th element of the set
$\\{a_{1},\dots,a_{n},b_{1},\dots,b_{n}\\}$ in the natural order). Moreover,
all such sequences $(a_{j})_{1\leq j\leq n}$ and $(b_{j})_{1\leq j\leq n}$
yield the same unit interval graph, which we denote $G_{w}$. However, several
Dyck paths may correspond to a given unit interval graph, depending on the
interval representation of $G$. In particular, it always holds that
$G_{w}=G_{\overline{w}}$.

Another default of uniqueness appears when considering not connected graphs.
Let $G=G_{1}\uplus G_{2}$ be a disjoint union of two unit interval graphs, and
let $w^{(1)}$ and $w^{(2)}$ be Dyck paths encoding $G_{1}$ and $G_{2}$. Then
both concatenations $w^{(1)}\cdot w^{(2)}$ and $w^{(2)}\cdot w^{(1)}$ are
representatives of $G$. Furthermore, it is easy to see that $G_{w}$ is
connected if and only if $w$ is irreducible.

It turns out, see [SYKU10, Lemma 1]444Recall that unit interval graphs and
proper interval graphs are the same, see [BW99]., that mirror symmetry and
disconnectedness are the only objections to the uniqueness of representatives.

######  Proposition 6.1.

If $G$ is a connected unit interval graph. Then it can be encoded by exactly
one or two (necessarily irreducible) Dyck paths. In the second case, the two
representatives $w$ and $w^{\prime}$ are mirror of each other.

###  6.2. Limit of random unit interval graphs: the uniform irreducible Dyck
path model

In this section, we determine the limit in the Gromov–Prokhorov topology of
the intersection graph of a uniform irreducible Dyck path.

We emphasize that a uniform random irreducible Dyck path of length $2n$ is
obtained from a uniform random Dyck path of length $2n-2$ by adding an up step
at the beginning and a down step at the end. Therefore classical asymptotic
results for uniform random Dyck paths – such as the convergence after
normalization to a Brownian excursion (recalled below) – also hold for uniform
random irreducible Dyck paths.

Let ${\bm{w}}$ be a uniform random irreducible Dyck path of length $2n$ and
$G_{\bm{w}}$ be the associated unit interval graph. Since $\bm{w}$ is
irreducible, the resulting graph $G_{\bm{w}}$ is connected. However,
$G_{\bm{w}}$ is not uniformly distributed among connected unit interval graphs
with $n$ vertices. We will address this issue in Section 6.4.

Recall that $d_{G_{\bm{w}}}$ denotes the graph distance in $G_{\bm{w}}$, and
$m_{V_{G_{\bm{w}}}}$ the uniform measure on its vertex set, denoted
$V_{G_{\bm{w}}}$.

######  Theorem 6.2.

The random mm-space
$(V_{G_{\bm{w}}},\frac{1}{\sqrt{n}}d_{G_{\bm{w}}},m_{V_{G_{\bm{w}}}})$
converges in distribution in the Gromov–Prokhorov topology to
$([0,1],\tfrac{1}{\sqrt{2}}d_{\mathbb{e}},\operatorname{Leb})$, where
$\mathbb{e}$ is a random Brownian excursion of length 1 and $d_{\mathbb{e}}$
is defined by the formula: for $x<y$ in $[0,1]$, we have

$d_{\mathbb{e}}(x,y)=\int_{x}^{y}\frac{dt}{\mathbb{e}(t)}.$

To prove Theorem 6.2, we will need two technical lemmas.

The first lemma gives an asymptotic expression for the distances in
$G_{\bm{w}}$ in terms of the height function of $\bm{w}$. Let us consider an
interval representation $(I_{1},\cdots,I_{n})$ of $G_{\bm{w}}$, with
$I_{j}=[a_{j},b_{j}]$, such that (13) holds. We assume as before that
$a_{1}<\dots<a_{n}$, and call $v_{j}$ the vertex of $G_{\bm{w}}$ corresponding
to the interval $I_{j}$. Also, in the following, $h_{\bm{w}}(i)$ is the
arrival height of the $i$-th up step in the Dyck path $\bm{w}$. The proof of
the following lemma is postponed to the next section.

######  Lemma 6.3.

Let ${\bm{w}}$ be a uniform random irreducible Dyck path of length $2n$. Then,
for any $\delta$ in $(0,1/2)$, the following convergence holds in probability,
as $n$ tends to $+\infty$:

$\frac{1}{\sqrt{n}}\ \sup_{\delta n\leq i<j\leq n-\delta
n}\,\left|\,d_{G_{\bm{w}}}(v_{i},v_{j})-\sum_{k=i}^{j-1}\frac{1}{h_{\bm{w}}(k)}\,\right|\,\longrightarrow\,0.$

The second lemma will allow to estimate the sum
$\sum_{k=i}^{j-1}\frac{1}{h_{\bm{w}}(k)}$ using the convergence of
$h_{\bm{w}}$ to the Brownian excursion.

######  Lemma 6.4.

There exists a probability space with copies of $\bm{w}$ (one copy for each
$n\geq 1$) and $\mathbb{e}$ such that for any $\delta$ in $(0,1/2)$,

$\sup_{\delta n\leq i<j\leq n-\delta
n}\,\left|\,\frac{1}{\sqrt{n}}\,\sum_{k=i}^{j-1}\frac{1}{h_{\bm{w}}(k)}-\int_{i/n}^{j/n}\frac{dt}{\sqrt{2}\,\mathbb{e}(t)}\,\right|\,\stackrel{{\scriptstyle
n\to+\infty}}{{\longrightarrow}}\,0\qquad\text{a.s.}.$

###### Proof.

We first claim that

(14) $\frac{h_{\bm{w}}(\lfloor
nx\rfloor)}{\sqrt{n}}\stackrel{{\scriptstyle(d)}}{{\longrightarrow}}\sqrt{2}\,\mathbb{e}(x)$

uniformly for all $x\in[0,1]$. Indeed, via the classical correspondence
between Dyck paths and plane trees, for $\bm{w}$ a uniform Dyck path of length
$2n$, the function $h_{\bm{w}}$ can be interpreted as the height function of a
uniform random plane tree with $n$ vertices, which corresponds to a
conditioned Galton-Watson tree with geometric offspring distribution of
parameter $1/2$ (whose standard deviation is $\sigma=\sqrt{2}$). It is known,
see _e.g._ [LG05, Theorem 1.15], that such a height fonction, correctly
renormalized, converges to $\frac{2}{\sigma}\mathbb{e}(x)$. The convergence
holds in distribution in Skorokhod space; however, when the limit is
continuous, convergence in Skorokhod space is equivalent to uniform
convergence [Bil99, p. 124]. As explained above, this immediately transfers to
the case where $\bm{w}$ is a uniform irreducible Dyck path of length $2n$.

Using Skorokhod representation theorem, there exists a probability space with
copies of $\bm{w}$ and $\mathbb{e}$ on which convergence in Eq. 14 holds
almost surely. We now work on this probability space.

Fix now $\delta\in(0,1/2)$,

$\displaystyle\sup_{\delta n\leq i<j\leq n-\delta
n}\,\left|\,\frac{1}{\sqrt{n}}\,\sum_{k=i}^{j-1}\frac{1}{h_{\bm{w}}(k)}-\frac{1}{n}\,\sum_{k=i}^{j-1}\frac{1}{\sqrt{2}\,\mathbb{e}(k/n)}\,\right|$
$\displaystyle\leq\sup_{\delta n\leq i<j\leq n-\delta
n}\,\frac{1}{n}\sum_{k=i}^{j-1}\bigg{|}\frac{\sqrt{n}}{h_{\bm{w}}(k)}-\frac{1}{\sqrt{2}\,\mathbb{e}(k/n)}\bigg{|}$
(15) $\displaystyle\leq\frac{1}{n}\,\sum_{k=\delta n}^{n-\delta
n-1}\bigg{|}\frac{\sqrt{n}}{h_{\bm{w}}(k)}-\frac{1}{\sqrt{2}\,\mathbb{e}(k/n)}\bigg{|}.$

Since $\mathbb{e}$ is a.s. positive on $[\delta,1-\delta]$, Eq. 14 implies
$\displaystyle{\frac{\sqrt{n}}{h_{\bm{w}}(\lfloor
nx\rfloor)}\stackrel{{\scriptstyle\text{a.s.}}}{{\to}}\frac{1}{\sqrt{2}\,\mathbb{e}(x)}}$
uniformly for $x$ in $[\delta,1-\delta]$. This implies that, a.s.,

(16) $\frac{1}{n}\,\sum_{k=\delta n}^{n-\delta
n-1}\bigg{|}\frac{\sqrt{n}}{h_{\bm{w}}(k)}-\frac{1}{\sqrt{2}\,\mathbb{e}(k/n)}\bigg{|}\,\longrightarrow\,0.$

Moreover, for $\delta n\leq i<j\leq n-\delta n$, we have

$\left|\frac{1}{n}\,\sum_{k=i}^{j-1}\frac{1}{\sqrt{2}\,\mathbb{e}(k/n)}-\int_{i/n}^{j/n}\frac{dt}{\sqrt{2}\,\mathbb{e}(t)}\,\right|\leq\int_{i/n}^{j/n}\left|\frac{1}{\sqrt{2}\,\mathbb{e}(\lfloor
tn\rfloor/n)}-\frac{1}{\sqrt{2}\,\mathbb{e}(t)}\right|dt\\\
\leq\sup_{x,y:\,\delta\leq x,y\leq 1-\delta\atop|x-y|\leq
1/n}\left|\frac{1}{\sqrt{2}\,\mathbb{e}(x)}-\frac{1}{\sqrt{2}\,\mathbb{e}(y)}\right|.$

Almost surely, it holds that $t\mapsto\frac{1}{\sqrt{2}\,\mathbb{e}(t)}$ is a
continuous function on the interval $[\delta,1-\delta]$, and thus is uniformly
continuous. The above upper bound therefore tends to $0$ as $n$ tends to
$+\infty$. Since this bound is independent from $i$ and $j$ (subject to the
constraint $\delta n\leq i<j\leq n-\delta n$) we can take the supremum over
$i$ and $j$ and conclude that

(17) $\sup_{\delta n\leq i<j\leq n-\delta
n}\,\left|\frac{1}{n}\,\sum_{k=i}^{j-1}\frac{1}{\sqrt{2}\,\mathbb{e}(k/n)}-\int_{i/n}^{j/n}\frac{dt}{\sqrt{2}\,\mathbb{e}(t)}\,\right|\,\longrightarrow\,0.$

Bringing Sections 6.2, 16 and 17 together concludes the proof of Lemma 6.4. ∎

###### Proof of Theorem 6.2.

Let us write
$X_{n}=(V_{G_{\bm{w}}},\frac{1}{\sqrt{n}}d_{G_{\bm{w}}},m_{V_{G_{\bm{w}}}})$
and $X_{\infty}=([0,1],\tfrac{1}{\sqrt{2}}d_{\mathbb{e}},\operatorname{Leb})$.
For proving the Gromov–Prokhorov convergence of $X_{n}$ to $X_{\infty}$ the
strategy is to use Theorem 3.6. For this purpose we introduce on $X_{n}\times
X_{\infty}$ a relation $R_{n,\delta}$ and a distribution $\nu$ which allow to
bound the box distance $\Box(X_{n},X)$ (see Definition 3.5).

Fix $\delta>0$. Let $R_{n,\delta}\subseteq X_{n}\times X_{\infty}$ be the
relation given by $R_{n,\delta}:=\\{(v_{1+\lfloor xn\rfloor},x),\,\delta\leq
x\leq 1-\delta\\}$, where $v_{k}$ denotes, as before, the vertex of
$G_{\bm{w}}$ corresponding to the $k$-th interval of an interval
representation of $G_{\bm{w}}$. Let also $\nu$ be the distribution of
$(v_{1+\lfloor nU\rfloor},U)$ where $U$ is uniform in $[0,1]$. Since
$1+\lfloor nU\rfloor$ is uniform in $[n]$ the first marginal of $\nu$ is
$m_{V_{G_{\bm{w}}}}$, so that $\nu$ is a coupling between $m_{V_{G_{\bm{w}}}}$
and $\operatorname{Leb}$. By construction we have
$\nu(R_{n,\delta})=1-2\delta$.

The discrepancy (see again Definition 3.5) of $R_{n,\delta}$ is equal to

$\operatorname{disc}(R_{n,\delta})=\sup_{(x_{1},x^{\prime}_{1}),(x_{2},x^{\prime}_{2})\in
R_{n,\delta}}\left|\frac{1}{\sqrt{n}}\,d_{G_{\bm{w}}}(x_{1},x_{2})-\frac{1}{\sqrt{2}}\,d_{\mathbb{e}}(x^{\prime}_{1},x^{\prime}_{2})\right|.$

We have

$\displaystyle\operatorname{disc}(R_{n,\delta})$
$\displaystyle=\sup_{\delta\leq x<y\leq
1-\delta}\,\left|\,\frac{1}{\sqrt{n}}\,d_{G_{\bm{w}}}(v_{1+\lfloor
xn\rfloor},v_{1+\lfloor
yn\rfloor})-\int_{x}^{y}\frac{dt}{\sqrt{2}\,\mathbb{e}(t)}\,\right|$
$\displaystyle\leq\sup_{1+\lfloor n\delta\rfloor\leq i<j\leq 1+\lfloor
n(1-\delta)\rfloor}\,\left|\,\frac{1}{\sqrt{n}}\,d_{G_{\bm{w}}}(v_{i},v_{j})-\int_{i/n}^{j/n}\frac{dt}{\sqrt{2}\,\mathbb{e}(t)}\,\right|+\frac{2}{n}\sup_{t\in[\delta,1-\delta]}\frac{1}{\sqrt{2}\,\mathbb{e}(t)}.$

From Lemmas 6.3 and 6.4, we know that the first summand of this upper bound
tends to $0$ in probability as $n$ tends to $+\infty$. The second one tends to
$0$ as well, since
$\sup_{t\in[\delta,1-\delta]}\frac{1}{\sqrt{2}\,\mathbb{e}(t)}$ is a random
variable independent of $n$. We conclude that
$\operatorname{disc}(R_{n,\delta})$ tends in probability to $0$.

By definition of the box distance,

$\Box(X_{n},X_{\infty})\leq\max(\operatorname{disc}(R_{n,\delta}),2\delta),$

so that
$\mathbb{P}(\Box(X_{n},X_{\infty})>2\delta)\leq\mathbb{P}(\operatorname{disc}(R_{n,\delta})>2\delta)$.
The latter tends to $0$ since $\operatorname{disc}(R_{n,\delta})$ tends in $0$
in probability, and therefore, $\mathbb{P}(\Box(X_{n},X_{\infty})>2\delta)$
tends to $0$. This holds for any $\delta>0$, i.e. $X_{n}$ tends to
$X_{\infty}$ in probability for the box distance, in the probability space
constructed in Lemma 6.4. We conclude that in the original probability space,
$X_{n}$ tends to $X_{\infty}$ in distribution for the Gromov–Prokhorov
topology, as wanted. ∎

###  6.3. Proof of Lemma 6.3

Fix an irreducible Dyck path $w$ of length $2n$. We start by explaining how to
compute distances in $G_{w}$. We consider as usual an interval representation
of $G_{w}$, denoted $\mathcal{I}=(I_{1},...,I_{n})$, with
$I_{j}=[a_{j},b_{j}]$ for all $i$, and $a_{1}<a_{2}<\dots<a_{n}$. We also
denote $v_{j}$ the vertex of $G_{w}$ represented by $I_{j}$. For $i\leq n$, we
let $f_{w}(i)$ be the number of up steps between the $i$-th up step (excluded)
and the $i$-th down step in $w$. Note that $f_{w}(i)>0$ for all $i<n$ since
$w$ is irreducible. Recall that in the correspondance between the Dyck path
$w$ and the unit interval graph $G_{w}$, the $i$-th up step and the $i$-th
down step in $w$ corresponds to the bound $a_{i}$ and $b_{i}$ of the interval
$I_{i}$. Hence, by definition, $f_{w}(i)$ is the maximal $k$ such that the
interval $I_{i+k}$ starts before the end of $I_{i}$, _i.e._ it is the maximal
$k$ such that $v_{i}$ and $v_{i+k}$ are connected in $G_{w}$. This property
allows to compute distances in $G_{w}$ using the function $f_{w}$ (see Fig.
9).

######  Lemma 6.5.

Let $w$ be an irreducible Dyck path of length $2n$ and take $i<j$ in $[n]$.
Define $i_{0}=i$ and recursively $i_{m+1}=i_{m}+f_{w}(i_{m})$ until $i_{m}\geq
j$. One has

(18) $
d_{G_{w}}(v_{i},v_{j})=\left\lceil\sum_{k=i}^{j-1}\frac{1}{f_{w}(\max\\{i_{m}:i_{m}\leq
k\\})}\right\rceil,$

where $\lceil x\rceil$ is the smallest integer greater than or equal to $x$.

Figure 9. Illustration of Lemma 6.5 and its notation. Left: the unit interval
graph associated to the Dyck path $w$ of Fig. 8, and a shortest path from
$v_{1}$ to $v_{5}$. Right: the corresponding function $f_{w}$, and how to read
on it that $d_{G_{w}}(v_{1},v_{5})=\lceil
1/f_{w}(i_{0})+1/f_{w}(i_{0})+1/f_{w}(i_{1})+1/f_{w}(i_{2})\rceil=\lceil
1/2+1/2+1/1+1/2\rceil=3$.

###### Proof.

It is clear from the interval representation of $G_{w}$ that for any $i\leq
k\leq j$ we have

$d_{G_{w}}(v_{i},v_{j})\geq d_{G_{w}}(v_{k},v_{j}).$

Hence finding a shortest path from $v_{i}$ to $v_{j}$ ($i<j$) can be realized
by the following gready procedure:

  * •

if $v_{i}$ is connected to $v_{j}$, we have a path of length $1$;

  * •

otherwise, we find the neighbor of $v_{i}$ with greatest label, which is
$v_{i+f_{w}(i)}$ as explained above. We take the edge
$\\{v_{i},v_{i+f_{w}(i)}\\}$, concatenated with a shortest path from
$v_{i+f_{w}(i)}$ to $v_{j}$ built recursively by the same procedure.

In terms of distance, this yields (for $i<j$)

$d_{G_{w}}(v_{i},v_{j})=\begin{cases}1&\text{ if $j\leq i+f_{w}(i)$;}\\\
1+d_{G_{w}}(v_{i+f_{w}(i)},v_{j})&\text{ otherwise.}\end{cases}$

It is easy to verify that the right-hand side of (18) satisfies the same
recursive characterization, proving the lemma. (The integer part guarantees
that the formula is true even if $i_{m}>j$.) ∎

Let us now consider a uniform random irreducible Dyck path $\bm{w}$ of length
$2n$. Our goal is to show that $f_{\bm{w}}(\max\\{i_{m}:i_{m}\leq k\\})$ is
close to $h_{\bm{w}}(k)$. We first show that $f_{\bm{w}}(i)$ and
$h_{\bm{w}}(i)$ are typically close to each other. We start with a classical
concentration type results for Dyck paths.

######  Lemma 6.6.

Let $\bm{w}$ be a uniform random irreducible Dyck path of length $2n$. Fix
$\varepsilon_{n}=n^{-0.1}$. Then, with probability tending to $1$, for all
intervals $I\subset[2n]$ of size at least $n^{0.4}$, the proportion of up
steps in $I$ lies in
$[\frac{1}{2}-\varepsilon_{n};\frac{1}{2}+\varepsilon_{n}]$.

###### Proof.

Let $\tilde{\bm{w}}$ be a uniform random binary word of length $2n$. Starting
from the standard estimate $\mathbb{P}(\tilde{\bm{w}}\text{ is an irreducible
Dyck path})=\frac{1}{n}\binom{2n-2}{n-1}\times 2^{-2n}=\Theta(n^{-3/2})$, we
get that, for any event $E_{n}$,

$\mathbb{P}(\bm{w}\in
E_{n})=\mathcal{O}\left(n^{3/2}\mathbb{P}(\tilde{\bm{w}}\in E_{n})\right).$

Let $E_{n}$ be the following event: there exists an interval $I\subset[2n]$ of
size at least $n^{0.4}$ such that the proportion of up steps in $I$ is not in
$[\tfrac{1}{2}-\varepsilon_{n};\tfrac{1}{2}+\varepsilon_{n}]$. By the union
bound

$\displaystyle\mathbb{P}\left(\tilde{\bm{w}}\in E_{n}\right)$
$\displaystyle\leq(2n)^{2}\max_{I\subset[2n]\,\text{s.t.}\,|I|\geq
n^{0.4}}\mathbb{P}\left(\text{the proportion of 'up' in $I$ is not in
$[\tfrac{1}{2}-\varepsilon_{n};\tfrac{1}{2}+\varepsilon_{n}]$}\right)$
$\displaystyle\leq(2n)^{2}\max_{s\geq
n^{0.4}}\mathbb{P}\left(\left|\mathrm{Binom}(s,1/2)-s/2\right|>s\varepsilon_{n}\right)$
$\displaystyle\leq(2n)^{2}\max_{s\geq
n^{0.4}}2\exp\left(-2s\varepsilon_{n}^{2}\right),\text{ using the Hoeffding
inequality}$ $\displaystyle\leq 8n^{2}\exp\left(-2n^{0.4-0.2}\right).$

This proves that $\mathbb{P}(\bm{w}\in E_{n})\leq e^{-cn^{\alpha}}$ for some
$c,\alpha>0$, hence concluding the proof. ∎

######  Corollary 6.7.

Let $\bm{w}$ be a uniform random irreducible Dyck path of length $2n$. Fix
$\varepsilon_{n}=n^{-0.1}$. With probability tending to $1$, the following
holds. For all $i$ such that either $h_{\bm{w}}(i)\geq n^{0.4}$ or
$f_{\bm{w}}(i)\geq n^{0.4}$, the quotient
$\frac{h_{\bm{w}}(i)}{f_{\bm{w}}(i)}$ belongs to
$[1-5\varepsilon_{n};1+5\varepsilon_{n}]$.

###### Proof.

We observe that, by definition of $h_{\bm{w}}(i)$, there are $i-h_{\bm{w}}(i)$
down steps before the $i$-th up step of $w$. Hence there are $h_{\bm{w}}(i)$
down steps between the $i$-th up step (excluded) and the $i$-th down step of
${\bm{w}}$ (included). By definition, the number of up steps in the same
interval is $f_{\bm{w}}(i)$. Hence if either $h_{\bm{w}}(i)\geq n^{0.4}$ or
$f_{\bm{w}}(i)\geq n^{0.4}$, this interval has length at least $n^{0.4}$ and
Lemma 6.6 applies. We get that
$\frac{f_{\bm{w}}(i)}{f_{\bm{w}}(i)+h_{\bm{w}}(i)}$ belongs to
$[\frac{1}{2}-\varepsilon_{n};\frac{1}{2}+\varepsilon_{n}]$. Elementary
manipulations then imply that, for $n$ large enough,
$\frac{h_{\bm{w}}(i)}{f_{\bm{w}}(i)}$ belongs to
$[1-5\varepsilon_{n};1+5\varepsilon_{n}]$, concluding the proof of the lemma.
∎

######  Corollary 6.8.

Let $\bm{w}$ be a uniform random Dyck path of length $2n$. For any $\delta$ in
$(0,1/2)$, we have the following convergence in probability:

$\frac{1}{\sqrt{n}}\ \sup_{\delta n\leq i<j\leq n-\delta
n}\,\left|\,d_{G_{\bm{w}}}(v_{i},v_{j})-\sum_{k=i}^{j-1}\frac{1}{h_{\bm{w}}(\max\\{i_{m}:i_{m}\leq
k\\})}\,\right|\,\longrightarrow\,0.$

###### Proof.

It is enough to check that, for any $\delta$ in $(0,1/2)$, we have the
following convergence in probability:

(19) $\sup_{\delta n\leq\ell\leq n-\delta
n}\sqrt{n}\left|\frac{1}{f_{\bm{w}}(\ell)}-\frac{1}{h_{\bm{w}}(\ell)}\right|\,\longrightarrow\,0.$

Indeed, if this holds, it suffices to use Eq. 18 and to sum the above estimate
for $\ell=\ell(k)=\max\\{i_{m}:i_{m}\leq k\\}$ for $k$ in
$\\{i,\cdots,j-1\\}$.

The left-hand side of (19) rewrites as

$\sup_{\delta n\leq\ell\leq n-\delta
n}\left(\frac{\sqrt{n}}{h_{\bm{w}}(\ell)}\left|\frac{h_{\bm{w}}(\ell)}{f_{\bm{w}}(\ell)}-1\right|\right)\leq\frac{\sqrt{n}}{\inf_{\delta
n\leq\ell\leq n-\delta n} h_{\bm{w}}(\ell)}\cdot\sup_{\delta n\leq\ell\leq
n-\delta n}\left|\frac{h_{\bm{w}}(\ell)}{f_{\bm{w}}(\ell)}-1\right|.$

Recall from (14) that $\frac{1}{\sqrt{n}}h_{\bm{w}}(\lfloor nx\rfloor)$
converges in distribution to $\sqrt{2}\,\mathbb{e}(x)$. We then have

$\frac{\sqrt{n}}{\inf_{\delta n\leq\ell\leq n-\delta n}
h_{\bm{w}}(\ell)}\to\frac{1}{\inf_{x\in
[\delta,1-\delta]}\sqrt{2}\,\mathbb{e}(x)},$

in distribution, as $n$ tends to $+\infty$. Note that the right-hand-side is
a.s. finite since the Brownian excursion does not vanish in
$[\delta,1-\delta]$. Moreover, with probability tending to $1$, we have that
$h_{\bm{w}}(\ell)\geq n^{0.4}$ for all $\ell$ in $[\delta n,n-\delta n]$. Thus
we can apply Corollary 6.7, and we get, that with probability tending to $1$

$\sup_{\delta n\leq\ell\leq n-\delta
n}\left|\frac{h_{\bm{w}}(\ell)}{f_{\bm{w}}(\ell)}-1\right|\leq
5\varepsilon_{n}=5n^{-0.1}.$

Bringing everything together proves Eq. 19, and thus Corollary 6.8. ∎

######  Lemma 6.9.

The following holds with probability tending to $1$. For any $i\leq k<j$, we
have

$|h_{\bm{w}}(k)-h_{\bm{w}}(\max\\{i_{m}:i_{m}\leq k\\})|\leq n^{0.45}.$

###### Proof.

Set $k^{\prime}:=\max\\{i_{m}:i_{m}\leq k\\}$ and let $I$ be the interval
between the $k^{\prime}$-th up step (excluded) and the $k$-th up step
(included).

We first bound the length of this interval. Since $h_{\bm{w}}$ converges after
normalization in space by $\sqrt{n}$ to the Brownian excursion, with
probability tending to 1, it holds that

$\sup_{i\leq n}h_{\bm{w}}(i)\leq n^{0.52}.$

Using Corollary 6.7, we get that, with probability tending to 1,

$\sup_{i\leq n}f_{\bm{w}}(i)\leq n^{0.53}.$

By construction of the sequence $(i_{m})$, the number of up-steps in $I$ is
bounded as follows:

$|k-k^{\prime}|\leq f_{\bm{w}}(k^{\prime})\leq\sup_{i\leq n}f_{\bm{w}}(i)\leq
n^{0.53},$

where the last inequality holds with probability tending to $1$. By Lemma 6.6,
with probability tending to 1, the number of down steps satisfy a similar
inequality up to a factor tending to $1$. We conclude that the inequality
$|I|\leq n^{0.54}$ holds with probability tending to $1$.

We now observe that $h_{\bm{w}}(k)-h_{\bm{w}}(k^{\prime})$ is the difference
between the number of up and down steps in the interval $I$, and we
distinguish two cases.

  * •

If $|I|\leq n^{0.45}$, then trivially

$|h_{\bm{w}}(k)-h_{\bm{w}}(k^{\prime})|\leq|I|\leq n^{0.45}.$

  * •

Otherwise, $n^{0.45}\leq|I|\leq n^{0.54}$. By Lemma 6.6, with probability
tending to 1, we have

$|h_{\bm{w}}(k)-h_{\bm{w}}(k^{\prime})|\leq 2\varepsilon_{n}|I|\leq
2n^{-0.1}n^{0.54}\leq n^{0.45}.\qed$

###### Proof of Lemma 6.3.

Fix $\delta>0$. Using again the convergence of $h_{\bm{w}}$ to the Brownian
excursion, with probability tending to 1, we have

$\inf_{\ell\in[\delta n,n-\delta n]}h_{\bm{w}}(\ell)\geq n^{0.49}.$

Thus (using also Lemma 6.9), with probability tending to 1, for any $i\leq
k<j$ in $[\delta n,n-\delta n]$,

$\left|\frac{1}{h_{\bm{w}}(k)}-\frac{1}{h_{\bm{w}}(\max\\{i_{m}:i_{m}\leq
k\\})}\right|\leq\frac{|h_{\bm{w}}(k)-h_{\bm{w}}(\max\\{i_{m}:i_{m}\leq
k\\})|}{h_{\bm{w}}(k)\,h_{\bm{w}}(\max\\{i_{m}:i_{m}\leq
k\\})}\leq\frac{n^{0.45}}{n^{0.98}}=n^{-0.53}.$

Summing over $k$, we get that, with probability tending to $1$,

$ \frac{1}{\sqrt{n}}\sup_{\delta n\leq i<j\leq n-\delta
n}\sum_{k=i}^{j-1}\left|\frac{1}{h_{\bm{w}}(k)}-\frac{1}{h_{\bm{w}}(\max\\{i_{m}:i_{m}\leq
k\\})}\right|\leq n^{-0.03}.$

Together with Corollary 6.8, this yields

$\frac{1}{\sqrt{n}}\ \sup_{\delta n\leq i<j\leq n-\delta
n}\,\left|\,d_{G_{\bm{w}}}(v_{i},v_{j})-\sum_{k=i}^{j-1}\frac{1}{h_{\bm{w}}(k)}\,\right|\,\longrightarrow\,0,$

as wanted. ∎

###  6.4. From uniform irreducible Dyck paths to uniform unit interval graphs

Let $\bm{G}_{n}$ be a uniform (possibly disconnected) unit interval graph with
$n$ vertices. The goal of this section is to prove that $\bm{G}_{n}$ has the
same Gromov-Prokhorov limit as that found for $G_{\bm{w}}$ in Theorem 6.2. As
a first step, we prove the result for a uniform connected unit interval graph
${\bm{C}_{n}}$ with $n$ vertices. In the sequel, we use
$d_{\mathrm{T}V}(\mu,\nu)$ for the total variation distance between
probability measures $\mu$ and $\nu$, and by extension, for random variables
$X$ and $Y$, we write $d_{\mathrm{T}V}(X,Y)$ for the total variation distance
between their laws.

######  Lemma 6.10.

Let $\bm{w}$ be a uniform irreducible Dyck path of length $2n$ and
$\bm{C}_{n}$ be a uniform connected unit interval graph with $n$ vertices. It
holds that

$\lim_{n\to+\infty} d_{\mathrm{T}V}(G_{\bm{w}},\bm{C}_{n})=0.$

###### Proof.

Let us consider the map $w\mapsto G_{w}$ mapping irreducible Dyck paths of
length $2n$ to connected unit interval graphs with $n$ vertices. From
Proposition 6.1, each connected unit interval graph has either 1 or 2 pre-
images. The lemma will follow if we show that the probability that
$\bm{C}_{n}$ has exactly 1 pre-image tends to $0$ as $n$ tends to $+\infty$.

But a connected unit interval graph has exactly 1 pre-image $w$ if and only if
$w$ is irreducible and palindromic. Moreover

$\frac{\\#\left\\{\begin{tabular}[]{c}palindromic irreducible\\\ Dyck paths of
length $2n$\end{tabular}\right\\}}{\\#\left\\{\begin{tabular}[]{c}irreducible
Dyck\\\ paths of length
$2n$\end{tabular}\right\\}}=\frac{\\#\left\\{\begin{tabular}[]{c}Dyck
prefixes\\\ of length
$n-1$\end{tabular}\right\\}}{\\#\left\\{\begin{tabular}[]{c}Dyck paths\\\ of
length
$2n-2$\end{tabular}\right\\}}=\frac{\displaystyle\binom{n-1}{\lfloor(n-1)/2\rfloor}}{\displaystyle\frac{1}{n}\binom{2n-2}{n-1}},$

where the enumeration for Dyck prefixes can be found, _e.g._ , in [Sta99,
Ex.$6.19$, p.$219$]. The right-hand side obviously tends to $0$, ending the
proof of the lemma. ∎

######  Corollary 6.11.

Theorem 6.2 holds true with $\bm{C}_{n}$ instead of $G_{\bm{w}}$.

We now consider a uniform (possibly disconnected) unit interval graph
$\bm{G}_{n}$ with $n$ vertices. We use the standard notation
$X_{n}=\mathcal{O}_{\mathbb{P}}(1)$ to say that a sequence of random variables
$X_{n}$ is stochastically bounded555  _i.e._ for every $\varepsilon>0$ there
exist constants $k_{\varepsilon},n_{\varepsilon}$ such that for $n\geq
n_{\varepsilon}$ one has $\mathbb{P}(|X_{n}|\leq k_{\varepsilon})\geq
1-\varepsilon$..

######  Lemma 6.12.

Let $\bm{G}_{n}$ be as above and let $L_{n}$ be the size of its largest
connected component. Then $n-L_{n}=\mathcal{O}_{\mathbb{P}}(1)$.

###### Proof.

Let $C(z)$ and $G(z)$ be the ordinary generating series of connected and
general unit interval graphs with respect to the number of vertices. Since a
general graph is a multiset of connected graphs, using [FS09, Theorem 1.1], we
have

$G(z)=\exp\left(\sum_{k\geq 1}\frac{1}{k}C(z^{k})\right).$

We write this as $G(z)=F(C(z),z)$ where

$F(w,z)=\exp(w)\cdot\exp\left(\sum_{k\geq 2}\frac{1}{k}C(z^{k})\right).$

From Proposition 6.1, we get that

$C(z)=\tfrac{1}{2}I(z)+\tfrac{1}{2}P(z),$

where $I(z)$ and $P(z)$ are respectively the series of irreducible Dyck paths
and of palindromic irreducible Dyck paths. Since irreducible Dyck paths of
length $2n+2$ are in one-to-one correspondence with Dyck paths of length $2n$,
the series $I(z)$ has radius of convergence $\rho=1/4$ and a square-root
singularity. Moreover,

$P(z)=1+\sum_{n\geq 1}\binom{n-1}{\lfloor(n-1)/2\rfloor}z^{n}$

has radius of convergence $1/2$. Therefore $C(z)$ has a square-root
singularity at $\rho=1/4$. In particular, it is of algebraic-logarithmic type,
as defined in [Gou98, Definition 1]. Therefore we can apply [Gou98, Theorem 1]
– in this reference, the author only considers the case where the function $F$
depends on one variable $w$, but his proof readily extends to the case of a
bivariate function $F(w,z)$, provided that it is analytic at
$(w,z)=(C(\rho),\rho)$. We get that $n-L_{n}$ converges to a discrete law,
proving that it is stochastically bounded. ∎

We can now prove the main result of this section, whose statement we recall:

Theorem 2.3 _Let $\bm{G}_{n}$ be a uniform random unit interval graph with $n$
vertices. The random mm-space
$(\bm{G}_{n},\frac{1}{\sqrt{n}}d_{\bm{G}_{n}},m_{V_{\bm{G}_{n}}})$ converges
in distribution in the Gromov–Prokhorov topology to
$\linebreak([0,1],\tfrac{1}{\sqrt{2}}d_{\mathbb{e}},\operatorname{Leb})$. _

###### Proof.

We let $\bm{G}^{0}_{n}$ be the largest connected component of $\bm{G}_{n}$.
From Lemma 6.12, $\bm{G}^{0}_{n}$ has size
$L_{n}=n-\mathcal{O}_{\mathbb{P}}(1)$. Moreover, conditioned to $L_{n}$,
$\bm{G}^{0}_{n}$ is a uniform connected unit interval graph with $L_{n}$
vertices. From Corollary 6.11, Theorem 6.2 holds true with a uniform connected
unit interval graph $\bm{C}_{n}$ instead of $G_{\bm{w}}$. Therefore the random
mm-space
$(\bm{G}^{0}_{n},\frac{1}{\sqrt{L}_{n}}d_{\bm{G}^{0}_{n}},m_{V_{\bm{G}^{0}_{n}}})$
converges in the GP topology to
$([0,1],\tfrac{1}{\sqrt{2}}d_{\mathbb{e}},\operatorname{Leb})$. The theorem
follows because
$d_{\mathrm{T}V}(m_{V_{\bm{G}^{0}_{n}}},m_{{V_{\bm{G}_{n}}}})=\frac{n-L_{n}}{n}$
and $d_{\bm{G}^{0}_{n}}$ is the distance $d_{\bm{G}_{n}}$ restricted to
$\bm{G}^{0}_{n}$. ∎

###  6.5. Number of copies of $K_{k}$

In this section, we find the asymptotic behavior of the number of copies of
the complete graph $K_{k}$ in a uniform random unit interval graph
$\bm{G}_{n}$. Unlike the case of permutation and circle graphs, this does not
follow directly from our scaling limit result, but builds on the same
intermediate considerations.

As above, we first consider the unit interval graph $G_{\bm{w}}$ associated
with a uniform irreducible Dyck path $\bm{w}$ of length $2n$. We start with
the following deterministic lemma, where we use the notation $f_{w}(i)$ from
Section 6.3.

######  Lemma 6.13.

Let $w$ be an irreducible Dyck path, and $G_{w}$ its associated unit interval
graph. The following holds:

$\\#\left\\{\text{cliques of size $k$ in
}G_{w}\right\\}=\sum_{i=1}^{n}\binom{f_{w}(i)}{k-1}.$

###### Proof.

Consider a $k$-tuple of vertices $(v_{i_{1}},v_{i_{2}},\dots,v_{i_{k}})$ of
$G_{w}$, where the vertices of $G_{w}$ are labeled as in Section 6.2 and where
$i_{1}<i_{2}<\dots<i_{k}$. Recall that the vertex $v_{i_{j}}$ corresponds to
some interval $[a_{i_{j}},b_{i_{j}}]$.

We claim that this $k$-tuple induces a clique in $G_{w}$ if and only if
$i_{k}\leq i_{1}+f_{w}(i_{1})$. This condition is clearly necessary, since
this is a necessary condition for $i_{k}$ to be connected to $i_{1}$.
Conversely, if $i_{k}\leq i_{1}+f_{w}(i_{1})$, then all of $a_{i_{2}}$, …,
$a_{i_{k}}$ belong to $[a_{i_{1}},b_{i_{1}}]$. Since all intervals have unit
length, all intervals $[a_{i_{j}},b_{i_{j}}]$ intersect each other, and the
vertices $(v_{i_{1}},v_{i_{2}},\dots,v_{i_{k}})$ indeed induce a clique
$K_{k}$ in $G_{w}$.

We now count such $k$-tuples, grouping them by the value of $i_{1}$. For
$i_{1}$ in $[n]$, there are $\binom{f_{w}(i_{1})}{k-1}$ ways to choose
$i_{2}<\dots<i_{k}$ larger than $i_{1}$ such that $i_{k}\leq
i_{1}+f_{w}(i_{1})$. The formula in the lemma follows immediately. ∎

This lemma allows to find the asymptotic behavior of the number of cliques of
size $k$ in $G_{\bm{w}}$, where $\bm{w}$ is a uniform random irreducible Dyck
path of length $2n$.

######  Lemma 6.14.

For any $K\geq 1$, we have the following joint convergence in distribution:

$\left(\frac{\\#\left\\{\text{cliques of size $k$ in
}G_{\bm{w}}\right\\}}{n^{\frac{k+1}{2}}}\right)_{2\leq k\leq
K}\to\left(\frac{2^{(k-1)/2}}{(k-1)!}
\int_{0}^{1}\mathbb{e}(t)^{k-1}dt\right)_{2\leq k\leq K},$

where $\mathbb{e}(t)$ is a Brownian excursion.

###### Proof.

For $k\leq K$, we let $N_{k}(G_{\bm{w}})$ be the number of cliques of size $k$
in $G_{\bm{w}}$. From Lemma 6.13, we have

$n^{-\frac{k+1}{2}}N_{k}(G_{\bm{w}})=n^{-\frac{k+1}{2}}\sum_{i=1}^{n}\binom{f_{\bm{w}}(i)}{k-1}=n^{-\frac{k+1}{2}}\sum_{i=1}^{n}\left(\frac{f_{\bm{w}}(i)^{k-1}}{(k-1)!}+O\big{(}f_{\bm{w}}(i)^{k-2}\big{)}\right)\\\
=\frac{1}{n}\left(\sum_{i=1}^{n}\frac{1}{(k-1)!}\left(\frac{f_{\bm{w}}(i)}{\sqrt{n}}\right)^{k-1}\right)+\frac{1}{\sqrt{n}}\
O\left(\sup_{i}\left(\frac{f_{\bm{w}}(i)}{\sqrt{n}}\right)^{k-2}\right).$

Using the convergence of $\frac{h_{\bm{w}}}{\sqrt{n}}$ to a Brownian excursion
and Corollary 6.7, we see that $\frac{f_{\bm{w}}(i)}{\sqrt{n}}$ is bouded
almost surely. Consequently, for $k\geq 2$,

$n^{-\frac{k+1}{2}}N_{k}(G_{\bm{w}})=\frac{1}{n}\left(\sum_{i=1}^{n}\frac{1}{(k-1)!}\left(\frac{f_{\bm{w}}(i)}{\sqrt{n}}\right)^{k-1}\right)+o_{P}(1),$

where, as usual, the notation $o_{P}(1)$ represents a random variable
converging to $0$ in probability. Using Corollary 6.7 and observing that terms
with $f_{\bm{w}}(i)<n^{0.4}$ and $h_{\bm{w}}(i)<n^{0.4}$ have a negligible
contribution, we get that with a probability tending to one

$n^{-\frac{k+1}{2}}N_{k}(G_{\bm{w}})=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{(k-1)!}\left(\frac{h_{\bm{w}}(i)}{\sqrt{n}}\right)^{k-1}+o_{P}(1)\\\
=\frac{1}{(k-1)!}\int_{0}^{1}\left(\frac{h_{\bm{w}}(\lfloor
nt\rfloor)}{\sqrt{n}}\right)^{k-1}dt+o_{P}(1).$

Recall from Eq. 14 that the random function $\frac{h_{\bm{w}}(\lfloor
nt\rfloor)}{\sqrt{n}}$ converges uniformly in distribution to
$\sqrt{2}\,\mathbb{e}(t)$, in the space of continuous functions on $[0,1]$
equipped with uniform convergence. Since $f\mapsto\left(1,\int f,\int
f^{2},\dots,\int f^{K-1}\right)$ is continuous on that space this implies that

$n^{-\frac{k+1}{2}}N_{k}(G_{\bm{w}})\rightarrow\frac{2^{(k-1)/2}}{(k-1)!}
\int_{0}^{1}\mathbb{e}(t)^{k-1}dt,$

jointly for $2\leq k\leq K$. The lemma is proved. ∎

From Lemma 6.10, a version of Lemma 6.14 where $G_{\bm{w}}$ is replaced by a
uniform random connected unit interval graph $\bm{C}_{n}$ also holds. Finally,
mimicking the proof of Theorem 2.3, the result also holds for a uniform random
(nonnecessarily connected) unit interval graph $\bm{G}_{n}$, concluding the
proof of Theorem 2.4.

##  Appendix A Proofs of two technical results

###  A.1. Proof of Proposition 5.5: indecomposable matchings and split-prime
circle graphs

Let us recall the statement of the Proposition.

Proposition 5.5. _Let $G$ be a circle graph and $\mathfrak{m}$ be a matching
that represents $G$. Then $G$ is split-prime if and only if $\mathfrak{m}$ is
indecomposable. _

###### Proof.

Let $n$ denote the number of vertices of $G$. If $n\leq 3$ then $G$ is
trivially split-prime and $\mathfrak{m}$ cannot be decomposable so there is
nothing to prove. Assume $n\geq 4$.

Proof of $\mathfrak{m}$ decomposable $\Rightarrow$ $G$ has a nontrivial split.
Let $C_{1},C_{2},C_{3},C_{4}$ be the partition of $[2n]$ associated to the
$k$-decomposition of $\mathfrak{m}$. Let $V_{odd}$ (resp. $V_{even}$) be the
set of vertices of $G$ corresponding to chords of $C_{1}\cup C_{3}$ (resp.
$C_{2}\cup C_{4}$). The sets $V_{odd}$ and $V_{even}$ both contain at least
two vertices and form a nontrivial split, whose cut vertex set $V^{cut}_{odd}$
(resp. $V^{cut}_{even}$) consists of chords between $C_{1}$ and $C_{3}$ (resp.
of chords between $C_{2}$ and $C_{4}$). See Fig. 5 (right).

Proof of $G$ has a nontrivial split $\Rightarrow$ $\mathfrak{m}$ decomposable.
We distinguish three cases.

Case 1: $\mathfrak{m}$ has a chord $\\{a,a{+}1\\}$ for some $a$ (where $a{+}1$
is interpreted mod $2n$, as well as $a{+}2$ below). Let $b$ be such that
$\\{a{+}2,b\\}\in\mathfrak{m}$. Then $\mathfrak{m}$ admits a decomposition as
in Definition 5.3, where one of the sets $C_{i}$ is $\\{a,a{+}1,a{+}2\\}$ and
another is $\\{b\\}$. Hence the matching $\mathfrak{m}$ is indeed
decomposable.

Case 2: $G$ is disconnected but $\mathfrak{m}$ has no chord of the form
$\\{a,a{+}1\\}$. Let $V^{\prime}$ be the set of vertices of a connected
component of $G$. Each vertex in $V^{\prime}$ corresponds to a pair
$\\{a,b\\}$ in $\mathfrak{m}$, and we denote by $I$ the union of such pairs.
Up to choosing another connected component $V^{\prime}$, we may assume that
$1\notin I$. Let $C_{2}$ be the integer interval $[\min(I),\max(I)]$ (in
particular, all chords of $V^{\prime}$ have both extremities in $C_{2}$) and
$C_{1}$ its complement in $[2n]$. We claim that there is no chord from $C_{1}$
to $C_{2}$ in $\mathfrak{m}$. Indeed such a chord would necessarily cross a
chord corresponding to a vertex in $V^{\prime}$ (since such chords form a
connected set in the unit disk containing $\min(I)$ and $\max(I)$). Thus this
chord would itself correspond to a vertex in $V^{\prime}$, which is impossible
since it has an extremity in $C_{1}$.

We have proved that $\mathfrak{m}$ has only chords from $C_{1}$ to $C_{1}$,
and from $C_{2}$ to $C_{2}$. Since $\mathfrak{m}$ has no chord of the form
$\\{a,a{+}1\\}$, each of $C_{1}$ and $C_{2}$ has size at least 4, and
$(C_{1},C_{2},\emptyset,\emptyset)$ is a decomposition as in Definition 5.3.
Thus $\mathfrak{m}$ is decomposable.

Case 3: $G$ is connected. Since $G$ is assumed to be split-decomposable, its
vertex set admits a nontrivial split $\\{V_{odd},V_{even}\\}$, with
corresponding cut vertex sets $V_{odd}^{cut}$ and $V_{even}^{cut}$. Vertices
in $G$ correspond to chords in the matching $\mathfrak{m}$, and we let
$S_{odd}$ (resp. $S_{even}$, $S_{odd}^{cut}$ and $S_{even}^{cut}$) be the set
of points belonging to a chord in $V_{odd}$ (resp. $V_{even}$, $V_{odd}^{cut}$
and $V_{even}^{cut}$).

Figure 10. Two examples of splits where the corresponding sets $S_{even}$ and
$S_{odd}$ are not unions of at most two circular intervals. By convention,
green points/chords correspond to elements of $S_{odd}$/$V_{odd}$ and bold
chords indicate elements of the cut vertex set $V_{odd}^{cut}$ (and similarly
replacing green by red, and odd by even).

If each of $S_{odd}$ and $S_{even}$ were a union of at most two circular
intervals, we would immediately have a decomposition as in Definition 5.3 and
conclude that $\mathfrak{m}$ is decomposable. However this is not always the
case (as can be seen on the examples of Fig. 10). The strategy of proof is
thus to define a particular type of split, called pure $4$-split, that
satisfies the following:

  * •

first, there exists a pure $4$-split as soon as $G$ is split-decomposable;

  * •

second, for a pure $4$-split, $S_{odd}$ and $S_{even}$ are unions of at most
two circular intervals.

The decomposability of $\mathfrak{m}$ will follow immediately.

Since $G$ is connected, $V_{odd}^{cut}$ and $V_{even}^{cut}$ are nonempty. By
definition of cut-set, any chord in $V_{odd}^{cut}$ crosses any chord in
$V_{even}^{cut}$, hence has the same amount of elements of $S_{even}^{cut}$ on
each side. As a consequence, one can show that there exist a positive integer
$d$ and $4d$ nonempty sets $S^{cut}_{1}$, …, $S^{cut}_{4d}$ that appear in
this order counter-clockwise around the circle and such that:

  * •

$S_{odd}^{cut}=\bigcup_{j\text{ odd}}S^{cut}_{j}$ and
$S_{even}^{cut}=\bigcup_{j\text{ even}}S^{cut}_{j}$;

  * •

and any chord in the cut vertex sets $V_{even}^{cut}$ (resp. $V_{odd}^{cut}$)
goes from $S^{cut}_{j}$ to $S^{cut}_{j+2d}$ for some even $j\leq 2d$ (resp.
odd $j\leq 2d$).

We then say that the split $\\{V_{odd},V_{even}\\}$ is a $4d$-split. For
$j\in[4d]$, we also let $I_{j}$ be the smallest circular interval containing
$S^{cut}_{j}$ (not containing $S^{cut}_{j^{\prime}}$ for $j^{\prime}\neq j$).
The definition of the intervals $I_{j}$ is illustrated on the two examples of
Fig. 10; the example on the left is an $8$-split, while that on the right is a
$4$-split (but not a pure $4$-split).

Subcase 3a: $d>1$. When $d>1$, we claim that $I_{j}$ contains only points of
$S_{odd}$ (resp. $S_{even}$) whenever $j$ is odd (resp. even). Let us prove
the claim by contradiction and assume, w.l.o.g., that $I_{1}$ contains a point
in $S_{even}$. Let $c$ be the chord containing this point; by construction $c$
is in $V_{even}\setminus V_{even}^{cut}$. Hence $c$ cannot cross chords of
$V_{odd}^{cut}$ forcing both extremities of $c$ to be in $I_{1}$ (see Fig. 11,
left). The set of chords in $V_{even}$ with extremities in $I_{1}$ then form a
connected component (or several) of the graph $G$, contradicting the
connectedness of $G$. This proves the claim that $I_{j}$ contains only points
of $S_{odd}$ (resp. $S_{even}$) whenever $j$ is odd (resp. even).

Figure 11. Illustration of the proof of Proposition 5.5, Subcase 3a. Left: the
interval $I_{1}$ contains only green points. Right: there is no alternation of
colors between $I_{1}$ and $I_{2}$.

Furthermore, let us call $\vec{A}$ the oriented circular arc going from
$I_{1}$ to $I_{2}$. By construction, points in $\vec{A}$ are either in
$S_{odd}\setminus S_{odd}^{cut}$ or in $S_{even}\setminus S_{even}^{cut}$. We
claim that in $\vec{A}$, we first see points of $S_{odd}$ and then points of
$S_{even}$. Assume it is not the case, and that there exists a point $x$ of
$S_{even}$ preceding a point $y$ of $S_{odd}$ in $\vec{A}$. Since $G$ is
connected, $x$ must be connected by a series of chords to $I_{2}$, these
chords belonging by construction to $V_{even}\setminus V_{even}^{cut}$, while
$y$ must be connected by a series of chords to $I_{1}$, these chords belonging
by construction to $V_{odd}\setminus V_{odd}^{cut}$. This forces a chord of
$V_{even}\setminus V_{even}^{cut}$ to cross a chord of $V_{odd}\setminus
V_{odd}^{cut}$, which is impossible – see Fig. 11, right. In general, on the
arc going from $I_{j}$ to $I_{j+1}$, we first see points of $S_{even}$ and
then points of $S_{odd}$ if $j$ is even, and conversely if $j$ is odd.

This implies that the circle can be cut in $4d$ circular intervals $S_{1}$,…,
$S_{4d}$ such that $S_{odd}=\bigcup_{j\text{ odd}}S_{j}$ and and
$S_{even}=\bigcup_{j\text{ even}}S_{j}$. Moreover, edges of the cut set go
from $S_{j}$ to $S_{j+2d}$ for some $j$, while edges not in the cut set go
from some $S_{j}$ to itself. We then set

$\begin{array}[]{rclcrcl}C_{1}&\\!\\!\\!=\\!\\!\\!&S_{1}\cup\dots\cup
S_{d},&&C_{2}&\\!\\!\\!=\\!\\!\\!&S_{d+1}\cup\dots\cup S_{2d},\\\
C_{3}&\\!\\!\\!=\\!\\!\\!&S_{2d+1}\cup\dots\cup
S_{3d},&&C_{4}&\\!\\!\\!=\\!\\!\\!&S_{3d+1}\cup\dots\cup S_{4d}.\end{array}$

Up to renaming cyclically $(C_{1},C_{2},C_{3},C_{4})$ so that $1\in C_{1}$,
the $C_{i}$’s form a partition of the circle as in Definition 5.3, proving
that $\mathfrak{m}$ is decomposable.

Subcase 3b: $d=1$. When $d=1$, unlike in the previous case, it might happen
that there is a chord $c$ in $V_{odd}\setminus V_{odd}^{cut}$ having one
endpoint in $I_{2}$ and one in $I_{4}$ (see Fig. 12, left), or symmetrically a
chord $c^{\prime}$ in $V_{even}\setminus V_{even}^{cut}$ going from $I_{1}$
and $I_{3}$. We say that the split $\\{V_{odd},V_{even}\\}$ is even-pure
(resp. odd-pure) if there is no chord $c$ in $V_{odd}\setminus V_{odd}^{cut}$
having one endpoint in $I_{2}$ and one in $I_{4}$ (resp. no chord $c^{\prime}$
in $V_{even}\setminus V_{even}^{cut}$ having one endpoint in $I_{1}$ and one
in $I_{3}$). A split is pure if it is simultaneously odd-pure and even-pure.

When the split $\\{V_{odd},V_{even}\\}$ is pure, the same argument as in
Subcase 3a shows that $S_{odd}$ and $S_{even}$ decompose as $S_{1}\cup S_{3}$
and $S_{2}\cup S_{4}$ respectively, where $S_{1}$, $S_{2}$, $S_{3}$, $S_{4}$
are circular intervals appearing in this order counter-clockwise along the
circle. Thus $\mathfrak{m}$ is decomposable.

$\begin{array}[]{c}\includegraphics{ImpureSplit}\end{array}\quad\begin{array}[]{c}\includegraphics{GoodSplit}\end{array}$
Figure 12. Left: A split that is not even-pure, as there is a green edge from
$I_{2}$ to $I_{4}$. Modifying the split as indicated in the proof (here
$c=\\{5,15\\},C=\\{c\\}\cup\\{\\{14,16)\\}\\}$, and $V^{even}_{3}$ consists of
the chords $\\{6,8\\}$ and $\\{7,13\\}$) yields the bicoloration of the same
matching shown on the right picture. The corresponding split is both even-pure
and odd-pure.

We will show that one can always transform (possibly in several steps) an
impure $4$-split into a pure one. The notation and this part of the proof are
illustrated in Fig. 12. First observe that any $4$-split is either even-pure
or odd-pure (otherwise there would be crossing chords $c$ and $c^{\prime}$ in
$V_{odd}\setminus V_{odd}^{cut}$ and $V_{even}\setminus V_{even}^{cut}$
respectively, which is impossible). Without loss of generality, we can assume
that our initial split $\\{V_{odd},V_{even}\\}$ is odd-pure but not even-pure.
Let $c$ be a chord in $V_{odd}\setminus V_{odd}^{cut}$ having one endpoint in
$I_{2}$ and one in $I_{4}$. Since $c$ is not in $V_{odd}^{cut}$, it does not
cross chords in $V_{even}$. Thus this partitions $V_{even}$ into two mutually
noncrossing nonempty sets $V_{even}^{1}$ and $V_{even}^{3}$, the chords of
$V_{even}^{1}$ (resp. $V_{even}^{3}$) being on the same side of $c$ as $I_{1}$
(resp. $I_{3}$). Let $C$ be the connected component of $c$ in the induced
subgraph of $G$ on vertex set $V_{odd}\setminus V_{odd}^{cut}$. Then it is
easy to check that $V^{\prime}_{even}=V_{even}^{1}\cup C$ and
$V^{\prime}_{odd}=(V_{odd}\setminus C)\cup V_{even}^{3}$ forms a nontrivial
split of $G$, which is still odd-pure. Moreover, the intervals
$I^{\prime}_{2}$ and $I^{\prime}_{4}$ associated with this new split are
strictly smaller than $I_{2}$ and $I_{4}$. Therefore, we can iterate this
transformation until finding a pure nontrivial split. Since we have already
shown that $\mathfrak{m}$ is decomposable whenever $G$ contains a pure
nontrivial split, this ends the proof of the proposition. ∎

###  A.2. Proof of Lemma 5.10: distribution of atypical chords

Before recalling the statement of the lemma, we recall some notation. For a
matching $\mathfrak{m}$,
$x(\mathfrak{m})=\sum_{i=1}^{2n}\bm{1}[\mathfrak{m}(i)\equiv i+1]$ is the
number of chords between adjacent points, where $\equiv$ stands for equality
mod $2n$. Similarly
$y(\mathfrak{m})=\sum_{j=1}^{2n}\bm{1}[\mathfrak{m}(j)\equiv j+2]$. Finally

$z(\mathfrak{m})=\sum_{\begin{subarray}{c}1\leq k<\ell\leq 2n\\\
\ell-k\not\equiv\pm
1\end{subarray}}\bm{1}\big{[}\left\\{\mathfrak{m}(k),\mathfrak{m}(k+1)\right\\}\equiv\left\\{\ell,\ell+1\right\\}\big{]};$

_i.e._ $z(\mathfrak{m})$ counts pairs of consecutive points matched to another
pair of consecutive points. The definitions of $x(\mathfrak{m})$,
$y(\mathfrak{m})$ and $z(\mathfrak{m})$ are illustrated on Fig. 7. Finally,
recall that $M_{n}$ denotes a uniform random matching of size $n$, and
$X_{n}=x(M_{n})$, $Y_{n}=y(M_{n})$ and $Z_{n}=z(M_{n})$.

Lemma 5.10. _The triple $(X_{n},Y_{n},Z_{n})$ converges in distribution
towards a triple of independent Poisson random variables with mean 1. _

###### Proof.

It is enough to prove that the joint factorial moments of $X_{n}$, $Y_{n}$ and
$Z_{n}$ tend to $1$ (see pp. 60-62 in [Hof16] for a review on Poisson
convergence and joint factorial moments; in particular [Hof16, Theorem 2.6]
states that the convergence of joint factorial moments implies the joint
convergence in distribution). We write $(x)_{r}=x(x-1)\cdots(x-r+1)$ for
factorial powers. For integers $r,s,t\geq 1$, the joint factorial moments
expand as

(20) $\displaystyle\mathbb{E}\big{[}(X_{n})_{r}(Y_{n})_{s}(Z_{n})_{t}\big{]}$
$\displaystyle=\sum_{i_{1}\dots i_{r},j_{1}\dots j_{s}\atop
k_{1}<\ell_{1},\dots,k_{t}<\ell_{t}}P_{\mathbf{i},\mathbf{j},\mathbf{k}},$
$\displaystyle\text{where }P_{\mathbf{i},\mathbf{j},\mathbf{k}}$
$\displaystyle=\mathbb{P}\left(\begin{cases}M_{n}(i_{\alpha})\equiv
i_{\alpha}+1&\forall\alpha\leq r\\\ M_{n}(j_{\beta})\equiv
j_{\beta}+2&\forall\beta\leq s\\\
\left\\{M_{n}(k_{\gamma}),M_{n}(k_{\gamma}+1)\right\\}\equiv\left\\{\ell_{\gamma},\ell_{\gamma}+1\right\\}&\forall\gamma\leq
t\end{cases}\right)$

and the sum is taken over lists $\mathbf{i}=(i_{1},\dots,i_{r})$,
$\mathbf{j}=(j_{1},\dots,j_{s})$ and
$\mathbf{k}=((k_{1},\ell_{1}),\dots,(k_{t},\ell_{t}))$ such that

  * •

all $i_{\alpha}$’s are distinct;

  * •

all $j_{\beta}$’s are distinct;

  * •

all pairs $(k_{\gamma},\ell_{\gamma})$ are distinct and furthermore
$\ell_{\gamma}-k_{\gamma}\not\equiv\pm 1$, for every $\gamma\leq t$.

In the above sum, let us consider first the summands for which all indices
$i_{\alpha}$, $i_{\alpha}+1$, $j_{\beta}$, $j_{\beta}+2$, $k_{\gamma}$,
$k_{\gamma}+1$, $\ell_{\gamma}$ and $\ell_{\gamma}+1$ are distinct. We call
such terms $P_{\mathbf{i},\mathbf{j},\mathbf{k}}$ nice, while other terms are
referred to as painful. For each nice term,

$P_{\mathbf{i},\mathbf{j},\mathbf{k}}=2^{t}\frac{m_{n-r-s-2t}}{m_{n}}.$

Indeed, for each $\gamma$ we may choose whether
$M_{n}(k_{\gamma})=\ell_{\gamma}+1$ and $M_{n}(k_{\gamma}+1)=\ell_{\gamma}$ or
the converse, explaining the factor $2^{t}$. Additionally, once these choices
are made, the chords involving indices of ${\mathbf{i},\mathbf{j},\mathbf{k}}$
are fixed, and the remaining chords induce a uniform matching of size
$n-r-s-2t$. Using that $m_{n-1}/m_{n}=1/(2n-1)\sim 1/(2n)$, we have that for
fixed $r,s,t$ and for each nice term $P_{\mathbf{i},\mathbf{j},\mathbf{k}}$
the following holds:

(21) $P_{\mathbf{i},\mathbf{j},\mathbf{k}}\stackrel{{\scriptstyle
n\to+\infty}}{{\sim}}2^{t}\,(2n)^{-r-s-2t}.$

We now want to estimate the number $\mathcal{N}_{n}(r,s,t)$ of nice terms. Let
us remark that if we take $i_{1},\dots,i_{r}$ and $j_{1},\dots,j_{s}$
uniformly in $[2n]$, and $(k_{1},\ell_{1})$, …, $(k_{t},\ell_{t})$ uniformly
in $[2n]^{2}$ conditioned to satisfying $k_{\gamma}<\ell_{\gamma}$, all
independent to each other, then $\mathbf{i},\mathbf{j},\mathbf{k}$ is the
index of a nice term with probability tending to $1$ as $n$ tends to
$+\infty$. Indeed, a fixed number (here $r+s+2t$) of uniform integers in
$[2n]$ contains neither repetitions, nor adjacent points with probability
tending to $1$. Hence, as $n$ tends to $+\infty$, we have

$\mathcal{N}_{n}(r,s,t)\sim(2n)^{r}(2n)^{s}\binom{2n}{2}^{t}\sim
2^{-t}\,(2n)^{r+s+2t}.$

We conclude that the total contribution of nice terms to the sum in Eq. 20
tends to $1$.

We now prove that the total contribution of painful terms is asymptotically
negligible. With a triple of lists $(\mathbf{i},\mathbf{j},\mathbf{k})$ as
above, we associate a graph $G_{\mathbf{i},\mathbf{j},\mathbf{k}}$ encoding
coincidences as follows.

  * •

Its vertex set is

$\\{a_{\alpha},\alpha\leq r\\}\cup\\{b_{\beta},\beta\leq
s\\}\cup\\{c_{\gamma},\gamma\leq t\\}\cup\\{d_{\gamma},\gamma\leq t\\}.$

Each $a_{\alpha}$ (resp. $b_{\beta}$, $c_{\gamma}$, $d_{\gamma}$) is a formal
symbol representing the set $\\{i_{\alpha},i_{\alpha}+1\\}$ (resp. the set
$\\{j_{\beta},j_{\beta}+2\\}$, $\\{k_{\gamma},k_{\gamma}+1\\}$,
$\\{\ell_{\gamma},\ell_{\gamma}+1\\}$).

  * •

There is an edge between two vertices when the corresponding sets have a
nonempty intersection.

Nice terms are those for which $G_{\mathbf{i},\mathbf{j},\mathbf{k}}$ is the
empty graph. For a nonempty graph $G$, let us denote by $\mathcal{N}_{n}^{G}$
the number of triples $(\mathbf{i},\mathbf{j},\mathbf{k})$ with
$G_{\mathbf{i},\mathbf{j},\mathbf{k}}=G$. We have

$\mathcal{N}_{n}^{G}=\mathcal{O}\big{(}n^{\operatorname{cc}(G)}\big{)},$

where $\operatorname{cc}(G)$ is the number of connected components of $G$.
Indeed, one can choose freely the value of $i_{\alpha}$ (or $j_{\beta}$,
$k_{\gamma}$, $\ell_{\gamma}$) for one vertex in each connected component of
$G$. Then there are only finitely many choices for the value of $i_{\alpha}$
(or $j_{\beta}$, $k_{\gamma}$, $\ell_{\gamma}$) for other vertices in the same
component.

We now discuss the value of $P_{\mathbf{i},\mathbf{j},\mathbf{k}}$. In some
cases, _e.g._ if
$\\{i_{\alpha},i_{\alpha}+1\\}\cap\\{j_{\beta},j_{\beta}+2\\}\neq\emptyset$
for some $\alpha,\beta$, the conditions in the definition of
$P_{\mathbf{i},\mathbf{j},\mathbf{k}}$ are incompatible and
$P_{\mathbf{i},\mathbf{j},\mathbf{k}}=0$. Otherwise the conditions define a
configuration of chords that the random matching $M_{n}$ should contain (or
more precisely $M_{n}$ should contain a configuration among a finite number of
possible ones, as for each $\gamma$, one can choose whether $k_{\gamma}$ is
connected to $\ell_{\gamma}$ and $k_{\gamma}+1$ to $\ell_{\gamma}+1$ or
conversely). With a similar reasoning as in Eq. 21, we have