# Homogeneous actions on the Random Graph

Pierre Fima, Soyoung Moon, Yves Stalder

► To cite this version:

Pierre Fima, Soyoung Moon, Yves Stalder. Homogeneous actions on the Random Graph. Groups, Geometry, and Dynamics, 2021, 15 (1), pp.1-34. 10.4171/GGD/589. hal-01902444v2

HAL Id: hal-01902444

https://hal.science/hal-01902444v2

Submitted on 25 May 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# HOMOGENEOUS ACTIONS ON THE RANDOM GRAPH

PIERRE FIMA, SOYOUNG MOON, AND YVES STALDER

**ABSTRACT.** We show that any free product of two (non-trivial) countable groups, one of them being infinite, admits a faithful and homogeneous action on the Random Graph. We also show that a large class of HNN extensions or free products, amalgamated over a finite group, admit such an action and we extend our results to groups acting on trees. Finally, we show the ubiquity of finitely generated free dense subgroups of the automorphism group of the Random Graph whose action on it have all orbits infinite.

## INTRODUCTION

The *Random Graph* (or *Rado graph* or *Erdős-Rényi graph*) is the unique, up to isomorphism, countable infinite graph $\mathcal{R}$ having the following property : for any pair of disjoint finite subsets $(U, V)$ of the set of vertices there exists a vertex adjacent to any vertex in $U$ and not adjacent to any vertex in $V$. Using this property and a model theoretic device called “back-and-forth” one can show that $\mathcal{R}$ is *homogeneous* : any graph isomorphism between finite induced subgraphs can be extended to a graph automorphism of $\mathcal{R}$. Hence, the Random Graph plays the same role in graph theory as the Uryshon’s space does in metric spaces.

The Random Graph has been popularized by Erdős and Rényi in a serie of papers between 1959 and 1968. They showed [ER63] that if a countable graph is chosen at random, by selecting edges independently with probability $\frac{1}{2}$ from the set of 2-elements subsets of the vertex set, then almost surely the resulting graph is isomorphic to $\mathcal{R}$. Erdős and Rényi conclude that this Theorem demolishes the theory of infinite random graphs (however, the world of finite random graphs is much less predictable).

Since almost all countable graphs are isomorphic to $\mathcal{R}$, Erdős and Renyi did not give an explicit construction of the Random Graph. However, by using the uniqueness property of $\mathcal{R}$, it is clear that one may give many different explicit constructions. Such an explicit description was proposed by Rado [Ra64]. The uniqueness property of $\mathcal{R}$ may also be used to show many stability properties (if small changes are made on $\mathcal{R}$ then the resulting graph is still isomorphic to $\mathcal{R}$) and to construct many automorphisms of $\mathcal{R}$ as well as group actions on $\mathcal{R}$.

The homogeneity of $\mathcal{R}$ means that its automorphism group Aut($\mathcal{R}$) is large: it acts transitively on vertices, edges and more generally on finite configurations of any given isomorphism type. We will view it as a closed subset of the Polish group (for the topology of pointwise convergence) of the bijections of the vertices. Hence, it has a natural Polish group topology.

The goal of this paper is to understand the countable dense subgroups of Aut($\mathcal{R}$). The first construction of such subgroups was given in [Mac86], where Macpherson showed that Aut($\mathcal{R}$)

<footnote n="2010">2010 *Mathematics Subject Classification*. 20B22 (Primary); 20E06, 20E05, 05C63, 54E52 (Secondary).

*Key words and phrases*. Homogeneous actions, Random graph, free groups, groups acting on trees, Baire category Theorem.</footnote>

<footnote>This research has been partially supported by the ANR Blanc ANR-14-CE25-0004, acronym GAMME.</footnote>
contains a dense free subgroup on 2 generators. More generally, he showed that if $M$ is a $\aleph_0$-categorical structure, then Aut($M$) has a dense free subgroup of rank $\aleph_0$. Melles and Shelah [MS94] proved that, if $M$ is a saturated model of a complete theory $T$ with $|M| = \lambda > |T|$, then Aut($M$) has a dense free subgroup of cardinality $2^\lambda$. By using the extension property for graphs, Bhattacharjee and Macpherson showed in [BM05] that Aut($\mathcal{R}$) has a dense locally finite subgroup.

We call a group action $\Gamma \curvearrowright \mathcal{R}$ *homogeneous* if, for any graph isomorphism $\varphi : U \to V$ between finite induced subgraphs $U, V$ of $\mathcal{R}$, there exists $g \in \Gamma$ such that $g(u) = \varphi(u)$ for all $u \in U$. The homogeneity of $\mathcal{R}$ means exactly that Aut($\mathcal{R}$) $\curvearrowright \mathcal{R}$ is homogeneous. Moreover, it is easy to check that a subgroup $G < \text{Aut}(\mathcal{R})$ is dense if and only if the action $G \curvearrowright \mathcal{R}$ is homogeneous.

Hence, to understand the countable dense subgroups of Aut($\mathcal{R}$) one has to identify the class $\mathcal{H}_\mathcal{R}$ of all countable groups that admit a faithful and homogeneous action on $\mathcal{R}$. Besides free groups ([Mac86], [MS94], [GK03] and [GS15]) and a locally finite subgroup ([BM05]), little is known on groups in $\mathcal{H}_\mathcal{R}$. There are some obvious obstructions to be in the class $\mathcal{H}_\mathcal{R}$: it is easy to deduce from the simplicity of Aut($\mathcal{R}$), proved in [Tr85], that any $\Gamma \in \mathcal{H}_\mathcal{R}$ must be icc and not solvable (see Corollary 2.14). Our first positive result is the following. We shall use the notion of *highly core-free subgroups*, which is a strengthening of core-freeness, introduced in [FMS15] and recalled in Section 1.2. As an example, let us note that a finite subgroup in an icc group is highly core-free.

**Theorem A.** If $\Gamma_1, \Gamma_2$ are non-trivial countable groups and $\Gamma_1$ is infinite then $\Gamma_1 * \Gamma_2 \in \mathcal{H}_\mathcal{R}$. If $\Sigma < \Gamma_1, \Gamma_2$ is a common finite subgroup such that $\Sigma$ is highly core-free in $\Gamma_1$ and, either $\Gamma_2$ is infinite and $\Sigma$ is highly core-free in $\Gamma_2$, or $\Gamma_2$ is finite and $[\Gamma_2 : \Sigma] \ge 2$, then $\Gamma_1 *_{\Sigma} \Gamma_2 \in \mathcal{H}_\mathcal{R}$.

To prove Theorem A, we first show that any infinite countable group $\Gamma$ admits a “nice” action on $\mathcal{R}$ (Corollary 2.8). To produce this explicit action on $\mathcal{R}$ we use an inductive limit process. Then starting from an action of $\Gamma := \Gamma_1 * \Gamma_2 \curvearrowright \mathcal{R}$ and an automorphism $\alpha \in \text{Aut}(\mathcal{R})$, we construct a natural action $\pi_\alpha : \Gamma \curvearrowright \mathcal{R}$ and we show that the set $\{\alpha \in \text{Aut}(\mathcal{R}) : \pi_\alpha$ is faithful and homogeneous$\}$ is a dense $G_\delta$ in $\text{Aut}(\mathcal{R})$ whenever the initial action is “nice enough” (Theorem 3.1). We follow the same strategy for amalgamated free products but we need to be more careful since we also have to realize the amalgamated free product relations.

Using the same strategy, we prove an analogous result for HNN-extensions.

**Theorem B.** Let $H$ be an infinite countable group, $\Sigma < H$ a finite subgroup and $\theta : \Sigma \to H$ an injective group homomorphism. If both $\Sigma$ and $\theta(\Sigma)$ are highly core-free in $H$ then $\text{HNN}(H, \Sigma, \theta) \in \mathcal{H}_\mathcal{R}$.

By Bass-Serre theory we obtain the following result.

**Corollary C.** Let $\Gamma$ be a countable group acting, without inversion, on a non-trivial tree $\mathcal{T}$ in the sense of [Se77]. If every vertex stabilizer of $\mathcal{T}$ is infinite and, for every edge $e$ of $\mathcal{T}$ the stabilizer of $e$ is finite and is a highly core-free subgroup of both the stabilizer of the source of $e$ and the stabilizer of the range of $e$, then $\Gamma \in \mathcal{H}_\mathcal{R}$.

Finally, we study the ubiquity of dense free subgroups of Aut($\mathcal{R}$). Gartside and Knight [GK03] gave necessary and sufficient conditions for a Polish topological group to be “almost
free<fnref n="1" />”, and gave applications to permutation groups, profinite groups, Lie groups and unitary groups. In particular, they showed that if $M$ is $\aleph_0$-categorical then $\text{Aut}(M)$ is almost free. There are abundant results on the ubiquity of free subgroups in various classes of groups. In particular, almost freeness of various oligomorphic<fnref n="2" /> groups has been shown in [Dr85], [Ka92], [GMR93], [Ca96] and [GK03]. We prove the following result. For $k \ge 2$ and $\bar{\alpha} = (\alpha_1, \dots, \alpha_k) \in \text{Aut}(\mathcal{R})^k$, we denote by $\langle\bar{\alpha}\rangle$ the subgroup of $\text{Aut}(\mathcal{R})$ generated by $\alpha_1, \dots, \alpha_k$, and we set $\mathcal{A}_k := \{\bar{\alpha} \in \text{Aut}(\mathcal{R})^k : \langle\bar{\alpha}\rangle \frown \mathcal{R} \text{ has all orbits infinite}\}$. Since $\mathcal{A}_k$ is closed in $\text{Aut}(\mathcal{R})^k$, it is a Baire space.

**Theorem D.** For all $k \ge 2$, the set of $\bar{\alpha} = (\alpha_1, \dots, \alpha_k) \in \text{Aut}(\mathcal{R})^k$ such that $\langle\bar{\alpha}\rangle$ is a free group with basis $\bar{\alpha}$ and $\langle\bar{\alpha}\rangle \frown \mathcal{R}$ is homogeneous with all orbits infinite is a dense $G_\delta$ in $\mathcal{A}_k$.

To prove Theorem D we use the “back-and-forth” device (Theorem 6.6).

The paper is organized as follows. In Section 1 we introduce the notations used in the paper about graphs, random extensions and inductive limits. In Section 2 we introduce the Random Graph and we show how to extend any group action on a finite or countable graph to a group action on the Random Graph. We study the basic properties of the extension and the properties of groups acting homogeneously of $\mathcal{R}$. We prove Theorem A in Section 3, Theorem B in Section 4, Corollary C in Section 5 and Theorem D in Section 6.

## 1. PRELIMINARIES

1.1. **Graphs.** A Graph $\mathcal{G}$ is a pair $(V(\mathcal{G}), E(\mathcal{G}))$, where $V(\mathcal{G})$ is a set and $E(\mathcal{G}) \subset V(\mathcal{G})^2$ is a subset such that $E(\mathcal{G}) \cap \Delta = \emptyset$, where $\Delta = \{(u, u) \in V(\mathcal{G})^2 : u \in V(\mathcal{G})\}$, and $(u, v) \in E(\mathcal{G}) \Leftrightarrow (v, u) \in E(\mathcal{G})$. For $u, v \in V(\mathcal{G})$, we write $u \sim v$ if $(u, v) \in E(\mathcal{G})$.

Any subset $U \subset V(\mathcal{G})$ has a natural structure of a graph, called the *induced graph structure* on $U$ and denoted by $\mathcal{G}_U$, defined by $V(\mathcal{G}_U) = U$ and $E(\mathcal{G}_U) = E(\mathcal{G}) \cap (U \times U)$.

Let $\mathcal{G}_1, \mathcal{G}_2$ be two graphs. A *morphism of graphs* from $\mathcal{G}_1$ to $\mathcal{G}_2$ is a map $\pi : V(\mathcal{G}_1) \to V(\mathcal{G}_2)$ such that, for all $u, v \in V(\mathcal{G}_1)$, $u \sim v \implies \pi(u) \sim \pi(v)$. A morphism $\pi$ is called an *isomorphism* of graphs if $\pi$ is moreover bijective and its inverse $\pi^{-1} : V(\mathcal{G}_2) \to V(\mathcal{G}_1)$ is a morphism of graphs. A morphism of graphs $\pi : \mathcal{G}_1 \to \mathcal{G}_2$ is called *open* if

$$ \text{for all } u, v \in V(\mathcal{G}_1), u \sim v \Leftrightarrow \pi(u) \sim \pi(v). $$

Note that the inclusion $\iota$ of a subset $U \subset V(\mathcal{G})$ gives an open and injective graph homomorphism $\iota : \mathcal{G}_U \to \mathcal{G}$. Moreover, an injective graph homomorphism $\pi : \mathcal{G}_1 \to \mathcal{G}_2$ induces an isomorphism between $\mathcal{G}_1$ and the induced graph on $\pi(V(\mathcal{G}_1))$ if and only if $\pi$ is open.

A *partial isomorphism* of a graph $\mathcal{G}$ is an isomorphism between induced subgraphs of $\mathcal{G}$. For a partial isomorphism $\varphi$, we write $d(\varphi)$ its domain and $r(\varphi)$ its range. We denote by $P(\mathcal{G})$ the set of finite partial isomorphisms i.e. those partial isomorphism for which $d(\varphi)$ is finite (hence $r(\varphi)$ is also finite).

Given a countable graph $\mathcal{G}$, we write $\text{Aut}(\mathcal{G})$ the group of isomorphisms from $\mathcal{G}$ to $\mathcal{G}$. An action of a group $\Gamma$ on the graph $\mathcal{G}$ is a group homomorphism $\alpha : \Gamma \to \text{Aut}(\mathcal{G})$. We write

<footnote n="1">¹A Polish group $G$ is almost free if for all $n \ge 2$, the set $\{(g_1, \dots, g_n) \in G^n : g_1, \dots, g_n \text{ freely generates a free subgroup of } G\}$ is a dense $G_\delta$ in $G^n$.</footnote>

<footnote n="2">²A permutation group $G < S(X)$ is called *oligomorphic* if $G$ has only finitely many orbits on $X^n$ for every $n \in \mathbb{N}$.</footnote>
$\Gamma \curvearrowright \mathcal{G}$ for an action of $\Gamma$ on $\mathcal{G}$. Let $S(X)$ be the group of bijections of a countable set $X$. It is a Polish group under the topology of pointwise convergence. Note that $\mathrm{Aut}(\mathcal{G}) \subset S(V(\mathcal{G}))$ is a closed subgroup hence, $\mathrm{Aut}(\mathcal{G})$ is a Polish group.

## 1.2. Group actions.
The main purpose of this section is to introduce the *Random Extension* of a group action on a graph. This notion will be crucial to produce explicit actions on the Random Graph (Section 2.2). Many properties of an action are preserved by its Random Extension (Proposition 1.1). However, the freeness property is not preserved; except for actions of torsion-free groups. Nevertheless, a weaker-but still useful-property, that we call *strong faithfulness*, is preserved.

An action $\Gamma \curvearrowright X$ of a group $\Gamma$ on a set $X$ is called *strongly faithful* if, for all finite subsets $F \subset X$ with $X \setminus F \neq \emptyset$ one has $g(x) = x \ \forall x \notin F \implies g = 1$. When $X$ is finite, an action on $X$ is strongly faithful if and only if it is free. When $X$ is infinite, an action $\Gamma \curvearrowright X$ is strongly faithful if and only if for all $g \in \Gamma \setminus \{1\}$, the set $\{x \in X : gx \neq x\}$ is infinite. Note also that, for an action $\Gamma \curvearrowright X$ with $X$ infinite, one has: almost free (i.e. every non-trivial group element has finitely many fixed points) $\implies$ strongly faithful $\implies$ faithful.

An action $\Gamma \curvearrowright \mathcal{G}$ of a group $\Gamma$ on a graph $\mathcal{G}$ is called *homogeneous* if for all $\varphi \in P(\mathcal{G})$ (recall that $d(\varphi)$ and $r(\varphi)$ are supposed to be finite), there exists $g \in \Gamma$ such that $gu = \varphi(u)$ for all $u \in d(\varphi)$. It is easy to see that $\Gamma \curvearrowright \mathcal{G}$ is homogeneous if and only if the image of $\Gamma$ in $\mathrm{Aut}(\mathcal{G})$ is dense.

We say that $\Gamma \curvearrowright \mathcal{G}$ has *infinite orbits* (resp. is *free*, resp. is *strongly faithful*) if the action $\Gamma \curvearrowright V(\mathcal{G})$ on the set $V(\mathcal{G})$ has infinite orbits i.e. all orbits are infinite (resp. is free, resp. is strongly faithful).

We say that $\Gamma \curvearrowright \mathcal{G}$ disconnects the finite sets if for all finite subsets $F \subset V(\mathcal{G})$ there exists $g \in \Gamma$ such that $gF \cap F = \emptyset$ and, for all $u, v \in F$, $gu \approx v$. Note that if $\Gamma \curvearrowright \mathcal{G}$ disconnects the finite sets then it has infinite orbits and the converse holds when $E(\mathcal{G}) = \emptyset$.

We say that $\Gamma \curvearrowright \mathcal{G}$ is *non-singular* if for every $u \in V(\mathcal{G})$ and $g \in \Gamma$ we have $gu \approx u$.

The notion of a *highly core-free* subgroup $\Sigma < \Gamma$ has been introduced in [FMS15]: it is a strengthening of the notion of core-free subgroup. Recall that, given a nonempty subset $S \subset \Gamma$, the normal core of a subgroup $\Sigma < \Gamma$ relative to $S$ is defined by $\mathrm{Core}_S(\Sigma) = \cap_{h \in S} h^{-1}\Sigma h$. Then, $\Sigma$ is called *core-free* if $\mathrm{Core}_\Gamma(\Sigma) = \{1\}$. Now, $\Sigma$ is called *highly core-free* if, for every finite covering of $\Gamma$ with non-empty sets, up to finitely many $\Sigma$-classes, there exists at least one set in the covering for which the associated normal core is trivial. More precisely, it means that, for every finite subset $F \subset \Gamma$, for any $n \ge 1$, for any non-empty subsets $S_1, \dots, S_n \subset \Gamma$ such that $\Gamma - \Sigma F \subset \cup_{k=1}^n S_k$ there exists $1 \le k \le n$ such that $\mathrm{Core}_{S_k}(\Sigma) = \{1\}$. Many examples of highly core-free subgroups are given in [FMS15]. Let us mention some of them below.

* For any countable field $K$, any $d \ge 2$, the stabilizer in $\mathrm{PSL}_d(K)$ of any point in $\mathrm{P}^1(K^d)$ for the natural action $\mathrm{PSL}_d(K) \curvearrowright \mathrm{P}^1(K^d)$ is a highly core-free subgroup of $\mathrm{PSL}_d(K)$.

* Any finite subgroup of an *icc* group is highly core-free (a group is called *icc* if the conjugacy class of every non-trivial group element is infinite).

* A finite malnormal subgroup of an infinite group is highly core-free ($\Sigma < \Gamma$ is called *malnormal* if $\forall g \in \Gamma - \Sigma$ one has $\Sigma \cap g\Sigma g^{-1} = \{1\}$).
* If $\Lambda$ and $\Sigma$ are non trivial groups and $\Sigma$ is abelian then $\Sigma$ is highly core-free in $\Gamma = \Lambda * \Sigma$. More generally, an abelian malnormal subgroup of infinite index is highly core-free.

* For any infinite (commutative) field, $K^* < K^* \ltimes K$ is malnormal, in particular highly core-free by the previous example.

Let us finally note that being highly core-free is a strictly stronger property than being core-free. Indeed, let us denote by $S_\infty$ the group of finitely supported bijections of $\mathbb{N}$. Then, the stabilizer of any $n \in \mathbb{N}$ in $S_\infty$ is a core-free but not highly core-free subgroup of $S_\infty$.

The notion of a highly core-free subgroup $\Sigma < \Gamma$ with respect to an action $\Gamma \curvearrow X$ on the set $X$ has also been introduced in [FMS15]. It is defined in such a way that $\Sigma < \Gamma$ is highly core-free if and only if it is highly core-free with respect to the left translation action $\Gamma \curvearrow \Gamma$. We will use here a similar notion for an action $\Gamma \curvearrow G$ on a graph $G$. Let $\Sigma < \Gamma$ be a subgroup and $\Gamma \curvearrow G$ be an action on the graph $G$. We say that $\Sigma$ is highly core-free with respect to $\Gamma \curvearrow G$ if for every finite subset $F \subset V(G)$ there exists $g \in \Gamma$ such that $gF \cap \Sigma F = \emptyset$, $gu \sim v$ for all $u, v \in F$, $\Sigma gu \cap \Sigma gv = \emptyset$ for all $u, v \in F$ with $u \neq v$ and $\sigma gu \sim gv$ for all $u, v \in F$ and all $\sigma \in \Sigma \setminus \{1\}$. In practice, we will use the following equivalent definition (obtained by replacing $F$ by $F_1 \cup F_2$): for every finite subsets $F_1, F_2 \subset V(G)$ there exists $g \in \Gamma$ such that $gF_1 \cap \Sigma F_2 = \emptyset$, $gx \sim u$, $\sigma gx \sim gx'$ for all $u \in F_2, x, x' \in F_1, \sigma \in \Sigma \setminus \{1\}$ and $\Sigma gx \cap \Sigma gx' = \emptyset$ for all $x, x' \in F_1$ with $x \neq x'$.

It is clear that if $\Sigma$ is highly core-free w.r.t. $\Gamma \curvearrow G$ then the action $\Gamma \curvearrow G$ disconnects the finite sets. We adopt a terminology slightly different from [FMS15]: if $E(G) = \emptyset$ then $\Sigma$ is highly core-free with respect to the action $\Gamma \curvearrow G$ on the graph $G$ in the sense explained above if and only if $\Sigma$ is strongly highly core-free with respect to the action $\Gamma \curvearrow V(G)$ on the set $V(G)$ in the sense of [FMS15, Definition 1.7]. In particular, if $E(G) = \emptyset$ and $\Gamma \curvearrow G$ is free then $\Sigma$ is highly core-free with respect to $\Gamma \curvearrow G$ if and only if $\Sigma$ is highly-core free in $\Gamma$ (see [FMS15, Definition 1.1 and Lemma 1.6]. Note also that the trivial subgroup is highly core-free w.r.t. $\Gamma \curvearrow G$ if and only if the action $\Gamma \curvearrow G$ disconnects the finite sets and, if $\Sigma$ is highly core-free with respect to $\Gamma \curvearrow G$ then every subgroup of $\Sigma$ is highly core-free with respect to $\Gamma \curvearrow G$. In particular, if there exists a subgroup $\Sigma$ which is highly core-free with respect to $\Gamma \curvearrow G$ then the action $\Gamma \curvearrow G$ disconnects the finite sets.

In the sequel we always assume that $G$ is a non-empty graph. The Random Extension of $G$ is the graph $\tilde{G}$ defined by $V(\tilde{G}) = V(G) \sqcup \mathcal{P}_f(V(G))$, where $\mathcal{P}_f(X)$ denotes the set of non-empty finite subsets of a set $X$ and $\sqcup$ denotes the disjoint union, and:

$$E(\tilde{G}) = E(G) \sqcup (\sqcup_{U \in \mathcal{P}_f(V(G))} U \times \{U\}) \sqcup (\sqcup_{U \in \mathcal{P}_f(V(G))} \{U\} \times U)$$

i.e., given $a, b \in V(G)$ and $U, V \in \mathcal{P}_f(V(G))$ one has:

$$(a, b) \in E(\tilde{G}) \Leftrightarrow (a, b) \in E(G), \quad (U, V) \notin E(\tilde{G}), \quad (a, U) \in E(\tilde{G}) \Leftrightarrow (U, a) \in E(\tilde{G}) \Leftrightarrow a \in U.$$

Note that the inclusion $\iota: V(G) \to V(\tilde{G})$ defines an injective and open graph homomorphism $\iota: G \to \tilde{G}$.

Given an action $\Gamma \curvearrow G$ there is a natural action $\Gamma \curvearrow \tilde{G}$ for which the map $\iota$ is $\Gamma$-equivariant. Indeed, we take the original action of $\Gamma$ on $V(G) \subset V(\tilde{G})$ and, for $U \in \mathcal{P}_f(V(G)) \subset V(\tilde{G})$ and $g \in \Gamma$, we define the action of $g$ on $U$ by $g \cdot U := gU := \{gu : u \in U\} \in \mathcal{P}_f(V(G))$. This
defines an action of $\Gamma$ on $\tilde{\mathcal{G}}$ since for all $z \in V(\tilde{\mathcal{G}})$, $U \in P_f(V(\mathcal{G}))$ and all $g \in \Gamma$ we have
$$z \sim U \Leftrightarrow z \in U \Leftrightarrow gz \in gU \Leftrightarrow g \cdot z \sim g \cdot U.$$

It is clear that $\iota$ is $\Gamma$-equivariant.

**Proposition 1.1.** The following holds.

(1) $\Gamma \curvearrowright \tilde{\mathcal{G}}$ is faithful if and only if $\Gamma \curvearrowright \mathcal{G}$ is faithful.

(2) $\Gamma \curvearrowright \tilde{\mathcal{G}}$ is non-singular if and only if $\Gamma \curvearrowright \mathcal{G}$ is non-singular.

(3) $\Gamma \curvearrowright \tilde{\mathcal{G}}$ has infinite orbits if and only if $\Gamma \curvearrowright \mathcal{G}$ has infinite orbits.

(4) $\Gamma \curvearrowright \tilde{\mathcal{G}}$ disconnects the finite sets if and only if $\Gamma \curvearrowright \mathcal{G}$ disconnects the finite sets.

(5) If $\Gamma$ is torsion-free, $\mathcal{G}$ is infinite and $\Gamma \curvearrowright \mathcal{G}$ is free then $\Gamma \curvearrowright \tilde{\mathcal{G}}$ is free. If $\Gamma$ has torsion then $\Gamma \curvearrowright \tilde{\mathcal{G}}$ is not free.

(6) If $\Gamma \curvearrowright \mathcal{G}$ is strongly faithful and $\mathcal{G}$ is infinite then $\Gamma \curvearrowright \tilde{\mathcal{G}}$ is strongly faithful.

(7) Let $\Sigma < \Gamma$ be a subgroup. $\Sigma$ is highly core-free w.r.t. $\Gamma \curvearrowright \mathcal{G}$ if and only if it is highly core-free w.r.t. $\Gamma \curvearrowright \tilde{\mathcal{G}}$.

*Proof.* (1) and (2) are obvious.

(3). Suppose that $\Gamma \curvearrowright \mathcal{G}$ has infinite orbits. Since $\iota$ is equivariant, it suffices to check that the orbit of any $U \in P_f(V(\mathcal{G}))$ is infinite. Suppose that there is $U \in P_f(V(\mathcal{G}))$ with a finite orbit. Then there exists $g_1, \dots, g_n \in \Gamma$ such that for all $g \in \Gamma$ there exists $i \in \{1, \dots, n\}$ such that $gU = g_iU$. Hence $\cup_{g \in \Gamma} gU$ is a finite set since $\cup_{g \in \Gamma} gU \subset \cup_{i=1}^n g_iU$. However, since $U \neq \emptyset$, there exists $x \in U$ and $\Gamma x \subset \cup_{g \in \Gamma} gU$ is infinite, a contradiction. The converse is obvious.

(4). Suppose that $\Gamma \curvearrowright \mathcal{G}$ disconnects the finite sets. Let $F \subset V(\tilde{\mathcal{G}})$ be a finite set and write $F = F_1 \sqcup F_2$, where $F_1 = F \cap V(\mathcal{G})$ and $F_2 = F \cap \mathcal{P}_f(V(\mathcal{G}))$. Define the finite subset $\tilde{F} = F_1 \cup (\cup_{U \in F_2} U) \subset V(\mathcal{G})$. Since $\Gamma \curvearrowright \mathcal{G}$ disconnects the finite sets there exists $g \in \Gamma$ such that $g\tilde{F} \cap \tilde{F} = \emptyset$ and, for all $u, v \in \tilde{F}$, $u \not\sim gv$. It follows $gF_1 \cap F_1 = \emptyset$ and for all $u, v \in F_1$, $gu \not\sim v$. Moreover, for all $U, V \in F_2$, $gU \cap V = \emptyset$ hence $gU \neq V$ so $gF_2 \cap F_2 = \emptyset$. Obvisouly $gF_1 \cap F_2 = \emptyset$ and, since $gF_1 \cap U = \emptyset$ for all $U \in F_2$ we find that $gu \not\sim U$ for all $u \in F_1$ and all $U \in F_2$. Hence $gF \cap F = \emptyset$ and for all $u, v \in F$, $gu \not\sim v$. This shows that $\Gamma \curvearrowright \tilde{\mathcal{G}}$ disconnects the finite sets. The converse is obvious.

(5). Suppose $\Gamma \curvearrowright \mathcal{G}$ is free and $\Gamma \curvearrowright \tilde{\mathcal{G}}$ is not free. Then, there exists $U \in P_f(V(\mathcal{G}))$ and $g \in \Gamma - \{1\}$ such that $gU = U$. Then $g^nU = U$ for all $n \ge 0$. Since $U \neq \emptyset$ there exists $x \in U$ and the set $\{g^n x : n \ge 0\}$ is finite since it is a subset of $U$. Hence, there exists $n \ge 1$ such that $g^n x = x$. Since $\Gamma \curvearrowright \mathcal{G}$ is free we have $g^n = 1$ and $\Gamma$ is not torsion free. Suppose now that $\Gamma$ has torsion. Let $g \in \Gamma$, $g \neq 1$, such that $\langle g \rangle$ is a finite subgroup of $\Gamma$. Let $u \in V(\mathcal{G})$. The set $F = \langle g \rangle u \subset V(\mathcal{G})$ is finite and $gF = F$ hence $\Gamma \curvearrowright \tilde{\mathcal{G}}$ is not free.

(6). Let $F \subset V(\tilde{\mathcal{G}})$ be a finite subset and $g \in \Gamma$ such that $g(x) = x$ for all $x \notin F$. Define $\tilde{F} = F \cap V(\mathcal{G})$, which is a finite subset of $V(\mathcal{G})$. Since $V(\mathcal{G}) - \tilde{F} \subset V(\tilde{\mathcal{G}}) - F$ we have $g(x) = x$ for all $x \in V(\mathcal{G}) - \tilde{F}$. Since $\Gamma \curvearrowright \mathcal{G}$ is strongly faithful it follows that $g = 1$.

(7). Suppose that $\Sigma$ is highly core-free w.r.t. $\Gamma \curvearrowright \mathcal{G}$. Let $F \subset V(\tilde{\mathcal{G}})$ be a finite set and write $F = F_1 \sqcup F_2$, where $F_1 = F \cap V(\mathcal{G})$ and $F_2 = F \cap \mathcal{P}_f(V(\mathcal{G}))$. Define the finite subset $\tilde{F} = F_1 \cup (\cup_{U \in F_2} U) \subset V(\mathcal{G})$. Since $\Sigma$ is highly core-free w.r.t. $\Gamma \curvearrowright \mathcal{G}$ there exists $g \in \Gamma$ such that $g\tilde{F} \cap \Sigma\tilde{F} = \emptyset$, $u \not\sim gv$ for all $u, v \in \tilde{F}$, $\Sigma gu \cap \Sigma gv = \emptyset$ for all $u, v \in \tilde{F}$ with $u \neq v$ and $\sigma gu \not\sim gv$ for all $u, v \in \tilde{F}$ and all $\sigma \in \Sigma \setminus \{1\}$. Obviously, $gF \cap \Sigma F = \emptyset$ and for all $u, v \in F$,
$gu \not\sim v$. Let us show that $\Sigma gu \cap \Sigma gv = \emptyset$ for all $u, v \in F$ with $u \neq v$. If both $u, v$ are in $F_1$ or if ($u \in F_1$ and $v \in F_2$) or ($v \in F_2$ and $u \in F_1$) this is obvious. So assume that $U, V \in F_2$. We need to show that $\Sigma gU = \Sigma gv \implies U = V$. We know that for all $u \in U$ and all $v \in V$ we have $u \neq v \implies \Sigma gu \cap \Sigma gv = \emptyset$. Hence, if there exists $x \in \Sigma gU \cap \Sigma gv$ then we find $\sigma, \sigma' \in \Sigma$ such that $\sigma gU = \sigma'gv$. It follows that if $u \in U$ then there exists $v \in V$ such that $\sigma gu = \sigma'gv$ hence, $\Sigma gu = \Sigma gv$ so we must have $u = v \in V$. Hence, $U \subset V$. Similarly, $V \subset U$ so that $U = V$. It remains to show that $\sigma gu \not\sim gv$ for all $u, v \in F$ and $\sigma \in \Sigma \setminus \{1\}$. For $\sigma \in \Sigma \setminus \{1\}$ it is clear that $\sigma gu \not\sim gv$ for all $u, v \in F_2$ and also for all $u, v \in F_1$. Let $u \in F_1$ and $V \in F_2$. If $\sigma \in \Sigma$ is such that $\sigma gu \sim gv$ then there exists $v \in V \subset \tilde{F}$ such that $\sigma gu = gv$. Hence $\Sigma gu = \Sigma gv$ which implies that $u = v$. It follows that $\sigma = 1$. The converse is obvious. $\square$

**1.3. Inductive limits.** Let $X_n$ be a sequence of countable sets with injective maps $\iota_n : X_n \to X_{n+1}$. Let $l \ge n$. Define the injective map $\iota_{l,n} : X_n \to X_l$ by $\iota_{l,n} = \iota_{l-1} \circ \cdots \circ \iota_n$ if $l > n$, and $\iota_{n,n} = \text{id}$. Observe that for all $n \le m \le l$, $\iota_{l,m} \circ \iota_{m,n} = \iota_{l,n}$. Let $X_\infty$ be the inductive limit i.e. $X_\infty = \coprod X_n / \sim$, where $x \sim y$ if and only if there exists $n, m \in \mathbb{N}$ and $l \ge n, m$ such that $x \in X_n, y \in X_m$ and $\iota_{l,n}(x) = \iota_{l,m}(y)$. Observe that we have injections $\iota_{\infty,n} : X_n \to X_\infty$, $\iota_{\infty,n}(x) = [x]$, where $[x]$ denotes the class of the element $x \in X_n \subset \coprod_n X_n$ for the equivalence relation described above. Those injections satisfy $X_\infty = \bigcup_n^\uparrow \iota_{\infty,n}(X_n)$ and $\iota_{\infty,n+1} \circ \iota_n = \iota_{\infty,n}$ for all $n \in \mathbb{N}$. Actually $X_\infty$ is the unique set, up to a canonical bijection, such that there exists injections $\iota_{\infty,n} : X_n \to X_\infty$ satisfying $X_\infty = \bigcup_n^\uparrow \iota_{\infty,n}(X_n)$ and $\iota_{\infty,n+1} \circ \iota_n = \iota_n$ for all $n \in \mathbb{N}$. Note that $X_\infty$ is at most countable. Actually, it is finite if and only if for all $n \in \mathbb{N}$, $X_n$ is finite and there exists $l \in \mathbb{N}$ such that $\iota_k(X_k) = X_{k+1}$ for all $k \ge l$.

Given a sequence of actions $\pi_n : \Gamma \to S(X_n)$ of a group $\Gamma$ on the set $X_n$ satisfying $\pi_{n+1}(g) \circ \iota_n = \iota_n \circ \pi_n(g)$ for all $n \in \mathbb{N}$ and $g \in \Gamma$, we define the inductive limit action $\pi_\infty : \Gamma \to S(X_\infty)$ by $\pi_\infty(g) \circ \iota_{\infty,n} = \iota_{\infty,n} \circ \pi_n(g)$ for all $n \in \mathbb{N}$. The next proposition contains some standard observations on inductive limits. Since this results are well known and very easy to check, we omit the proof.

**Proposition 1.2.** *The following holds.*

(1) If there exists $n \in \mathbb{N}$ such that $\Gamma \curvearrow X_n$ is faithful then $\Gamma \curvearrow X_\infty$ is faithful.

(2) $\Gamma \curvearrow X_\infty$ is free if and only if $\Gamma \curvearrow X_n$ is free for all $n \in \mathbb{N}$.

(3) If $\Gamma \curvearrow X_n$ is strongly faithful for all $n \in \mathbb{N}$ then $\Gamma \curvearrow X_\infty$ is strongly faithful.

(4) $\Gamma \curvearrow X_\infty$ has infinite orbits if and only if $\Gamma \curvearrow X_n$ has infinite orbits for all $n \in \mathbb{N}$.

Let $\mathcal{G}_n$ be a sequence of countable graphs with injective graphs homomorphisms $\iota_n : \mathcal{G}_n \to \mathcal{G}_{n+1}$. We define the inductive limit graph $\mathcal{G}_\infty$ by defining $V(\mathcal{G}_\infty) = \bigcup^\uparrow \iota_{\infty,n}(V(\mathcal{G}_n))$ as the inductive limit of the $V(\mathcal{G}_n)$ with respect to the maps $\iota_n$ and $E(\mathcal{G}_\infty)$ is the set of couples $(u, v) \in V(\mathcal{G}_\infty)^2$ for which there exists $k \ge n, m$ with $u = \iota_{\infty,n}(u_0), u_0 \in V(\mathcal{G}_n), v = \iota_{\infty,m}(v_0), v_0 \in V(\mathcal{G}_m)$ and $(\iota_{k,n}(u_0), \iota_{k,m}(v_0)) \in E(\mathcal{G}_k)$. We collect elementary observations on the inductive limit graph in the following proposition.

**Proposition 1.3.** *The following holds.*

(1) $\iota_{\infty,n}$ is a graph homomorphism for all $n \in \mathbb{N}$.

(2) If $\iota_n$ is open for all $n \in \mathbb{N}$ then $\iota_{\infty,n}$ is open for all $n \in \mathbb{N}$.

(3) If $\Gamma \curvearrow \mathcal{G}_\infty$ disconnects the finite sets then $\Gamma \curvearrow \mathcal{G}_n$ disconnects the finite sets for all $n \in \mathbb{N}$. The converse holds when $\iota_n$ is open for all $n \in \mathbb{N}$.
(4) If $\Gamma \curvearrowright \mathcal{G}_\infty$ is non-singular then $\Gamma \curvearrowright \mathcal{G}_n$ is non-singular for all $n \in \mathbb{N}$. The converse holds when $\iota_n$ is open for all $n \in \mathbb{N}$.

(5) Let $\Sigma < \Gamma$ be a subgroup. If $\Sigma$ is highly core-free w.r.t. $\Gamma \curvearrowright \mathcal{G}_\infty$ then $\Sigma$ is highly core-free w.r.t. $\Gamma \curvearrowright \mathcal{G}_n$ for all $n$. The converse holds when $\iota_n$ is open for all $n$.

*Proof.* (1) is obvious.

(2). Suppose that $\iota_n$ is open for all $n \in \mathbb{N}$ and let $u, v \in V(\mathcal{G}_n)$ such that $\iota_{\infty,n}(u) \sim \iota_{\infty,n}(v)$. Then, there exists $k \ge 0$ such that $(\iota_{k+n,n}(u), \iota_{k+n,n}(v)) \in E(\mathcal{G}_{k+n})$ and a proof by induction on $k \ge 0$ shows that $(u, v) \in E(\mathcal{G}_n)$.

(3). Suppose that $\Gamma \curvearrowright \mathcal{G}_\infty$ disconnects the finite sets and let $n \in \mathbb{N}$ and $F \subset V(\mathcal{G}_n)$ be a finite subset. Let $F' = \iota_{\infty,n}(F) \subset V(\mathcal{G}_\infty)$ and take $g \in \Gamma$ such that $gF' \cap F' = \emptyset$ and $gu' \sim v'$ for all $u', v' \in F'$. It follows that $gF \cap F = \emptyset$ and $\iota_{\infty,n}(gu) \sim \iota_{\infty,n}(v)$ for all $u, v \in F$. By (1) we have $gu \sim v$ for all $u, v \in F$. Suppose now that $\iota_n$ is open and $\Gamma \curvearrowright \mathcal{G}_n$ disconnects the finite sets for all $n \in \mathbb{N}$. Let $F \subset V(\mathcal{G}_\infty)$ be a finite set and take $n \in \mathbb{N}$ large enough so that $F = \iota_{\infty,n}(F')$, where $F' \subset V(\mathcal{G}_n)$ is a finite set. Take $g \in \Gamma$ such that $gF' \cap F' = \emptyset$ and $gu' \sim v'$ for all $u', v' \in F'$. Since $\iota_{\infty,n}$ injective we have $gF \cap F = \emptyset$ and since $\iota_{\infty,n}$ is open (by (2)) we have $gu \sim v$ for all $u, v \in F$.

(4). Suppose that $\Gamma \curvearrowright \mathcal{G}_\infty$ is non-singular and let $n \in \mathbb{N}$, $u \in V(\mathcal{G}_n)$ and $g \in \Gamma$. Then $\iota_{\infty,n}(gu) = g\iota_{\infty,n}(u) \sim \iota_{\infty,n}(u)$ which implies that $gu \sim u$ since $\iota_{\infty,n}$ is a graph homomorphism. Suppose now that $\iota_n$ is open and $\Gamma \curvearrowright \mathcal{G}_n$ is non-singular for all $n \in \mathbb{N}$. Let $u \in V(\mathcal{G}_\infty)$ and $g \in \Gamma$. Let $n \in \mathbb{N}$ large enough so that $u = \iota_{\infty,n}(u')$, where $u' \in V(\mathcal{G}_n)$. Then $gu' \sim u'$ implies that $gu = \iota_{\infty,n}(gu') \sim \iota_{\infty,n}(u') = u$ since $\iota_{\infty,n}$ is open.

(5). Suppose that $\Sigma$ is highly core-free with respect to $\Gamma \curvearrowright \mathcal{G}_\infty$ and let $n \in \mathbb{N}$ and $F \subset V(\mathcal{G}_n)$ be a finite subset. Let $F' = \iota_{\infty,n}(F) \subset V(\mathcal{G}_\infty)$ and take $g \in \Gamma$ such that $gF' \cap \Sigma F' = \emptyset$, $gu' \sim v'$ for all $u', v' \in F'$, $\Sigma gu' \cap \Sigma gv' = \emptyset$ for all $u', v' \in F'$ with $u' \ne v'$ and $\sigma gu' \sim gv'$ for all $u', v' \in F'$ and all $\sigma \in \Sigma \setminus \{1\}$. It follows that $gF \cap \Sigma F = \emptyset$ and $\Sigma gu \cap \Sigma gv = \emptyset$ for all $u, v \in F$ with $u \ne v$. Moreover, $\iota_{\infty,n}(gu) \sim \iota_{\infty,n}(v)$ and $\iota_{\infty,n}(\sigma gu) \sim \iota_{\infty,n}(gv)$ for all $u, v \in F$ and all $\sigma \in \Sigma \setminus \{1\}$. Suppose now that $\iota_n$ is open and $\Sigma$ is highly core-free w.r.t. $\Gamma \curvearrowright \mathcal{G}_n$ for all $n \in \mathbb{N}$. Let $F \subset V(\mathcal{G}_\infty)$ be a finite set and take $n \in \mathbb{N}$ large enough so that $F = \iota_{\infty,n}(F')$, where $F' \subset V(\mathcal{G}_n)$ is a finite set. Take $g \in \Gamma$ such that $gF' \cap \Sigma F' = \emptyset$, $gu' \sim v'$ and $\sigma gu' \sim gv'$ for all $u', v' \in F'$ and all $\sigma \in \Sigma \setminus \{1\}$ and $\Sigma gu' \cap \Sigma gv' = \emptyset$ for all $u', v' \in F'$ with $u' \ne v'$. Since $\iota_{\infty,n}$ injective we have $gF \cap \Sigma F = \emptyset$ and $\Sigma gu \cap \Sigma gv = \emptyset$ for all $u, v \in F$ with $u \ne v$. Moreover, since $\iota_{\infty,n}$ is open (by (2)) we have $gu \sim v$ and $\sigma gu \sim gv$ for all $u, v \in F$ and all $\sigma \in \Sigma \setminus \{1\}$. $\square$

## 2. THE RANDOM GRAPH

2.1. **Definition of the Random Graph.** Given a graph $\mathcal{G}$ and subsets $U, V \subset V(\mathcal{G})$ we define $\mathcal{G}_{U,V}$ as the induced subgraph on the subsets of vertices

$$V(\mathcal{G}_{U,V}) := \{z \in V(\mathcal{G}) \setminus (U \cup V) : z \sim u, \forall u \in U \text{ and } z \sim v, \forall v \in V\}.$$

Note that $V(\mathcal{G}_{U,V})$ may be empty for some subsets $U$ and $V$. To ease the notations we will denote by the same symbol $\mathcal{G}_{U,V}$ the induced graph on $V(\mathcal{G}_{U,V})$ and the set of vertices $V(\mathcal{G}_{U,V})$.
**Definition 2.1.** We say that a graph $\mathcal{G}$ has property (R) if, for any disjoint finite subsets $U, V \subset V(\mathcal{G})$, $\mathcal{G}_{U,V} \neq \emptyset$.

Note that a graph with property (R) is necessarily infinite. We recall the following well-known result (See e.g. [Ca97] or [Ca99]) that will be generalized later (Proposition 2.5).

**Proposition 2.2.** Let $\mathcal{G}_1, \mathcal{G}_2$ be two infinite countable graphs with property (R) and $A \subset V(\mathcal{G}_1)$, $B \subset V(\mathcal{G}_2)$ be finite subsets. Any isomorphism between the induced graphs $\varphi : (\mathcal{G}_1)_A \to (\mathcal{G}_2)_B$ extends to an isomorphism $\bar{\varphi} : \mathcal{G}_1 \to \mathcal{G}_2$.

There are many ways to construct a countable graph with property (R). Proposition 2.2 shows that a countable graph with property (R) is unique, up to isomorphism. Such a graph is denoted by $\mathcal{R}$ and called the Random Graph. Given an infinite countable set $V$ of vertices, Erdős and Rényi proved [ER63] that putting (independently) an edge between any pair $\{u, v\}$ of vertices with probability $1/2$, the resulting graph will have property (R) with probability 1. This result motivates the name Random Graph.

Proposition 2.2 also implies that every $\varphi \in P(\mathcal{R})$ admits an extension $\bar{\varphi} \in \mathrm{Aut}(\mathcal{R})$ (i.e. $\bar{\varphi}|_{d(\varphi)} = \varphi$). Proposition 2.2 is also useful to show stability properties of the graph $\mathcal{R}$ as done in the next Proposition.

**Proposition 2.3.** The following holds.

(1) For every finite subset $A \subset V(\mathcal{R})$, the induced subgraph $\mathcal{R}_{V(\mathcal{R})\setminus A}$ on $V(\mathcal{R}) \setminus A$ is isomorphic to $\mathcal{R}$.

(2) For all finite and disjoint $U, V \subset V(\mathcal{R})$, the graph $\mathcal{R}_{U,V}$ is isomorphic to $\mathcal{R}$.

(3) For every non-empty countable graph $\mathcal{G}$, the inductive limit $\mathcal{G}_\infty$ of the sequence $\mathcal{G}_0 = \mathcal{G}$ and $\mathcal{G}_{n+1} = \tilde{\mathcal{G}}_n$ (with $\iota_n : \mathcal{G}_n \to \mathcal{G}_{n+1}$ the inclusion) is isomorphic to $\mathcal{R}$. In particular, every countable graph is isomorphic to an induced subgraph of $\mathcal{R}$.

*Proof.* (1). Let $U, V \subset V(\mathcal{R}) \setminus A$ be disjoint finite subsets. Apply property (R) with the disjoint finite subsets $U' = U \sqcup A, V \subset V(\mathcal{R})$ and get $z \in V(\mathcal{R}) \setminus (U' \cup V) = (V(\mathcal{R}) \setminus A) \setminus (U \cup V)$ such that $z \sim u$ for all $u \in U$ and $z \asymp v$ for all $v \in V$. Hence the countable graph induced on $V(\mathcal{R}) \setminus A$ has property (R).

(2). Since $\mathcal{R}_{U,V}$ is at most countable, it suffices to check that $\mathcal{R}_{U,V}$ has property (R) and it is left to the reader.

(3). Since $\mathcal{G}$ is either finite and non-empty or infinite countable, the inductive limit is infinite countable and it suffices to check that it has property (R). Since $\iota_n$ is open for all $n \in \mathbb{N}$ it follows from Proposition 1.3 that we may and will assume that $\iota_{\infty,n} = \mathrm{id}$ and $(\mathcal{G}_n)_n$ is an increasing sequence of induced subgraphs of $\mathcal{G}_\infty$ such that $\mathcal{G}_\infty = \bigcup^\uparrow \mathcal{G}_n$. Let $U, V$ be two finite and disjoint subsets of the inductive limit. Let $n$ large enough so that $U, V \subsetneq V(\mathcal{G}_n)$. If $U \neq \emptyset$, we consider the element $z = U \in P_f(V(\mathcal{G}_n)) \subset V(\mathcal{G}_{n+1}) \subset V(\mathcal{G}_\infty)$ and if $U = \emptyset$, we consider any element $z = \{x\} \in P_f(V(\mathcal{G}_n)) \subset V(\mathcal{G}_{n+1}) \subset V(\mathcal{G}_\infty)$ for $x \in V(\mathcal{G}_n) \setminus V$. Then, by definition of the Random extension, we have, for all $u \in U$, $(u, z) \in E(\mathcal{G}_{n+1})$ and, for all $v \in V$, $(v, z) \notin E(\mathcal{G}_{n+1})$. Since $\mathcal{G}_{n+1}$ is the induced subgraph on $V(\mathcal{G}_{n+1})$ we have $z \in (\mathcal{G}_\infty)_{U,V}$. The last assertion also follows from Proposition 1.3 since the inclusion of $\mathcal{G}_0 = \mathcal{G}$ in the inductive limit is open. $\square$

**Remark 2.4.** The construction of Proposition 2.3, assertions (3), shows the existence of $\mathcal{R}$. This construction may also be performed starting with any countable graph $\mathcal{G}$, even $\mathcal{G} = \emptyset$,
and replacing, in the construction of the Random Extension, $\mathcal{P}_f(X)$ by all the finite subsets of $X$ (even the empty one). The resulting inductive limit is again isomorphic to $\mathcal{R}$.

We shall need the following generalization of Proposition 2.2. The proof is done by using the “back-and-forth” device.

**Proposition 2.5.** For $k = 1,2$, let $\pi_k : \Sigma \rightsquigarrow \mathcal{R}$ be two free and non-singular actions of the finite group $\Sigma$. For any partial isomorphism $\varphi \in P(\mathcal{R})$ such that $\pi_1(\Sigma)d(\varphi) = d(\varphi)$ and $\pi_2(\Sigma)r(\varphi) = r(\varphi)$ and $\varphi\pi_1(\sigma) = \pi_2(\sigma)\varphi$ for all $\sigma \in \Sigma$, there exists $\bar{\varphi} \in \mathrm{Aut}(\mathcal{R})$ such that $\bar{\varphi}\pi_1(\sigma) = \pi_2(\sigma)\bar{\varphi}$ for all $\sigma \in \Sigma$ and $\bar{\varphi}|_{d(\varphi)} = \varphi$.

*Proof.* Write $V(\mathcal{R}) \setminus d(\varphi) = \bigsqcup_{k=1}^{\infty} \pi_1(\Sigma)x_k$ and $V(\mathcal{R}) \setminus r(\varphi) = \bigsqcup_{k=1}^{\infty} \pi_2(\Sigma)y_k$. We define inductively pairwise distinct integers $k_n$, pairwise distinct integers $l_n$, subsets

$$A_n = d(\varphi) \sqcup \pi_1(\Sigma)x_{k_1} \sqcup \dots \sqcup \pi_1(\Sigma)x_{k_n} \subset V(\mathcal{R}),$$ $$B_n = r(\varphi) \sqcup \pi_2(\Sigma)y_{l_1} \sqcup \dots \sqcup \pi_2(\Sigma)y_{l_n} \subset V(\mathcal{R})$$

and isomorphisms $\varphi_n : A_n \to B_n$ such that $\varphi_n|_{d(\varphi)} = \varphi$, $\varphi_n\pi_1(\sigma) = \pi_2(\sigma)\varphi_n$ for all $\sigma \in \Sigma$, $A_n \subset A_{n+1}$, $B_n \subset B_{n+1}$, $\varphi_{n+1}|_{A_n} = \varphi_n$ and $V(\mathcal{R}) = \bigcup A_n = \bigcup B_n$. Once it is done, the Proposition is proved since we can define $\bar{\varphi} \in \mathrm{Aut}(\mathcal{R})$, $x \in A_n \mapsto \varphi_n(x)$ which obviously satisfies $\bar{\varphi}\pi_1(\sigma) = \pi_2(\sigma)\bar{\varphi}$ for all $\sigma \in \Sigma$ and $\bar{\varphi}|_{d(\varphi)} = \varphi$.

Define $A_0 = d(\varphi)$, $B_0 = r(\varphi)$ and $\varphi_0 = \varphi$. If step $n$ is constructed and $n$ is even define $k_{n+1} = \mathrm{Min}\{k \ge 1 : x_k \notin A_n\}$, $U = \{x \in A_n : x \sim x_{k_{n+1}}\}$, $V = A_n \setminus U$ and

$$W = \{y \in V(\mathcal{R}) \setminus B_n : y \sim \varphi_n(x) \text{ for all } x \in U \text{ and } y \sim \varphi_n(x) \text{ for all } x \in V\}.$$

By property (R), $W$ is non-empty. Let $l_{n+1} = \mathrm{Min}\{k \ge 1 : \pi_2(\Sigma)y_k \cap W \ne \emptyset\}$. Replacing $y_{l_{n+1}}$ by an element in $\pi_2(\Sigma)y_{l_{n+1}}$ we may and will assume that $y_{l_{n+1}} \in W$. Define $A_{n+1} = A_n \sqcup \pi_1(\Sigma)x_{k_{n+1}}$ and $B_{n+1} = B_n \sqcup \pi_2(\Sigma)y_{l_{n+1}}$. By freeness, we may define a bijection $\varphi_{n+1} : A_{n+1} \to B_{n+1}$ by $\varphi_{n+1}|_{A_n} = \varphi_n$ and $\varphi_{n+1}(\pi_1(\sigma)x_{k_{n+1}}) = \pi_2(\sigma)y_{k_{n+1}}$, for all $\sigma \in \Sigma$. By construction, it is an isomorphism between the induced graphs. Indeed if $x \in A_n$ is such that $x \sim \pi_1(\sigma)x_{k_{n+1}}$ for some $\sigma \in \Sigma$ then $\pi_1(\sigma^{-1})x \sim x_{k_{n+1}}$ so $y_{l_{n+1}} \sim \varphi_n(\pi_1(\sigma^{-1})x) = \pi_2(\sigma^{-1})\varphi_n(x)$ hence, $\varphi_{n+1}(x) = \varphi_n(x) \sim \pi_2(\sigma)y_{l_{n+1}} = \varphi_{n+1}(\pi_1(\sigma)x_{k_{n+1}})$. Since $\varphi_n$ is a graph isomorphism and since both actions are non-singular (which means that there is no edges on induced subgraphs of the form $\pi_k(\Sigma)z$) it shows that $\varphi_{n+1}$ is also a graph isomorphism. By construction we also have that $\varphi_{n+1}\pi_1(\sigma) = \pi_2(\sigma)\varphi_{n+1}$ for all $\sigma \in \Sigma$.

If $n$ is odd define $l_{n+1} = \mathrm{Min}\{k \ge 1 : y_k \notin B_n\}$, $U = \{y \in B_n : y \sim y_{l_{n+1}}\}$, $V = B_n \setminus U$ and

$$W = \{x \in V(\mathcal{R}) \setminus A_n : x \sim \varphi_n^{-1}(y) \text{ for all } y \in U \text{ and } x \sim \varphi_n^{-1}(y) \text{ for all } y \in V\}.$$

By property (R), $W$ is non-empty. Let $k_{n+1} = \mathrm{Min}\{k \ge 1 : x_k \in W\}$. We may and will assume that $x_{k_{n+1}} \in W$. Define $A_{n+1} = A_n \sqcup \pi_1(\Sigma)x_{k_{n+1}}$, $B_{n+1} = B_n \sqcup \pi_2(\Sigma)y_{l_{n+1}}$. By construction, the map $\varphi_{n+1} : A_{n+1} \to B_{n+1}$ defined by $\varphi_{n+1}|_{A_n} = \varphi_n$ and $\varphi_{n+1}(\pi_1(\sigma)x_{k_{n+1}}) = \pi_2(\sigma)y_{k_{n+1}}$, $\sigma \in \Sigma$, is an isomorphism between the induced graphs.

Let us show that $\cup A_n = d(\varphi) \sqcup \bigsqcup_{n=1}^{\infty} \pi_1(\Sigma)x_{k_n} = V(\mathcal{R})$. It suffices to show that $\{k_n : n \ge 1\} = \mathbb{N}^*$. Suppose that there exists $s \in \mathbb{N}$, $s \ne k_n$ for all $n \ge 1$. Since the elements $k_n$ are pairwise distinct, the set $\{k_{2n+1} : n \ge 0\}$ is not bounded. Hence, there exists $n \in \mathbb{N}$ such that $s < k_{2n+1}$. By definition, we have $k_{2n+1} = \mathrm{Min}\{k \ge 1 : x_k \notin A_{2n}\}$. However we have $x_s \notin A_{2n}$ and $s < k_{2n+1}$, a contradiction. The proof of $\cup B_n = V(\mathcal{R})$ is similar.

□
2.2. **Induced action on the Random Graph.** Let $\Gamma \curvearrowright \mathcal{G}$ be an action of a group $\Gamma$ on a non-empty countable graph $\mathcal{G}$ and consider the sequence of graphs $\mathcal{G}_0 = \mathcal{G}$ and $\mathcal{G}_{n+1} = \tilde{\mathcal{G}}_n$ with the associated sequence of actions $\Gamma \curvearrowright \mathcal{G}_n$. By Proposition 2.3, assertion (3), the inductive limit action defines an action of $\Gamma$ on $\mathcal{R}$. We call it the *induced action of $\Gamma \curvearrowright \mathcal{G}$ on $\mathcal{R}$*. We will show in Corollary 2.7 that many properties on the action $\Gamma \curvearrowright \mathcal{G}$ are preserved when passing to the induced action $\Gamma \curvearrowright \mathcal{R}$. However, freeness is not preserved and one has to consider a weaker notion that we call property $(F)$.

**Definition 2.6.** We say that an action $\Gamma \curvearrowright \mathcal{G}$ has *property $(F)$* if for all finite subsets $S \in \Gamma \setminus \{1\}$ and $F \subset V(\mathcal{G})$, there exists $x \in V(\mathcal{G}) \setminus F$ such that $x \not\approx u$ for all $u \in F$ and $gx \neq x$ for all $g \in S$.

Note that any action with property $(F)$ is faithful and any free action on $\mathcal{R}$ has property $(F)$.

**Corollary 2.7.** Let $\Gamma \curvearrowright \mathcal{G}$ be an action of a group $\Gamma$ on a non-empty countable graph $\mathcal{G}$ and write $\Gamma \curvearrowright \mathcal{R}$ the induced action. The following holds.

(1) If $\Gamma \curvearrowright \mathcal{G}$ is faithful then $\Gamma \curvearrowright \mathcal{R}$ is faithful.

(2) $\Gamma \curvearrowright \mathcal{G}$ has infinite orbits if and only if $\Gamma \curvearrowright \mathcal{R}$ has infinite orbits.

(3) $\Gamma \curvearrowright \mathcal{G}$ disconnects the finite sets if and only if $\Gamma \curvearrowright \mathcal{R}$ disconnects the finite sets.

(4) $\Gamma \curvearrowright \mathcal{G}$ is non-singular if and only if $\Gamma \curvearrowright \mathcal{R}$ is non-singular.

(5) Let $\Sigma < \Gamma$ be a subgroup. $\Sigma$ is highly core-free w.r.t. $\Gamma \curvearrowright \mathcal{G}$ if and only if $\Sigma$ is highly core-free w.r.t. $\Gamma \curvearrowright \mathcal{R}$.

(6) If $\Gamma \curvearrowright \mathcal{G}$ is free, $\mathcal{G}$ is infinite and $\Gamma$ is torsion free then $\Gamma \curvearrowright \mathcal{R}$ is free.

(7) If $\Gamma \curvearrowright \mathcal{G}$ is strongly faithful, $\mathcal{G}$ is infinite then $\Gamma \curvearrowright \mathcal{R}$ has property $(F)$.

*Proof.* The assertions (1) to (6) follow directly follows from Propositions 1.1, 1.2 and 1.3. Let us prove (7). We recall that $\mathcal{R} = \mathcal{G}_\infty = \cup \uparrow \mathcal{G}_n$, where $\mathcal{G}_0 = \mathcal{G}$ and $\mathcal{G}_{n+1} = \tilde{\mathcal{G}}_n$. Let $F \subset V(\mathcal{G}_\infty)$ and $S = \{g_1, \dots, g_n\} \subset \Gamma \setminus \{1\}$ be finite subsets. Since $\Gamma \curvearrowright \mathcal{G}$ is strongly faithful we deduce, by Proposition 1.1 (6) and induction that $\Gamma \curvearrowright \mathcal{G}_N$ is strongly faithful for all $N$. Let $N \in \mathbb{N}$ be large enough so that $F \subset V(\mathcal{G}_N)$. We can use strong faithfulness (and the fact that $\mathcal{G}_N$ is infinite) to construct, by induction, pairwise distinct vertices $y_1, \dots, y_n \in V(\mathcal{G}_N) \setminus F$ such that $y_i \neq g_j y_j$ for all $1 \le i, j \le n$. Define $x := \{y_1, \dots, y_n\} \in \mathcal{P}_f(V(\mathcal{G}_N)) \subset V(\mathcal{G}_{N+1}) \subset V(\mathcal{G}_\infty) = V(\mathcal{R})$. By construction $x \in V(\mathcal{R}) \setminus F$ and $g_k x \neq x$ for all $k$. Since the inclusion $\mathcal{G}_{N+1} \subset \mathcal{G}_\infty = \mathcal{R}$ is open, we also have $x \not\approx u$ for all $u \in F$. $\square$

**Corollary 2.8.** Every infinite countable group $\Gamma$ admits an action $\Gamma \curvearrowright \mathcal{R}$ that is non-singular, has property $(F)$ and disconnects the finite sets. If $\Gamma$ is torsion-free then the action can be chosen to be moreover free.

*Proof.* Consider the graph $\mathcal{G}$ defined by $V(\mathcal{G}) = \Gamma$ and $E(\mathcal{G}) = \emptyset$ with the action $\Gamma \curvearrowright \mathcal{G}$ given by left multiplication which is free, has infinite orbits and hence disconnects the finite sets and is non-singular since $E(\mathcal{G}) = \emptyset$. By Corollary 2.7 the induced action $\Gamma \curvearrowright \mathcal{R}$ has the required properties. $\square$

2.3. **The Random Extension with paramater.** We now describe a parametrized version of the induced action. As explained before, freeness is not preserved when passing to the action on the Random Extension and also when passing to the induced action. However, it is easy to compute explicitly the fixed points of any group element in the Random Extension. Now, given an action $\Gamma \curvearrowright \mathcal{G}$ and some fixed group elements in $\Gamma$, one can modify the Random Extension by removing the fixed points of our given group elements to make them act freely on
this modified version of the Random Extension. Then, the inductive limit process associated to this modified Random Extension will also produce, in some cases, the Random Graph with an action on it, for which our given group elements act freely. We call this process the parametrized Random Extension.

Let $\pi : \Gamma \curvearrowleft \mathcal{G}$ be an action of the group $\Gamma$ on the graph $\mathcal{G}$ and $F \subset \Gamma$ be a subset. From the action $\pi$, we have a canonical action $\Gamma \curvearrowleft \tilde{\mathcal{G}}$ on the Random Extension.

**Remark 2.9.** If $\mathcal{G}$ is infinite, for any $g \in \Gamma$, the set of fixed points of $g$ for the action on the Random Extension is either empty or of the form :

$$ \mathrm{Fix}_{\tilde{\mathcal{G}}}(g) = \{A \in P_f(V(\mathcal{G})) \text{ of the form } A = \sqcup_{i=1}^N \langle g \rangle x_i \text{ with } \langle g \rangle x_i \text{ finite } \forall i\} \sqcup \mathrm{Fix}_{\mathcal{G}}(g). $$

In particular, when the action $\pi$ is free one has $\mathrm{Fix}_{\tilde{\mathcal{G}}}(g) = \emptyset$ whenever $g$ has infinite order and, if $g$ has finite order, then $\mathrm{Fix}_{\tilde{\mathcal{G}}}(g)$ is the set of finite unions of $\langle g \rangle$-orbits.

Consider the induced subgraph on $V(\tilde{\mathcal{G}}) \setminus \{\mathrm{Fix}_{\tilde{\mathcal{G}}}(g) : g \in F\}$. Note that if $gFg^{-1} = F$ for all $g \in \Gamma$ then, since $g\mathrm{Fix}_{\tilde{\mathcal{G}}}(h) = \mathrm{Fix}_{\tilde{\mathcal{G}}}(ghg^{-1})$, the induced subgraph on $V(\tilde{\mathcal{G}}) \setminus \{\mathrm{Fix}_{\tilde{\mathcal{G}}}(g) : g \in F\}$ is globally $\Gamma$-invariant and we get an action of $\Gamma$ on it by restriction for which the elements of $F$ act freely by construction. However, for a general $F$, we cannot restrict the action and this is why we will remove more sets then the fixed points of elements of $F$.

Assume from now that $\mathcal{G}$ is a graph and $l \in \mathbb{N}^*$. We define the graph $\tilde{\mathcal{G}}_l$, the Random Extension of $\mathcal{G}$ with parameter $l$, as the induced subgraph on

$$ V(\tilde{\mathcal{G}}_l) := V(\mathcal{G}) \sqcup \{U \in \mathcal{P}_f(V(\mathcal{G})) : \mathrm{gcd}(l, |U|) = 1\} \subset V(\tilde{\mathcal{G}}). $$

Fix an action $\Gamma \curvearrowleft \mathcal{G}$. Since for any $g \in \Gamma$ and any finite subset $U \subset V(\mathcal{G})$ one has $|gU| = |U|$, the subgraph $\tilde{\mathcal{G}}_l$ is globally $\Gamma$-invariant and we get an action $\tilde{\pi}_l : \Gamma \curvearrowleft \tilde{\mathcal{G}}_l$ by restriction. Note that for any $u \in V(\mathcal{G})$ one has $\{u\} \in V(\tilde{\mathcal{G}}_l)$. It is clear that the inclusions of $\mathcal{G}$ in $\tilde{\mathcal{G}}_l$ and of $\tilde{\mathcal{G}}_l$ in $\tilde{\mathcal{G}}$ are $\Gamma$-equivariant open (and injective) graph homomorphisms.

**Proposition 2.10.** Let $\pi : \Gamma \curvearrowleft \mathcal{G}$ be an action and $l \in \mathbb{N}^*$.

(1) $\pi$ is faithful if and only if $\tilde{\pi}_l$ is faithful.

(2) $\pi$ is non-singular if and only if $\tilde{\pi}_l$ is non-singular.

(3) $\pi$ has infinite orbits if and only if $\tilde{\pi}_l$ has infinite orbits.

(4) $\pi$ disconnects the finite sets if and only if $\tilde{\pi}_l$ disconnects the finite sets.

(5) Let $\Sigma < \Gamma$ be a subgroup. $\Sigma$ is highly core-free w.r.t. $\pi$ if and only if $\Sigma$ is highly core-free w.r.t. $\tilde{\pi}_l$.

(6) If $\pi$ is strongly faithful and $\mathcal{G}$ is infinite then $\tilde{\pi}_l$ is strongly faithful.

(7) Let $\Sigma < \Gamma$ be a finite subgroup. If $\Sigma \curvearrowleft \mathcal{G}$ is free and $\mathcal{G}$ is infinite then $\Sigma \curvearrowleft \tilde{\mathcal{G}}_{|\Sigma|}$ is free.

*Proof.* Assertions (1) to (6) are obvious. Let us prove (7). Since any non-trivial element of $\Sigma$ acts freely, it follows from Remark 2.9 that any finite subset $U \subset V(\mathcal{G})$ in the set of fixed points of $\sigma \in \Sigma$ is a finite union of sets of the form $\langle \sigma \rangle x$, hence its size is a multiple of the order of $\sigma$ and $U \notin V(\tilde{\mathcal{G}}_{|\Sigma|})$. $\square$

We can now construct the induced action on $\mathcal{R}$ of the action $\pi$ with parameter $l$. Define the sequence of graphs $\mathcal{G}_0 = \mathcal{G}$ with action $\pi_0 = \pi$ of $\Gamma$ on it and, for $n \ge 0$, $\mathcal{G}_{n+1} = (\tilde{\mathcal{G}}_n)_l$ with the action $\pi_{n+1} = (\tilde{\pi}_n)_l$. Consider the inductive limit $\mathcal{G}_\infty^l$ with the inductive limit action $\pi_\infty^l : \Gamma \curvearrowleft \mathcal{G}_\infty^l$ on it. We list the properties of $\pi_l$ in the next Proposition.
**Proposition 2.11.** Let $\pi : \Gamma \curvearrowright \mathcal{G}$ be an action on a countable graph $\mathcal{G}$ and let $l \in \mathbb{N}^*$.

(1) If $\mathcal{G}$ is infinite then $\mathcal{G}_\infty^l \simeq \mathcal{R}$.

(2) $\pi$ is faithful if and only if $\pi_\infty^l$ is faithful.

(3) $\pi$ has infinite orbits if and only if $\pi_\infty^l$ has infinite orbits.

(4) $\pi$ disconnects the finite sets if and only if $\pi_\infty^l$ disconnects the finite sets.

(5) Let $\Sigma < \Gamma$ be a subgroup. $\Sigma$ is highly core-free w.r.t. to $\pi$ if and only if $\Sigma$ is highly core-free w.r.t. to $\pi_\infty^l$.

(6) $\pi$ is non-singular if and only if $\pi_\infty^l$ is non-singular.

(7) Let $\Sigma < \Gamma$ be a finite subgroup. If $\Sigma \curvearrowright \mathcal{G}$ is free and $\mathcal{G}$ is infinite then $\Sigma \curvearrowright \mathcal{G}_\infty^{|\Sigma|}$ is free.

(8) Suppose that $\Gamma$ and $\mathcal{G}$ are infinite. If $\pi$ is strongly faithful then $\pi_\infty^l$ has property (F).

*Proof.* The assertions (2) to (7) follow directly from Propositions 2.10, 1.2 and 1.3.

(1). Since $\mathcal{G}$ is infinite it follows that $\mathcal{G}_n$ is infinite for all $n$ and $\mathcal{G}_\infty$ is infinite. Hence, it suffices to check that $\mathcal{G}_\infty$ has property (R). Let $U, V \subset V(\mathcal{G}_\infty)$ be two finite subsets such that $U \cap V = \emptyset$ and let $n \in \mathbb{N}$ such that $U, V \subset V(\mathcal{G}_n)$. Since $V(\mathcal{G}_n) \setminus V$ is infinite, we may find a finite subset $x \subset V(\mathcal{G}_n) \setminus V$ such that $U \subset x$ and $\gcd(|x|, |\Sigma|) = 1$. Hence, $x \in V(\widetilde{\mathcal{G}_n}|_\Sigma) \subset V(\mathcal{G}_\infty^|\Sigma|)$ is such that $x \sim u$ for all $u \in U$ and $x \not\sim v$ for all $v \in V$.

(8). Let $S = \{g_1, \dots, g_n\} \subset \Gamma \setminus \{1\}$ and $F \subset V(\mathcal{G}_\infty^l)$ be finite subsets. Taking a larger $S$ if necessary, we may and will assume that $\gcd(n, l) = 1$. We repeat the proof of Corollary 2.7, assertion (7) and we get pairwise distinct vertices $y_1, \dots, y_n \in V(\mathcal{G}_N)$, where $F \subset V(\mathcal{G}_N)$ such that the element $x = \{y_1, \dots, y_n\} \in \mathcal{P}_f(V(\mathcal{G}_N)) \subset \widetilde{\mathcal{G}}_N$ satisfies the desired properties. Since $\gcd(|x|, l) = 1$, $x \in V(\widetilde{\mathcal{G}}_N)_l \subset V(\mathcal{G}_\infty^l)$. This concludes the proof. $\square$

Let $\Sigma < \Gamma$ be a finite subgroup of an infinite countable group $\Gamma$. By considering the induced action on $\mathcal{R}$ with parameter $l = |\Sigma|$ of the free action by left multiplication $\Gamma \curvearrowright \Gamma$ and view $\Gamma$ as a graph with no edges, we obtain the following Corollary.

**Corollary 2.12.** Let $\Sigma < \Gamma$ be a finite subgroup of an infinite countable group $\Gamma$. There exists a non-singular action $\Gamma \curvearrowright \mathcal{R}$ with property (F) such that the action $\Sigma \curvearrowright \mathcal{R}$ is free, the action $H \curvearrowright \mathcal{R}$ of any infinite subgroup $H < \Gamma$ disconnects the finite sets and, for any pair of intermediate subgroups $\Sigma' < H' < \Gamma$, if $\Sigma'$ is a highly core-free in $H'$ then $\Sigma'$ is highly core-free w.r.t. $H' \curvearrowright \mathcal{R}$.

## 2.4. Homogeneous actions on the Random Graph.

**Proposition 2.13.** Let $\Gamma \curvearrowright \mathcal{R}$ be an homogeneous action. The following holds.

(1) $\Gamma \curvearrowright \mathcal{R}$ disconnects the finite sets.

(2) If $N < \Gamma$ is normal then either $N$ acts trivially or it acts homogeneously.

*Proof.* (1). Let $F \subset V(\mathcal{R})$ be a finite set and write $F = \{u_1, \dots, u_n\}$ where the vertices $u_i$ are pairwise distinct. We shall define inductively pairwise distinct vertices $v_1, \dots, v_n \in V(\mathcal{R}) \setminus F$ such that, for all $1 \le i, j \le n$, $u_i \sim u_j \Leftrightarrow v_i \sim v_j$ and $u_i \not\sim v_j$. Take $v_1 \in \mathcal{R}_{\emptyset, F}$. Suppose that for a given $1 \le l \le n-1$ we have pairwise distinct vertices $v_1, \dots, v_l \in V(\mathcal{R}) \setminus F$ such that, for all $1 \le i, j \le l$, $u_i \sim u_j \Leftrightarrow v_i \sim v_j$ and $u_i \not\sim v_j$. Let $U = \{v_i : 1 \le i \le l \text{ s.t. } u_i \sim u_{l+1}\}$ and $V = \{v_i : 1 \le i \le l \text{ s.t. } u_i \not\sim u_{l+1}\}$. Then $U$ and $V \sqcup F$ are finite and disjoint. Take $v_{l+1} \in \mathcal{R}_{U, V \sqcup F}$. Then $v_{l+1} \sim v_i \Leftrightarrow u_{l+1} \sim u_i$ and $v_{l+1} \not\sim u_i$ for all $1 \le i \le l$ and $v_{l+1} \notin F \sqcup \{v_i : 1 \le i \le l\}$. This concludes the construction of the $v_i$ by induction. By the
properties of the $v_i$, the map $\varphi : \{u_i : 1 \le i \le n\} \to \{v_i : 1 \le i \le n\}$ defined by $\varphi(v_i) = v_i$ is an isomorphism between the induced subgraphs. Since $\Gamma \curvearrowleft \mathcal{R}$ is homogeneous there exists $g \in \Gamma$ such that $gu_i = v_i$ for all $1 \le i \le n$. It follows that $gF \cap F = \emptyset$ and $gu \sim u'$ for all $u, u' \in F$.

(2). Write $\overline{N}$ the closure of the image of $N$ inside Aut($\mathcal{R}$). By [Tr85], the abstract group Aut($\mathcal{R}$) is simple and, since $\overline{N}$ is normal in Aut($\mathcal{R}$) one has either $\overline{N} = \{1\}$ or $\overline{N} = \text{Aut}(\mathcal{R})$. $\square$

Using the previous Proposition and arguing as in [MS13, Corollary 1.6] we obtain the following Corollary.

**Corollary 2.14.** If $\Gamma \in \mathcal{H}_R$ then $\Gamma$ is icc and not solvable.

### 3. ACTIONS OF AMALGAMATED FREE PRODUCTS ON THE RANDOM GRAPH

Let $\Gamma_1, \Gamma_2$ be two countable groups with a common finite subgroup $\Sigma$ and define $\Gamma = \Gamma_1 *_{\Sigma} \Gamma_2$. Suppose that we have a faithful action $\Gamma \curvearrowleft \mathcal{R}$ and view $\Gamma < \text{Aut}(\mathcal{R})$.

Let $Z := \{\alpha \in \text{Aut}(\mathcal{R}) : \alpha\sigma = \sigma\alpha \forall\sigma \in \Sigma\}$. Note that $Z$ is a closed subgroup of $\text{Aut}(\mathcal{R})$, hence a Polish group. Moreover, for all $\alpha \in Z$, there exists a unique group homomorphism $\pi_\alpha : \Gamma \to \text{Aut}(\mathcal{R})$ such that:

$$ \pi_{\alpha}(g) = \begin{cases} g & \text{if } g \in \Gamma_1, \\ \alpha^{-1}g\alpha & \text{if } g \in \Gamma_2. \end{cases} $$

When $\Sigma$ is trivial, we have $Z = \text{Aut}(\mathcal{R})$. In this section we prove the following result.

**Theorem 3.1.** If $\Gamma \curvearrowleft \mathcal{R}$ is non-singular and has property (F), $\Sigma$ is highly core-free w.r.t. $\Gamma_1, \Gamma_2 \curvearrowleft \mathcal{R}$ and $\Sigma \curvearrowleft \mathcal{R}$ is free then the set $O = \{\alpha \in Z : \pi_\alpha \text{ is homogeneous and faithful}\}$ is a dense $G_\delta$ in $Z$. In particular, for every countably infinite groups $\Gamma_1, \Gamma_2$ we have $\Gamma_1 *_{\Sigma} \Gamma_2 \in \mathcal{H}_R$ and, for any finite highly core-free subgroup $\Sigma < \Gamma_1, \Gamma_2$ we have $\Gamma_1 *_{\Sigma} \Gamma_2 \in \mathcal{H}_R$.

*Proof.* We separate the proof in two lemmas.

**Lemma 3.2.** If $\Sigma \curvearrowleft \mathcal{R}$ is free and non-singular and $\Sigma$ is highly core-free w.r.t. $\Gamma_1, \Gamma_2 \curvearrowleft \mathcal{R}$ then the set $U = \{\alpha \in Z : \pi_\alpha \text{ is homogeneous}\}$ is a dense $G_\delta$ in $Z$.

*Proof.* Since $U = \cap_{\varphi \in P(\mathcal{R})} U_\varphi$, where $U_\varphi = \{\alpha \in Z : \exists g \in \Gamma \text{ such that } \pi_\alpha(g)|_{d(\varphi)} = \varphi\}$ is obviously open, it suffices to show that $U_\varphi$ is dense for all $\varphi \in P(\mathcal{R})$. Let $\varphi \in P(\mathcal{R})$, $\alpha \in Z$ and $F \subset V(\mathcal{R})$ a finite subset. It suffices to show that there exists $\gamma \in Z$ and $g \in \Gamma$ such that $\gamma|_F = \alpha|_F$ and $\pi_\gamma(g)|_{d(\varphi)} = \varphi$. Since $\Sigma$ is highly core-free w.r.t. $\Gamma_1 \curvearrowleft \mathcal{R}$ and $\Sigma F$ and $d(\varphi)$ are both finite sets, there exists $g_1 \in \Gamma_1$ such that $g_1 d(\varphi) \cap \Sigma F = \emptyset$, $g_1 x \sim u$ and $\sigma g_1 x \sim g_1 x'$ for all $u \in \Sigma F$, $x, x' \in d(\varphi)$, $\sigma \in \Sigma \setminus \{1\}$ and $\Sigma g_1 x \cap \Sigma g_1 x' = \emptyset$ for all $x, x' \in d(\varphi)$ with $x \neq x'$. Since $\Sigma$ is highly core-free w.r.t. $\Gamma_1 \curvearrowleft \mathcal{R}$, there exists also $g_2 \in \Gamma_1$ such that $g_2^{-1}r(\varphi) \cap (\Sigma F \cup \Sigma g_1 d(\varphi)) = \emptyset$ and $g_2^{-1}y \sim u$, $\sigma g_2^{-1}y \sim g_2^{-1}y'$ for all $u \in \Sigma F \cup \Sigma g_1 d(\varphi)$, $y, y' \in r(\varphi)$, $\sigma \in \Sigma \setminus \{1\}$ and $\Sigma g_2^{-1}y \cap \Sigma g_2^{-1}y' = \emptyset$ for all $y, y' \in r(\varphi)$ with $y \neq y'$. Define $F' = \alpha(\Sigma F) \cup \Sigma \alpha(g_1 d(\varphi))$. Since $\Sigma$ is highly core-free w.r.t. $\Gamma_2 \curvearrowleft \mathcal{R}$, there exists $h \in \Gamma_2$ such that $hF' \cap F' = \emptyset$ and for all $u, v \in F'$ and $\sigma \in \Sigma \setminus \{1\}$, $hu \sim v$, $\sigma hu \sim hv$ and $\Sigma hu \cap \Sigma hu' = \emptyset$ for all $u, u' \in F'$ with $u \neq u'$. Define $A = (\Sigma F) \cup \Sigma g_1 d(\varphi) \cup \Sigma g_2^{-1}r(\varphi)$ and $B = \alpha(\Sigma F) \cup \alpha(\Sigma g_1 d(\varphi)) \cup \Sigma h\alpha(g_1 d(\varphi))$. Note that $\Sigma A = A$ and, since $\alpha \in Z$, $\Sigma B = B$. Since the $\Sigma$ action is free, we can define a bijection $\gamma_0 : A \to B$ by $\gamma_0(u) = \alpha(u)$ for
$u \in \Sigma F \sqcup \Sigma g_1 d(\varphi)$ and $\gamma_0(\sigma g_2^{-1} \varphi(x)) = \sigma h \alpha g_1 x$, for all $x \in d(\varphi)$ and $\sigma \in \Sigma$. By construction, $\gamma_0$ is a partial isomorphism and $\gamma_0 \sigma = \sigma \gamma_0$ for all $\sigma \in \Sigma$. By Proposition 2.5 there exists an extension $\gamma \in Z$ of $\gamma_0$. Note that $\gamma|_F = \alpha|_F$ moreover, with $g = g_2 h g_1 \in \Gamma$ we have, for all $x \in d(\varphi)$, $\pi_\gamma(g)x = g_2 \gamma^{-1} h \gamma g_1 x = g_2 \gamma^{-1} h \alpha(g_1 x) = g_2 g_2^{-1} \varphi(x) = \varphi(x)$. $\square$

**Lemma 3.3.** If $\Sigma \curvearrowleft \mathcal{R}$ is free, $\Gamma \curvearrowleft \mathcal{R}$ is non-singular and has property (F) then the set $V = \{\alpha \in Z : \pi_\alpha \text{ is faithful}\}$ is a dense $G_\delta$ in Z.

*Proof.* Writing $V = \cap_{g \in \Gamma \setminus \{1\}} V_g$, where $V_g = \{\alpha \in Z : \pi_\alpha(g) \neq \text{id}\}$ is obviously open, it suffices to show that $V_g$ is dense for all $g \in \Gamma \setminus \{1\}$. If $g \in \Gamma_k \setminus \{1\}$ ($k = 1, 2$) then it is easy to see that $V_g = Z$. Hence it suffices to show that $V_g$ is dense for all $g$ reduced of length at least 2. Write $g = g_{i_n} \dots g_{i_1}$, where $n \ge 2$ and $g_{i_k} \in \Gamma_{i_k} \setminus \Sigma$ reduced expression for $g$. Fix $\alpha \in Z$ and $F \subset V(\mathcal{R})$ a finite subset. Define the finite sets

$$ \tilde{F} := \Sigma F \cup \alpha(\Sigma F) \cup \left( \bigcup_{l=1}^{n} (g_{i_l} \dots g_{i_1})^{-1} (\Sigma F \cup \alpha(\Sigma F)) \right) \subset V(\mathcal{R}), $$

and

$$ S := \{\sigma g_{i_l} \dots g_{i_1} : 1 \le l \le n, \sigma \in \Sigma\} \cup \{g_{i_1}^{-1} \dots g_{i_l}^{-1} \sigma g_{i_k} \dots g_{i_1} : 1 \le l < k \le n, \sigma \in \Sigma\} \subset \Gamma \setminus \{1\}. $$

Using property (F) for $\Gamma \curvearrowleft \mathcal{R}$ we find a vertex $x \in V(\mathcal{R}) \setminus \tilde{F}$ such that $x \sim u$ for all $u \in \tilde{F}$ and $gx \neq x$ for all $g \in S$. In particular, the sets $\Sigma F$ (resp. $\alpha(\Sigma F)$) and $\Sigma x$, $\Sigma g_{i_l} \dots g_{i_1} x$ for $1 \le l \le n$ are pairwise distincts and, since $\Gamma \curvearrowleft \mathcal{R}$ is non-singular, the only vertices on the induced subgraph on $Y := \Sigma F \sqcup (\bigcup_{l=1}^n \Sigma g_{i_l} \dots g_{i_1} x) \sqcup \Sigma x$ (resp. $Y' := \Sigma \alpha(F) \sqcup (\bigcup_{l=1}^n \Sigma g_{i_l} \dots g_{i_1} x) \sqcup \Sigma x$) are the ones with extremities in $\Sigma F$ (resp. $\Sigma \alpha(F)$). Hence, the bijection $\gamma_0 : Y \to Y'$ defined by $\gamma_0|_{\Sigma F} = \alpha|_{\Sigma F}$ and $\gamma_0|_{Y \setminus \Sigma F} = \text{id}$ is a graph isomorphism between the induced subgraphs. By construction and since $\alpha \in Z$ we have $\gamma_0 \sigma = \sigma \gamma_0$ for all $\sigma \in \Sigma$. By Proposition 2.5 there exists an extension $\gamma \in Z$ of $\gamma_0$. Then $\gamma|_F = \alpha|_F$ and $\pi_\gamma(g_{i_n} \dots g_{i_1})x = g_{i_n} \dots g_{i_1} x \neq x$, since $g_{i_n} \dots g_{i_1} \in S$. Hence $\gamma \in V_g$. $\square$

*End of the proof of the Theorem.* The first part of the Theorem follows from Lemmas 3.2 and 3.3 since $O = U \cap V$. The last part follows from the first part and Corollary 2.12. $\square$

We have a similar result when only one of the factors in the free product is infinite.

**Theorem 3.4.** Suppose that $\Gamma_2$ is finite such that $[\Gamma_2 : \Sigma] \ge 2$. If $\Gamma \curvearrowleft \mathcal{R}$ is non-singular and has property (F), $\Sigma$ is highly core-free w.r.t. $\Gamma_1 \curvearrowleft \mathcal{R}$ and the action $\Gamma_2 \curvearrowleft \mathcal{R}$ is free then the set

$$ O = \{\alpha \in Z : \pi_{\alpha} \text{ is homogeneous and faithful}\} $$

is a dense $G_\delta$ in Z. In particular, for every countably infinite group $\Gamma_1$, for every finite non-trivial group $\Gamma_2$ we have $\Gamma_1 * \Gamma_2 \in \mathcal{H}_R$ and, for any common finite subgroup $\Sigma < \Gamma_1, \Gamma_2$ such that $\Sigma$ is highly core-free in $\Gamma_1$ and $[\Gamma_2 : \Sigma] \ge 2$ we have $\Gamma_1 * \Gamma_2 \in \mathcal{H}_R$.

*Proof.* We first prove the analogue of Lemma 3.2.

**Lemma 3.5.** If $\Sigma$ is highly core-free w.r.t. $\Gamma_1 \curvearrowleft \mathcal{R}$, $\Gamma_2$ is finite and $\Gamma_2 \curvearrowleft \mathcal{R}$ is free and non-singular such that $[\Gamma_2 : \Sigma] \ge 2$, then the set $U = \{\alpha \in Z : \pi_\alpha \text{ is homogeneous}\}$ is a dense $G_\delta$ in Z.
**Proof.** Since $U = \cap_{\varphi \in P(\mathcal{R})} U_{\varphi}$, where $U_{\varphi} = \{\alpha \in Z : \exists g \in \Gamma \text{ such that } \pi_{\alpha}(g)|_{d(\varphi)} = \varphi\}$ is obviously open, it suffices to show that $U_{\varphi}$ is dense for all $\varphi \in P(\mathcal{R})$. Let $\varphi \in P(\mathcal{R})$, $\alpha \in Z$ and $F \subset V(\mathcal{R})$ a finite subset. Since $\Sigma$ is highly core-free w.r.t. $\Gamma_1 \curvearrowleft \mathcal{R}$, there exists $g_1 \in \Gamma_1$ such that $g_1 d(\varphi) \cap \Sigma F = \emptyset$, $g_1 x \not\sim u$ and $\sigma g_1 x \not\sim g_1 x'$ for all $u \in \Sigma F$, $x, x' \in d(\varphi)$, $\sigma \in \Sigma \setminus \{1\}$ and $\Sigma g_1 x \cap \Sigma g_1 x' = \emptyset$ for all $x, x' \in d(\varphi)$ with $x \neq x'$. There exists also $g_2 \in \Gamma_1$ such that $g_2^{-1} r(\varphi) \cap (\Sigma F \sqcup \Sigma g_1 d(\varphi)) = \emptyset$ and $g_2^{-1} y \not\sim u$, $\sigma g_2^{-1} y \not\sim g_2^{-1} y'$ for all $u \in \Sigma F \sqcup \Sigma g_1 d(\varphi)$, $y, y' \in r(\varphi)$, $\sigma \in \Sigma \setminus \{1\}$ and $\Sigma g_2^{-1} y \cap \Sigma g_2^{-1} y' = \emptyset$ for all $y, y' \in r(\varphi)$ with $y \neq y'$. In the sequel we write $d(\varphi) = \{x_1, \dots, x_n\}$.

**Claim.** There exists pairwise distinct vertices $z_1, \dots, z_n \in V(\mathcal{R}) \setminus \Gamma_2 \alpha(F)$ such that

* $\Gamma_2 z_i \cap \Gamma_2 z_j = \emptyset, \forall 1 \le i \neq j \le n$;

* $\Sigma h z_i \cap \Sigma z_i = \emptyset, \forall h \in \Gamma_2 \setminus \Sigma, \forall 1 \le i \le n$;

* $h z_i \not\sim z_j, \forall h \in \Gamma_2 \setminus \{1\}, \forall 1 \le i, j \le n$;

* $x_i \sim x_j \Leftrightarrow z_i \sim z_j, \forall 1 \le i, j \le n$;

* $z_i \not\sim u, \forall u \in \Gamma_2 \alpha(F), \forall 1 \le i \le n$.

**Proof of the Claim.** We define inductively the vertices $z_1, \dots, z_n \in V(\mathcal{R}) \setminus \Gamma_2 \alpha(F)$. For $n=1$ we take $z_1 \in \mathcal{R}_{\emptyset, \Gamma_2 \alpha(F)} \setminus \Gamma_2 \alpha(F)$. Then $z_1 \notin \Gamma_2 \alpha(F)$ and, for all $u \in \Gamma_2 \alpha(F)$ and for all $h \in \Gamma_2$, $u \not\sim z_1$ and $h z_1 \not\sim z_1$ since $\Gamma_2 \curvearrowleft \mathcal{R}$ is non-singular. Moreover, since $\Gamma_2 \curvearrowleft \mathcal{R}$ is free, we have $h z_1 \neq \sigma z_i$ for all $h \in \Gamma_2 \setminus \Sigma$ and all $\sigma \in \Sigma$.

Suppose that, for a given $1 \le l \le n-1$, we have pairwise distinct vertices $z_1, \dots, z_l \in V(\mathcal{R}) \setminus \Gamma_2 \alpha(F)$ such that $\Gamma_2 z_i \cap \Gamma_2 z_j = \emptyset, \forall 1 \le i \neq j \le l, \Sigma h z_i \cap \Sigma z_i = \emptyset, \forall h \in \Gamma_2 \setminus \Sigma, \forall 1 \le i \le l, h z_i \not\sim z_j, \forall h \in \Gamma_2 \setminus \{1\}, x_i \sim x_j \Leftrightarrow z_i \sim z_j$ and $z_i \not\sim u, \forall u \in \Gamma_2 \alpha(F) \forall 1 \le i, j \le l$. Define

$$U = \{z_i : 1 \le i \le l \text{ s.t. } x_i \sim x_{l+1}\}$$

and

$$V = \{z_i : 1 \le i \le l \text{ s.t. } x_i \not\sim x_{l+1}\} \sqcup \{h z_i : 1 \le i \le l, h \in \Gamma_2 \setminus \{1\}\} \sqcup \Gamma_2 \alpha(F).$$

Since $\mathcal{R}_{U,V}$ is infinite and $\Gamma_2$ is finite, we may take

$$z_{l+1} \in \mathcal{R}_{U,V} \setminus \left( \Gamma_2 \alpha(F) \sqcup \sqcup_{i=1}^{l} \Gamma_2 z_i \right).$$

Then, for all $u \in \Gamma_2 \alpha(F)$, $u \not\sim z_{l+1}$ and, for all $1 \le i \le l, h \in \Gamma_2 \setminus \{1\}, x_i \sim x_{l+1} \Leftrightarrow z_i \sim z_{l+1}$, $h z_i \not\sim z_{l+1}$ and, for all $i \neq l+1, \Gamma_2 z_i \cap \Gamma_2 z_{l+1} = \emptyset$. Also, since $\Gamma_2 \curvearrowleft \mathcal{R}$ is free, we have $\Sigma h z_{l+1} \cap \Sigma z_{l+1} = \emptyset$ for all $h \in \Gamma_2 \setminus \Sigma$. This completes the proof.

**End of the proof of the Lemma.** Write $d(\varphi) = \{x_1, \dots, x_n\}$ and define, for $1 \le k \le n$, $y_k = \varphi(x_k)$. Let $z_1, \dots, z_n$ be the elements obtained by the Claim. Take $h \in \Gamma_2 \setminus \Sigma$. Then the sets $\alpha(\Sigma F), \Sigma z_i$ for $1 \le i \le n$, and $\Sigma h z_i$ for $1 \le i \le n$ are pairwise disjoint. Moreover, $u \not\sim \sigma z_i, u \not\sim \sigma h z_i$ and $\sigma' z_i \not\sim \sigma h z_j$ for all $u \in \alpha(\Sigma F)$, for all $\sigma, \sigma' \in \Sigma$ and for all $1 \le i, j \le n$. Define

$$A = \Sigma F \sqcup (\sqcup_{i=1}^n \Sigma g_1 x_i) \sqcup (\sqcup_{i=1}^n \Sigma g_2^{-1} y_i) \text{ and } B = \alpha(\Sigma F) \sqcup (\sqcup_{i=1}^n \Sigma z_i) \sqcup (\sqcup_{i=1}^n \Sigma h z_i)$$

and consider the induced graph structure on $A$ and $B$. Note that $\Sigma A = A, \Sigma B = B$ and the only vertices in $A$ (resp. $B$) are the ones with extremities in $\Sigma F$ (resp. $\alpha(\Sigma F)$). Since $\Sigma \curvearrowleft \mathcal{R}$ is free, we may define a bijection $\gamma_0 : A \to B$ by $\gamma_0(u) = \alpha(u)$ for $u \in \Sigma F$ and $\gamma_0(\sigma g_1 x_i) = \sigma z_i, \gamma_0(\sigma g_2^{-1} y_i) = \sigma h z_i$ for all $1 \le i \le n$ and for all $\sigma \in \Sigma$ which is a graph
isomorphism satisfying $\gamma_0\sigma = \sigma\gamma_0$ for all $\sigma \in \Sigma$. By Proposition 2.5, there exists an extension
$\gamma \in Z$ of $\gamma_0$. Then $\gamma|_F = \alpha|_F$ and with $g = g_2hg_1 \in \Gamma$ we have, for all $1 \le i \le n$,

$$
\pi_{\gamma}(g)x_i = g_2\gamma^{-1}h\gamma g_1x_i = g_2\gamma^{-1}hz_i = g_2g_2^{-1}y_i = y_i.
$$

□

End of the proof of the Theorem 3.4. The first assertion of the Theorem follows from Lemmas 3.5 and 3.3. The last part follows from the first part and Corollary 2.12, where the group $\Sigma$ in Corollary 2.12 is actually our group $\Gamma_2$, the group $\Sigma'$ is our group $\Sigma$ and the group $H'$ is our group $\Gamma_1$.
□

□

4. ACTIONS OF HNN EXTENSIONS ON THE RANDOM GRAPH

Let $\Sigma < H$ be a finite subgroup of a countable group $H$ and $\theta : \Sigma \to H$ be an injective group homomorphism. Define $\Gamma = \text{HNN}(H, \Sigma, \theta)$ the HNN-extension and let $t \in \Gamma$ be the “stable letter” i.e. $\Gamma$ is the universal group generated by $\Sigma$ and $t$ with the relations $t\sigma t^{-1} = \theta(\sigma)$ for all $\sigma \in \Sigma$. For $\epsilon \in \{-1, 1\}$, we write

$$
\Sigma_{\epsilon} := \begin{cases} \Sigma & \text{if } \epsilon = 1, \\ \theta(\Sigma) & \text{if } \epsilon = -1. \end{cases}
$$

Suppose that we have a faithful action $\Gamma \curvearrowright \mathcal{R}$ and view $\Gamma < \text{Aut}(\mathcal{R})$. Define the closed (hence Polish space) subset $Z = \{\alpha \in \text{Aut}(\mathcal{R}) : \theta(\sigma) = \alpha\sigma\alpha^{-1} \text{ for all } \sigma \in \Sigma\} \subset \text{Aut}(\mathcal{R})$ and note that it is non-empty (since $t \in Z$). By the universal property of $\Gamma$, for each $\alpha \in Z$ there exists a unique group homomorphism $\pi_{\alpha} : \Gamma \to \text{Aut}(\mathcal{R})$ such that

$$
\pi_{\alpha}|_{H} = \mathrm{id}_{H} \text{ and } \pi_{\alpha}(t) = \alpha.
$$

In this section we prove the following result.

**Theorem 4.1.** If $\Gamma \curvearrowright \mathcal{R}$ is non-singular, has property (F), $\Sigma_\epsilon \curvearrowright \mathcal{R}$ is free and $\Sigma_\epsilon$ is highly core-free w.r.t. $H \curvearrowright \mathcal{R}$ for all $\epsilon \in \{-1, 1\}$ then the set

$$
O = \{ \alpha \in \mathrm{Aut}(\mathcal{R}) : \pi_{\alpha} \text{ is faithful and homogeneous} \}
$$

is a dense $G_\delta$ in $Z$. In particular, for any finite subgroup $\Sigma$ of an infinite countable group $H$
such that $\Sigma_\epsilon < H$ is highly core-free for all $\epsilon \in \{-1, 1\}$, we have $\mathrm{HNN}(H, \Sigma, \theta) \in \mathcal{H}_R$.

We separate the proof in two lemmas.

**Lemma 4.2.** If, for all $\epsilon \in \{-1, 1\}$, $\Sigma_\epsilon \curvearrowright \mathcal{R}$ is free, non-singular and $\Sigma_\epsilon$ is highly core-free w.r.t. $H \curvearrowright \mathcal{R}$ then the set $U = \{\alpha \in \mathrm{Aut}(\mathcal{R}) : \pi_\alpha \text{ is homogeneous}\}$ is a dense $G_\delta$ in $Z$.

Proof. Since $U = \cap_{\varphi \in P(\mathcal{R})} U_\varphi$, where $U_\varphi = \{\alpha \in Z : \exists g \in \Gamma \text{ such that } \pi_\alpha(g)|_{d(\varphi)} = \varphi\}$ is obviously open, it suffices to show that $U_\varphi$ is dense for all $\varphi \in P(\mathcal{R})$. Let $\varphi \in P(\mathcal{R})$, $\alpha \in Z$ and $F \subset V(\mathcal{R})$ a finite subset. It suffices to show that there exists $\gamma \in Z$ and $g \in \Gamma$ such that $\gamma|_F = \alpha|_F$ and $\pi_\gamma(g)|_{d(\varphi)} = \varphi$. Since $\Sigma$ is highly core-free w.r.t. $H \curvearrowright \mathcal{R}$, there exists $g_1 \in H$ such that $g_1 d(\varphi) \cap \Sigma F = \emptyset$ and $g_1 x \approx u$, $\sigma g_1 x \approx g_1 x'$ for all $u \in \Sigma F$, $x, x' \in d(\varphi)$, $\sigma \in \Sigma \setminus \{1\}$ and $\Sigma g_1 x \cap \Sigma g_1 x' = \emptyset$ for all $x, x' \in d(\varphi)$ with $x \neq x'$. Since $\theta(\Sigma)$ is highly core-free w.r.t. $H \curvearrowright \mathcal{R}$, there exists $g_2 \in H$ such that $g_2^{-1} r(\varphi) \cap (\alpha(\Sigma F \cup \Sigma g_1 d(\varphi))) = \emptyset$ and $g_2^{-1} y \approx u$, $\theta(\sigma)g_2^{-1} y \approx g_2^{-1} y'$ for all $u \in \alpha(\Sigma F \cup \Sigma g_1 d(\varphi))$, $y, y' \in r(\varphi)$, $\sigma \in \Sigma \setminus \{1\}$ and $\theta(\Sigma)g_2^{-1} y \cap \theta(\Sigma)g_2^{-1} y' = \emptyset$ for all $y, y' \in r(\varphi)$ with $y \neq y'$. In the sequel we write $d(\varphi) = \{x_1, \dots, x_n\}$ and $y_i = \varphi(x_i)$. Define $Y = (\bigsqcup_{i=1}^n \Sigma g_1 x_i) \sqcup (\bigsqcup_{i=1}^n \Sigma \alpha^{-1}(g_2^{-1} y_i)) \sqcup (\Sigma F)$ and note that $\alpha(Y) = (\bigsqcup_{i=1}^n \theta(\Sigma)\alpha(g_1 x_i)) \sqcup (\bigsqcup_{i=1}^n \theta(\Sigma)(g_2^{-1} y_i)) \sqcup (\theta(\Sigma)\alpha(F))$. Note that $\Sigma Y = Y$
and $\theta(\Sigma)\alpha(Y) = \alpha(Y)$. Define the bijection $\gamma_0 : Y \to \alpha(Y)$ by $\gamma_0(\sigma g_1 x_i) = \theta(\sigma)g_2^{-1}y_i$, $\gamma_0(\sigma\alpha^{-1}(g_2^{-1}y_i)) = \theta(\sigma)\alpha(g_1 x_i)$ for all $1 \le i \le n$, $\sigma \in \Sigma$ and $\gamma_0|_{\Sigma F} = \alpha|_{\Sigma F}$. By construction $\gamma_0$ is a graph isomorphism such that $\gamma_0\sigma = \theta(\sigma)\gamma_0$ for all $\sigma \in \Sigma$. By Proposition 2.5 there exists an extension $\gamma \in Z$ of $\gamma_0$. Note that $\gamma|_F = \alpha|_F$ moreover, with $g = g_2tg_1 \in \Gamma$ we have, for all $1 \le i \le n$, $\pi_\gamma(g)x_i = g_2\gamma g_1 x_i = g_2\gamma_0(g_1 x_i) = g_2g_2^{-1}y_i = y_i$. $\square$

**Lemma 4.3.** If, for all $\epsilon \in \{-1, 1\}$, $\Sigma_\epsilon \cap \mathcal{R}$ is free and $\Gamma \cap \mathcal{R}$ is non-singular and has property (F) then the set $V = \{\pi_\alpha : \pi_\alpha \text{ is faithful}\}$ is a dense $G_\delta$ in $Z$.

*Proof.* Since $V = \bigcap_{g \in \Gamma \setminus \{1\}} V_g$, where $V_g = \{\alpha \in Z : \pi_\alpha(g) \neq \text{id}\}$ is clearly open, it suffices to show that $V_g$ is dense for all $g \in \Gamma \setminus \{1\}$. We may and will assume that $g \notin H$, since when $g \in H$ we have $V_g = Z$. Write $g = h_n t^{\epsilon_n} \dots t^{\epsilon_1} h_0$ a reduced expression for $g$, where $n \ge 1$, $h_k \in H$ and $\epsilon_k \in \{-1, 1\}$, $\forall 1 \le k \le n$. Fix $\alpha \in Z$ and $F \subset V(\mathcal{R})$ be a finite subset.

Define

$$H_1 = \begin{cases} \Sigma h_0 & \text{if } \epsilon_1 = 1 \\ \Sigma t^{-1} h_0 & \text{if } \epsilon_1 = -1 \end{cases} \quad \text{and} \quad \tilde{H}_1 = \begin{cases} \theta(\Sigma) t h_0 & \text{if } \epsilon_1 = 1 \\ \theta(\Sigma) h_0 & \text{if } \epsilon_1 = -1. \end{cases}$$

For $2 \le l \le n$, define

$$H_l = \begin{cases} \Sigma h_{l-1} t^{\epsilon_{l-1}} \dots t^{\epsilon_1} h_0 & \text{if } \epsilon_l = 1 \\ \Sigma t^{-1} h_{l-1} t^{\epsilon_{l-1}} \dots t^{\epsilon_1} h_0 & \text{if } \epsilon_l = -1 \end{cases} \quad \text{and} \quad \tilde{H}_l = \begin{cases} \theta(\Sigma) t h_{l-1} t^{\epsilon_{l-1}} \dots t^{\epsilon_1} h_0 & \text{if } \epsilon_l = 1 \\ \theta(\Sigma) h_{l-1} t^{\epsilon_{l-1}} \dots t^{\epsilon_1} h_0 & \text{if } \epsilon_l = -1. \end{cases}$$

Let $G := \cup_{l=1}^n H_l$, $\tilde{G} := \cup_{l=1}^n \tilde{H}_l$ and $S := G^{-1}G \cup \tilde{G}^{-1}\tilde{G} \cup \{g\} \subset \Gamma$ be finite subsets of $\Gamma$ and $\tilde{F} := \cup_{s \in G \cup \tilde{G}} s^{-1}(\Sigma F \cup \alpha(\Sigma F)) \subset V(\mathcal{R})$ a finite subset of $V(\mathcal{R})$. Since $\Gamma \cap \mathcal{R}$ has property (F) there exists $x \in V(\mathcal{R}) \setminus \tilde{F}$ such that $x \sim u$ for all $u \in \tilde{F}$ and $sx \neq x$ for all $s \in S \setminus \{1\}$. In particular, defining $Y_l := H_l x$ and $\tilde{Y}_l := \tilde{H}_l x$, the sets $\Sigma F$ and $Y_l$ (resp. $\alpha(\Sigma F)$ and $\tilde{Y}_l$) for $1 \le l \le n$ are pairwise disjoint and, using moreover the fact that $\Gamma \cap \mathcal{R}$ is non-singular, the only vertices on the induced subgraph on $Y := \Sigma F \cup (\bigsqcup_{l=1}^n Y_l)$ (resp. on $\tilde{Y} := \theta(\Sigma)\alpha(F) \cup (\bigsqcup_{l=1}^n \tilde{Y}_l)$) are the ones with extremities in $\Sigma F$ (resp. in $\theta(\Sigma)\alpha(F)$). It implies that the bijection $\gamma_0 : Y \to \tilde{Y}$ defined by $\gamma_0|_{\Sigma F} = \alpha|_{\Sigma F}$ and, for all $1 \le l \le n$, $\gamma_0|_{Y_l} = t|_{Y_l}$ is actually a graph isomorphism between the induced subgraphs. Since we clearly have $\gamma_0\sigma = \theta(\sigma)\gamma_0$ for all $\sigma \in \Sigma$, there exists, by Proposition 2.5 an extension $\gamma \in Z$ of $\gamma_0$. Then $\gamma$ satisfies $\gamma|_F = \alpha|_F$ and $\pi_\gamma(g)x = h_n\gamma^{\epsilon_n} \dots \gamma^{\epsilon_1}h_0x = h_n t^{\epsilon_n} \dots t^{\epsilon_1}h_0x = gx \neq x$ since $g \in S$. It follows that $\gamma \in V_g$. $\square$

*End of the proof of Theorem 4.1.* The first assertion follows directly from Lemmas 4.2 and 4.3 since $O = U \cap V$ and the last part follows from the first part and Corollary 2.12.

## 5. ACTIONS OF GROUPS ACTING ON TREES ON THE RANDOM GRAPH

Let $\Gamma$ be a group acting without inversion on a non-trivial tree. By [Se77], the quotient graph $\mathcal{G}$ can be equipped with the structure of a graph of groups $(\mathcal{G}, \{\Gamma_p\}_{p \in V(\mathcal{G})}, \{\Sigma_e\}_{e \in E(\mathcal{G})})$ where each $\Sigma_e = \Sigma_{\bar{e}}$ is isomorphic to an edge stabilizer and each $\Gamma_p$ is isomorphic to a vertex stabilizer and such that $\Gamma$ is isomorphic to the fundamental group $\pi_1(\Gamma, \mathcal{G})$ of this graph of groups i.e., given a fixed maximal subtree $\mathcal{T} \subset \mathcal{G}$, the group $\Gamma$ is generated by the groups $\Gamma_p$ for $p \in V(\mathcal{G})$ and the edges $e \in E(\mathcal{G})$ with the relations

$$\bar{e} = e^{-1}, \quad s_e(x) = er_e(x)e^{-1}, \quad \forall x \in \Sigma_e \quad \text{and} \quad e = 1 \quad \forall e \in E(\mathcal{T}),$$

where $s_e : \Sigma_e \to \Gamma_{s(e)}$ and $r_e = s_{\bar{e}} : \Sigma_e \to \Gamma_{r(e)}$ are respectively the source and range group monomorphisms.
**Theorem 5.1.** If $\Gamma_p$ is countably infinite, for all $p \in V(\mathcal{G})$, $\Sigma_e$ is finite and $s_e(\Sigma_e)$ is highly core-free in $\Gamma_{s(e)}$, for all $e \in E(\mathcal{G})$, then $\Gamma \in \mathcal{H}_R$.

*Proof.* Let $e_0$ be one edge of $\mathcal{G}$ and $\mathcal{G}'$ be the graph obtained from $\mathcal{G}$ by removing the edges $e_0$ and $\bar{e}_0$.

**Case 1:** $\mathcal{G}'$ is connected. It follows from Bass-Serre theory that $\Gamma = \text{HNN}(H, \Sigma, \theta)$ where $H$ is fundamental group of our graph of groups restricted to $\mathcal{G}'$, $\Sigma = r_{e_0}(\Sigma_{e_0}) < H$ is a subgroup and $\theta: \Sigma \to H$ is given by $\theta = s_{e_0} \circ r_{e_0}^{-1}$. By hypothesis $H$ is countably infinite, $\Sigma$ is finite and, since $\Sigma < \Gamma_{r(e_0)}$ (resp. $\theta(\Sigma) < \Gamma_{s(e_0)}$) is a highly core-free subgroup, $\Sigma < H$ (resp. $\theta(\Sigma) < H$) is also a highly core-free subgroup. Thus we may apply Theorem 4.1 to conclude that $\Gamma \in \mathcal{H}_R$.

**Case 2:** $\mathcal{G}'$ is not connected. Let $\mathcal{G}_1$ and $\mathcal{G}_2$ be the two connected components of $\mathcal{G}'$ such that $s(e_0) \in V(\mathcal{G}_1)$ and $r(e_0) \in V(\mathcal{G}_2)$. Bass-Serre theory implies that $\Gamma = \Gamma_1 *_{\Sigma_{e_0}} \Gamma_2$, where $\Gamma_i$ is the fundamental group of our graph of groups restricted to $\mathcal{G}_i$, $i = 1, 2$, and $\Sigma_{e_0}$ is viewed as a highly core-free subgroup of $\Gamma_1$ via the map $s_{e_0}$ and as a highly core-free subgroup of $\Gamma_2$ via the map $r_{e_0}$ since $s_{e_0}(\Sigma_{e_0})$ is highly core-free in $\Gamma_{s(e_0)}$ and $r_{e_0}(\Sigma_{e_0})$ is highly core-free in $\Gamma_{r(e_0)}$ by hypothesis. Since $\Gamma_1$ and $\Gamma_2$ are countably infinite and $\Sigma_{e_0}$ is finite, we may apply Theorem 3.1 to conclude that $\Gamma \in \mathcal{H}_R$. $\square$

## 6. ACTIONS OF FREE GROUPS ON THE RANDOM GRAPH

Recall that $P(\mathcal{R})$ denotes the set of isomorphisms of $\mathcal{R}$ between finite induced subgraphs $d(\varphi), r(\varphi) \subset V(\mathcal{R})$ and note that $P(\mathcal{R})$ has a natural structure of groupoid.

In this Section, we prove Theorem D. The main tool, called *an elementary extension*, is a refinement of the “back and forth” method used to extend any partial isomorphism $\varphi \in P(\mathcal{R})$ to an automorphism of $\mathcal{R}$.

**6.1. Elementary extensions.** Let $\Phi \subset P(\mathcal{R})$ and $F \subset V(\mathcal{R})$ be finite subsets. Let $\gamma \in \Phi$. We construct a partial isomorphism $\tilde{\gamma} \in P(\mathcal{R})$ which extends $\gamma$ as follows: first, we set

$$K := F \cup \bigcup_{\varphi \in \Phi} (d(\varphi) \cup r(\varphi)), \quad D := K \setminus d(\gamma), \quad R := K \setminus r(\gamma).$$

Note that $D$ and $R$ have the same cardinality and write $D = \{x_1, \dots, x_m\}$ and $R = \{v_1, \dots, v_m\}$. We then successively find vertices $u_1, \dots, u_m \in V(\mathcal{R}) \setminus K$ such that:

* the vertex $u_j$ is adjacent to all vertices $u \in d(\gamma)$ such that $v_j \sim \gamma(u)$ and all vertices $u_{j'}$, with $j' < j$, such that $v_{j'} \sim v_j$;

* it is not adjacent to any other vertices in $K$.

After that, we successively find vertices $y_1, \dots, y_m \in V(\mathcal{R}) \setminus (K \cup \{u_1, \dots, u_m\})$ such that:

* the vertex $y_i$ is adjacent to all vertices $y \in r(\gamma)$ such that $x_j \sim \gamma^{-1}(y)$ and all vertices $y_{i'}$, with $i' < i$, such that $x_{i'} \sim x_i$;

* it is not adjacent to any other vertices in $K$, nor to vertices $u_1, \dots, u_m$.

Finally, since the sets $D = \{x_1, \dots, x_m\}$, $d(\gamma)$, $\{u_1, \dots, u_m\}$ are pairwise disjoint, and the sets $\{y_1, \dots, y_m\}$, $r(\gamma)$, $R = \{v_1, \dots, v_m\}$ are pairwise disjoint, we can define a partial bijection

$$\tilde{\gamma}: K \sqcup \{u_1, \dots, u_m\} \to \{y_1, \dots, y_m\} \sqcup K$$
which extends $\gamma$ by setting $\tilde{\gamma}(x_i) = y_i$ for all $i = 1, \dots, m$, and $\tilde{\gamma}(z) = \gamma(z)$ for all $z \in d(\gamma)$, and $\tilde{\gamma}(u_j) = v_j$ for all $j = 1, \dots, n$.

**Definition 6.1.** The above $\tilde{\gamma}$ is called an *elementary extension* of the triple $(\gamma, \Phi, F)$.

**Proposition 6.2.** Any elementary extension $\tilde{\gamma}$ of $(\gamma, \Phi, F)$ has the following properties:

(1) $\tilde{\gamma} \in P(\mathcal{R})$, that is, $\tilde{\gamma}$ is an isomorphism between finite induced subgraphs;

(2) $F \subset d(\tilde{\gamma}) \cap r(\tilde{\gamma})$, and for all $\varphi \in \tilde{\Phi}$, $d(\varphi) \cup r(\varphi) \subset d(\tilde{\gamma}) \cap r(\tilde{\gamma})$;

(3) The sets $\tilde{\gamma}^{-1}(d(\gamma) \setminus r(\gamma))$, $\tilde{\gamma}(r(\gamma) \setminus d(\gamma))$ and $K$ are pairwise disjoint and $u \not\sim v$, $\forall u \in \tilde{\gamma}^{-1}(d(\gamma) \setminus r(\gamma))$, $\forall v \in \tilde{\gamma}(r(\gamma) \setminus d(\gamma))$;

(4) Let $\tilde{\Phi} := (\Phi \setminus \{\gamma\}) \cup \{\tilde{\gamma}\}$. For any subset $A$ of $\cup_{\varphi \in \tilde{\Phi}}(d(\varphi) \cup r(\varphi))$ let $\Omega$ (resp. $\tilde{\Omega}$) be the orbit of $A$ under the groupoid generated by $\Phi$ (resp. $\tilde{\Phi}$). Then, any edge of $\mathcal{R}$ contained in $\tilde{\Omega} \setminus \Omega$ is the image under $\tilde{\gamma}$ or $\tilde{\gamma}^{-1}$ of an edge in $\Omega$.

*Proof.* (1) It is clear from the construction that $K$ is finite, as it is a finite union of finite sets. Hence, $d(\tilde{\gamma}) = K \sqcup \{u_1, \dots, u_m\}$ and $r(\tilde{\gamma}) = \{y_1, \dots, y_m\} \sqcup K$ are finite. Let us now check that $\tilde{\gamma}$ is an isomorphism between finite induced subgraphs. Notice that one has $d(\tilde{\gamma}) = \{x_1, \dots, x_m\} \sqcup d(\gamma) \sqcup \{u_1, \dots, u_m\}$ and let $u, x \in d(\tilde{\gamma})$. We are going to check that $u \sim x \Leftrightarrow \tilde{\gamma}(u) \sim \tilde{\gamma}(x)$ by distinguishing cases. If $u$ and $x$ are in the same component of the disjoint union $\{x_1, \dots, x_m\} \sqcup d(\gamma) \sqcup \{u_1, \dots, u_m\}$, the equivalence follows readily from the construction and the fact that $\gamma \in P(\mathcal{R})$. If $x \in d(\gamma)$ and $u = u_j$, then $x \sim u_j \Leftrightarrow$ 
$\gamma(x) \sim v_j \Leftrightarrow \tilde{\gamma}(x) \sim \tilde{\gamma}(u_j)$ by the selection of the $u_j$'s. If $x = x_i$ and $u \in d(\gamma)$, then $x_i \sim u \Leftrightarrow y_i \sim \gamma(u) \Leftrightarrow \tilde{\gamma}(x_i) \sim \tilde{\gamma}(u)$ again by the choice of the $y_i$'s. Finally, if $x = x_i$ and $u = u_j$, then $\tilde{\gamma}(u_j) = v_j$ and $\tilde{\gamma}(x_i) = y_i$. It follows from the selection of the $u_j$'s and $y_i$'s that $u_j \not\sim x_i$ and $v_j \not\sim y_i$. Hence the equivalence holds.

(2) It is clear since $F \cup d(\varphi) \cup r(\varphi)$ for $\varphi \in \Phi$ are contained in $K$ and $K \subset d(\tilde{\gamma}) \cap r(\tilde{\gamma})$.

(3) Notice that $\tilde{\gamma}^{-1}(d(\gamma) \setminus r(\gamma)) \subset \{u_1, \dots, u_m\}$ and $\tilde{\gamma}(r(\gamma) \setminus d(\gamma)) \subset \{y_1, \dots, y_m\}$. Therefore the assertion follows from the construction.

(4) Note that $\tilde{\Omega} \setminus \Omega \subset \tilde{\gamma}^{-1}(\Omega \setminus r(\gamma)) \cup \tilde{\gamma}(\Omega \setminus d(\gamma))$. Let $(x, y) \in \tilde{\Omega}^2 \setminus \Omega^2$ such that $x \sim y$. If $x, y \in \tilde{\gamma}(\Omega \setminus d(\gamma))$ or $x, y \in \tilde{\gamma}^{-1}(\Omega \setminus r(\gamma))$ the result is trivial. Note that we cannot have $x \in \tilde{\gamma}(\Omega \setminus d(\gamma))$ and $y \in \tilde{\gamma}^{-1}(\Omega \setminus r(\gamma))$ because otherwise there exists $i$ and $j$ such that $x = y_i$ and $y = u_j$ which implies that $x \not\sim y$. Suppose now that $x \in \tilde{\gamma}(\Omega \setminus d(\gamma))$ and $y \in \Omega$. Then there is some $i$ such that $x = y_i$ but then $y_i \sim y$ implies that $y \in r(\gamma)$ and $\tilde{\gamma}^{-1}(y) \sim \tilde{\gamma}^{-1}(x)$. Since $\tilde{\gamma}^{-1}(y) = \gamma^{-1}(y) \in \Omega$ and $\tilde{\gamma}^{-1}(x) = \tilde{\gamma}^{-1}(y_i) = x_i \in \Omega$, we are done. The other cases are proved in the same way. $\square$

**6.2. "Treezation" of a free group action.** We denote by $\mathbf{F}_k$ the free group on $k$ generators $a_1, \dots, a_k$. Given a tuple $\bar{\alpha} = (\alpha_1, \dots, \alpha_k) \in \mathrm{Aut}(\mathcal{R})^k$, we denote by $\alpha : \mathbf{F}_k \to \mathrm{Aut}(\mathcal{R})$ the unique group homomorphism such that $\alpha(a_j) = \alpha_j$ for all $j$.

In this section, given such a $k$-tuple $\bar{\alpha} \in \mathrm{Aut}(\mathcal{R})^k$ and a finite set $F$ of vertices of $\mathcal{R}$, we explain how to get a $k$-tuple $\bar{\beta} \in \mathrm{Aut}(\mathcal{R})^k$ such that, for all $j$ and $\varepsilon = \pm 1$, the automorphisms $\alpha_j^\varepsilon$ and $\beta_j^\varepsilon$ coincide on $F$, and, informally speaking, the associated Schreier graph (see definition below) looks like a tree far from $F$.
First, we define, for $1 \le j \le k$, the element $\beta_{0,j} \in P(\mathcal{R})$ by the restriction:

$$ \beta_{0,j} := \alpha_j|_{\alpha_j^{-1}(F) \cup F} : \alpha_j^{-1}(F) \cup F \to F \cup \alpha_j(F). $$

Write $\tilde{F} = \bigcup_{j=1}^k (\alpha_j^{-1}(F) \cup F \cup \alpha_j(F)) = \bigcup_{j=1}^k (d(\beta_{0,j}) \cup r(\beta_{0,j}))$. Let $\mathcal{B}_0 \subset P(\mathcal{R})$ be the groupoid generated by $\beta_{0,j}$ for $1 \le j \le k$ and note that, for all $\varphi \in \mathcal{B}_0$, one has $d(\varphi) \cup r(\varphi) \subset \tilde{F}$.

**Remark 6.3.** Suppose that $\alpha$ has all orbits infinite. It implies that for all $x \in \tilde{F}$ there exists $g \in \mathcal{B}_0$ and $1 \le j \le k$ such that $x \in d(g)$ and $gx \notin d(\beta_{0,j}) \cap r(\beta_{0,j})$. Indeed, since the $\alpha$-orbit of $x$ is infinite, there exists $w \in \mathbf{F}_k$ such that $\alpha(w)x \notin \tilde{F}$. Write $w = \alpha_{i_n}^{\epsilon_n} \dots \alpha_{i_1}^{\epsilon_1}$ its reduced expression, where $\epsilon_l \in \{-1, 1\}$. Since $\alpha(w)x \notin \tilde{F}$ it follows that $x \notin d(\beta_{0,i_n}^{\epsilon_n} \dots \beta_{0,i_1}^{\epsilon_1})$. We may and will assume that $x \in d(\beta_{0,i_1}^{\epsilon_1})$ (otherwise the conclusion is obvious). Let $1 \le n_0 \le n-1$ be the largest integer such that $x \in d(\beta_{0,i_{n_0}}^{\epsilon_{n_0}} \dots \beta_{0,i_1}^{\epsilon_1})$. Defining $g = \beta_{0,i_{n_0}}^{\epsilon_{n_0}} \dots \beta_{0,i_1}^{\epsilon_1} \in \mathcal{B}_0$ and $j = i_{n_0+1}$ we reach the conclusion.

Let $V(\mathcal{R}) = \{z_0, z_1, \dots\}$ be an enumeration of $V(\mathcal{R})$ and define inductively $\bar{\beta}_l \in P(\mathcal{R})^k$ by $\bar{\beta}_0 = (\beta_{0,1}, \dots, \beta_{0,k})$ and, if for some $l \ge 0$ the element $\bar{\beta}_l = (\beta_{l,1}, \dots, \beta_{l,k})$ is defined, we denote by $j(l)$ the unique element in $\{1, \dots, k\}$ such that $j(l) \equiv l+1 \pmod k$ and we define $\bar{\beta}_{l+1} = (\beta_{l+1,1}, \dots, \beta_{l+1,k})$ where $\beta_{l+1,j(l)}$ is the elementary extension of the triple $(\beta_{l,j(l)}, \{\beta_{l,1}, \dots, \beta_{l,k}\}, \{z_l\})$ and $\beta_{l+1,j} = \beta_{l,j}$ for $j \ne j(l)$. We will denote by $\mathcal{B}_l \subset P(\mathcal{R})$ the groupoid generated by $\beta_{l,1}, \dots, \beta_{l,k}$.

Define $\bar{\beta} = (\beta_1, \dots, \beta_k) \in \mathrm{Aut}(\mathcal{R})^k$, where $\beta_j$ is (well-) defined by $\beta_j(x) = \beta_{j,l}(x)$ whenever $x \in d(\beta_{j,l})$ (and denote by $\beta : \mathbf{F}_k \to \mathrm{Aut}(\mathcal{R})$ the unique group morphism which maps the $a_j$ onto $\beta_j$).

**Definition 6.4.** The $k$-tuple $\bar{\beta}$ is said to be a *treeization* of $\bar{\alpha}$ relatively to $F$.

We denote by $\mathcal{G}_\beta$ the *Schreier graph of $\beta$*: the vertices are $V(\mathcal{G}_\beta) = V(\mathcal{R})$ and for all $x \in V(\mathcal{G}_\beta)$ we have an oriented edge from $x$ to $\beta_j(x)$ which is decorated by $j^+$ and an oriented edge from $\beta_j^{-1}(x)$ to $x$ decorated by $j^-$.

More generally, given a groupoid $H \subset P(\mathcal{R})$ generated by $\gamma_1, \dots, \gamma_k \in P(\mathcal{R})$, we define $\mathcal{G}_H$ the *Schreier graph of $H$* with the generating tuple $(\gamma_1, \dots, \gamma_k)$ in the following way: $V(\mathcal{G}_H) = V(\mathcal{R})$ and, for all $x \in V(\mathcal{G}_H)$, there is an oriented edge decorated by $j^+$ from $x$ to $\gamma_j(x)$ whenever $x \in d(\gamma_j)$ and there is an oriented edge decorated by $j^-$ from $\gamma_j^{-1}(x)$ to $x$ whenever $x \in r(\gamma_j)$. For all $l \ge 0$, we will denote by $\mathcal{G}_l$ the *Schreier graph of $\mathcal{B}_l$* with the generating tuple $\bar{\beta}_l$.

Given a graph $\mathcal{G}$, for $l \ge 2$, a *minimal path* in $\mathcal{G}$ from $x_1 \in V(\mathcal{G})$ to $x_l \in V(\mathcal{G})$ is a finite sequence of pairwise distinct vertices $x_1, \dots, x_l$ such that $x_i \sim x_{i+1}$ for all $1 \le i \le l-1$. When $l \ge 3$ and $x_1 \sim x_l$, we call it a *minimal cycle*.

Recall that $a_1, \dots, a_k$ are the canonical generators of $\mathbf{F}_k$.

**Proposition 6.5.** Any treeization $\bar{\beta}$ of $\bar{\alpha}$ satisfies the following properties.

(1) For all $l \ge 0$ the minimal cycles in $\mathcal{G}_l$ are all contained in $\tilde{F}$.

(2) The minimal cycles of $\mathcal{G}_\beta$ are all in $\tilde{F}$.

(3) The minimal paths of $\mathcal{G}_\beta$ with extremities in $\tilde{F}$ are contained in $\tilde{F}$.

(4) If the orbits of $\alpha$ are infinite then the orbits of $\beta$ are infinite.
(5) For all $x, y \in \beta(\mathbf{F}_k)(\tilde{F})$, if $(x, y) \in E(\mathcal{R})$ then there exists $x_0, y_0 \in \tilde{F}$ such that $(x_0, y_0) \in E(\mathcal{R})$ and $w \in \mathbf{F}_k$ such that $\beta(w)x_0 = x$ and $\beta(w)(y_0) = y$.

(6) Let $x \in \tilde{F}$ and $w = a_{i_n}^{\epsilon_n} \dots a_{i_1}^{\epsilon_1} \in \mathbf{F}_k$ with its reduced expression, where $\epsilon_l \in \{-1, 1\}$. If there exists $s$ such that $\beta_{is}^{\epsilon_s} \dots \beta_{i_1}^{\epsilon_1} x \notin \tilde{F}$, then for all $s < t \le n$ the path

$$ \beta_{is}^{\epsilon_s} \dots \beta_{i_1}^{\epsilon_1} x, \beta_{is+1}^{\epsilon_{s+1}} \dots \beta_{i_1}^{\epsilon_1} x, \dots, \beta_{in}^{\epsilon_n} \dots \beta_{i_1}^{\epsilon_1} x $$

is a geodesic path in $\mathcal{G}_\beta$ and $d(\beta_{it}^{\epsilon_t} \dots \beta_{i_1}^{\epsilon_1} x, \tilde{F}) = 1 + d(\beta_{i_{t-1}}^{\epsilon_{t-1}} \dots \beta_{i_1}^{\epsilon_1} x, \tilde{F})$ for all $s < t \le n$, where $d$ is the graph distance.

*Proof.* (1) The result is obvious for $\mathcal{G}_0$ since all the edges in $\mathcal{G}_0$ have their source and range in $\tilde{F}$. Now, observe that the edges of $\mathcal{G}_l$ are included in the edges of $\mathcal{G}_{l+1}$ with the same label and any edge of $\mathcal{G}_{l+1}$ which is not already an edge on $\mathcal{G}_l$ has an extremity which is not in any domain or range of any $\beta_{l,j}$ for $1 \le j \le k$ since $\beta_{l+1,j(l)}$ is an elementary extension of $\beta_{l,j(l)}$ and for $j \ne j(l)$ one has $\beta_{l+1,j} = \beta_{j,l}$. Hence, the minimal cycles in $\mathcal{G}_{l+1}$ are contained in $\mathcal{G}_l$. This proves the result by induction on $l$.

(2) It follows from (1) since any minimal cycle in $\mathcal{G}_\beta$ is a minimal cycle in $\mathcal{G}_l$ for some $l \ge 0$.

(3) The proof is the same as the one of (1) and (2).

(4) It follows from (2) that the induced graph structure on the complement of $\tilde{F}$ coming from $\mathcal{G}_\beta$ is a forest. Hence, every $x \notin \tilde{F}$ has an infinite $\beta$-orbit. If $x \in \tilde{F}$, we find, by Remark 6.3, $g \in \mathcal{B}_0$ and $1 \le j \le n$ such that $x \in d(g)$ and $gx \notin d(\beta_{0,j}) \cap r(\beta_{0,j})$. Hence either $\beta_{k,j}(gx) \notin \tilde{F}$ or $\beta_{k,j}^{-1}(gx) \notin \tilde{F}$. In both cases, we find an element $w \in \mathbf{F}_k$ such that $\beta(w)(x) \notin \tilde{F}$. By the first part of the proof, the $\beta$-orbit of $x$ is infinite.

(5) Let $\Omega$ be the orbit of $\tilde{F}$ under the action $\beta$ and, for $l \ge 0$, $\Omega_l$ be the orbit of $\tilde{F}$ under the groupoid $\mathcal{B}_l$. Since every edge of $\mathcal{R}$ which is in $\Omega$ is actually in $\Omega_l$ for some $l$, it suffices to show that, for all $l \ge 0$ and all $x, y \in \Omega_l$ with $(x, y) \in E(\mathcal{R})$, there exists $g \in \mathcal{B}_l$ and $x_0, y_0 \in \tilde{F}$ such that $gx_0 = x$ and $gy_0 = y$. For $l = 0$ it is trivial since $\Omega_0 = \tilde{F}$ and the proof follows by induction by using assertion (4) of Proposition 6.2.

(6) The proof is a direct consequence of the following remark, which is itself a direct consequence of (2) and (3). For all $x \notin \tilde{F}$ in the connected component of a point in $\tilde{F}$ there exist a unique path in $\mathcal{G}_\beta$ without backtracking $x_1, x_2, \dots, x_l$ such that

* $x_1 = x$,

* $x_2, \dots, x_{l-1} \notin \tilde{F}$,

* $x_l \in \tilde{F}$.

Moreover, this path is geodesic.

□

6.3. **Proof of Theorem D.** Let us fix an integer $k \ge 2$. We still denote by $\mathbf{F}_k$ the free group on $k$ generators $a_1, \dots, a_k$, and by $\alpha$ the morphism $\mathbf{F}_k \to \mathrm{Aut}(\mathcal{R})$ associated to some $\bar{\alpha} \in \mathrm{Aut}(\mathcal{R})^k$. Let us mention that one has $\langle \bar{\alpha} \rangle = \{\alpha(w) : w \in \mathbf{F}_k\}$. The set

$$ \mathcal{A} = \{\bar{\alpha} \in \mathrm{Aut}(\mathcal{R})^k : \text{ every } \langle \alpha \rangle\text{-orbit on the vertices is infinite}\} $$
is closed in Aut($\mathcal{R}$)$^k$, which is closed on $S(\mathcal{R})^k$. Thus $\mathcal{A}$ is a Baire space. We also consider the subsets

$$ \mathcal{F} = \{ \bar{\alpha} \in \mathrm{Aut}(\mathcal{R})^k : \alpha \text{ is injective} \}; $$

$$ \mathcal{H} = \{ \bar{\alpha} \in \mathrm{Aut}(\mathcal{R})^k : \alpha \text{ is an homogeneous action on } \mathrm{Aut}(\mathcal{R}) \}. $$

Now, Theorem D can be stated as follows.

**Theorem 6.6.** The subset $\mathcal{A} \cap \mathcal{F} \cap \mathcal{H}$ is a dense $G_\delta$ in $\mathcal{A}$.

*Proof.* Let us prove that $\mathcal{A} \cap \mathcal{H}$ is a dense $G_\delta$ in $\mathcal{A}$. To do this, we observe that $\mathcal{A} \cap \mathcal{H} = \bigcap_{\varphi \in P(\mathcal{R})} (\mathcal{A} \cap \mathcal{H}_\varphi)$, where $\mathcal{H}_\varphi = \{\bar{\alpha} \in \mathrm{Aut}(\mathcal{R})^k : \exists w \in \mathbf{F}_k, \forall x \in d(\varphi), \alpha(w)x = \varphi x\}$. Since the $\mathcal{A} \cap \mathcal{H}_\varphi$'s are all open because the $\mathcal{H}_\varphi$'s are open in $\mathrm{Aut}(\mathcal{R})^k$, it suffices to prove that $\mathcal{A} \cap \mathcal{H}_\varphi$ is dense for all $\varphi \in P(\mathcal{R})$.

Take an arbitrary $\varphi \in P(\mathcal{R})$ and an arbitrary $\bar{\alpha} = (\alpha_1, \dots, \alpha_k) \in \mathcal{A}$. We need to prove that, for any finite subset $F \subset V(\mathcal{R})$, there exists $\bar{\omega} \in \mathcal{A} \cap \mathcal{H}_\varphi$ such that $\alpha_j^{\pm 1}$ and $\omega_j^{\pm 1}$ coincide on $F$ for all $j$. To prove this, we may assume that $F$ contains both $d(\varphi)$ and $r(\varphi)$.

We take such an $F$ and we set $\tilde{F} = \bigcup_{j=1}^k (\alpha_j^{-1}(F) \cup F \cup \alpha_j(F))$ as we did in Section 6.2. Then we take a treezation $\bar{\beta}$ of $\bar{\alpha}$ relatively to $F$. Let us recall that $\beta$ has all orbits infinite since $\alpha$ does, and that, for all $j$, the automorphisms $\beta_j^{\pm 1}$ and $\alpha_j^{\pm 1}$ coincide on $F$.

Recall that (known as Neumann's Lemma [Neu76]), if every orbit of an group action $G \curvearrow X$ in infinite, then for every finite subset $F$ of $X$, there exists $g \in G$ such that $gF \cap F = \emptyset$. Hence, there exists $u \in \mathbf{F}_k$ (we consider it as a reduced word) such that $\beta(u)\tilde{F} \cap \tilde{F} = \emptyset$. Up to replacing $u$ by some $a_j u$, we may assume that $u$ is moreover cyclically reduced. This is possible thanks to Proposition 6.5 (6). Since $u^2$ is reduced, we also have $\beta(u^2)\tilde{F} \cap \tilde{F} = \emptyset$, again by Proposition 6.5 (6).

Let us now show that $\tilde{F}$ and $\beta(u^2)\tilde{F}$ are disconnected, that is, for all $x \in \tilde{F}$ and $y \in \beta(u^2)\tilde{F}$, we have $x \asymp y$. Assume by contradiction that there exists $x \in \tilde{F}$ and $y \in \beta(u^2)\tilde{F}$ such that $x \sim y$. By Proposition 6.5 (5), there exist $x_0, y_0 \in \tilde{F}$ and $v \in \mathbf{F}_k$ such that $x = \beta(v)x_0$ and $y = \beta(v)y_0$. Using Proposition 6.5 (6), we see first that $v = uv'$ (reduced expression) since $y = \beta(v)y_0$ is in $\beta(v)\tilde{F} \cap \beta(u^2)\tilde{F}$, and then that $\beta(v)x_0 = \beta(u)\beta(v')x_0$ is not in $\tilde{F}$. Indeed, if $\beta(v')x_0 \in \tilde{F}$, then $\beta(u)\beta(v')x_0$ is not in $\tilde{F}$, and if $\beta(v')x_0 \notin \tilde{F}$, then $\beta(u)\beta(v')x_0$ is farer from $\tilde{F}$ than $\beta(v')x_0$ in the Schreier graph of $\beta$. Since we have $\beta(v)x_0 \notin \tilde{F}$, $x \in \tilde{F}$ and $x = \beta(v)x_0$, we have obtained a contradiction.

We now set $K = \bigcup_v \beta(v)\tilde{F}$, where the union is taken over the prefixes of $u^2$ (it is the union of trajectories (see Definition 3.1 in [MS13]) of points in $\tilde{F}$ in the Schreier graph of $\beta$) and $\tilde{K} = \bigcup_{j=1}^k (\beta_j^{-1}(K) \cup K \cup \beta_j(K))$. We also consider some integer $s > 10 \mathrm{diam}(\tilde{K})$, with respect to the metric on the Schreier graph of $\beta$, and an index $i$ such that the first letter of $u$ is different from $a_i^{\pm 1}$. Proposition 6.5 ensures that $\beta(a_i^{-s}u^2)\tilde{F}$, $\tilde{K}$ and $\beta(a_i^s u^2)\tilde{F}$ are pairwise disjoint.

Moreover, $\beta(a_i^{-s}u^2)\tilde{F}$ and $\beta(a_i^s u^2)\tilde{F}$ are both disconnected from $\tilde{K}$. Indeed, assume by contradiction that there exist $x \in \tilde{K}$ and $y \in \beta(a_i^s u^2)\tilde{F}$ such that $x \sim y$. By Proposition 6.5 (5), there exist $x_0, y_0 \in \tilde{F}$ and $v \in \mathbf{F}_k$ such that $x = \beta(v)x_0$ and $y = \beta(v)y_0$. On the one hand, using Proposition 6.5 (6), we see first that $v = a_i^s uv'$ (reduced expression) since $y = \beta(v)y_0$
is in $\beta(v)\tilde{F} \cap \beta(a_i^s u^2)\tilde{F}$, and then that the distance (in the Schreier graph of $\beta$) between $\beta(v)x_0$ and $\tilde{F}$ is greater than $10 \operatorname{diam}(\tilde{K})$. Indeed, we get, as above, that $\beta(uv')x_0 \notin \tilde{F}$, and deduce that the distance between $\beta(v)x_0 = \beta(a_i^s)\beta(uv')x_0$ and $\tilde{F}$ is greater than $s$, which is itself greater than $10 \operatorname{diam}(\tilde{K})$. On the other hand, since $x$ is in $\tilde{K}$, its distance is less or equal to $\operatorname{diam}(\tilde{K})$. Hence, we get $x \neq \beta(v)x_0$, a contradiction. This proves that there are no edges between $\tilde{K}$ and $\beta(a_i^s u^2)\tilde{F}$. One gets similarly that there are no edges between $\tilde{K}$ and $\beta(a_i^{-s} u^2)\tilde{F}$.

Thus we can define a partial graph isomorphism $\tau \in P(\mathcal{R})$ as follows: we fix some index $i'$ distinct from $i$ (which exists since $k \ge 2$) and set:

$$ \bullet \ d(\tau) = (\beta_{i'}^{-1}K \cup K) \sqcup \beta(a_i^s u^2)d(\varphi); \quad r(\tau) = (K \cup \beta_{i'}K) \sqcup \beta(a_i^{-s}u^2)r(\varphi); $$

$$ \bullet \text{ for } x \in \beta_{i'}^{-1}K \cup K, \text{ we set } \tau x = \beta_{i'}x; $$

$$ \bullet \text{ for } x \in \beta(a_i^s u^2)d(\varphi), \text{ we set } \tau x = \beta(a_i^{-s} u^2) \circ \varphi \circ \beta(u^{-2}a_i^{-s})x. $$

Note that without the fact that $\beta(a_i^{-s}u^2)\tilde{F}$ and $\beta(a_i^s u^2)\tilde{F}$ are both disconnected from $\tilde{K}$, the map $\tau$ could be only a bijection between vertices.

Now, one can extend $\tau$ to an automorphism $\omega_{i'}$, and set $\omega_j = \beta_j$ for other indices $j$. Then, for all $j$, $\omega_j^{\pm 1}$, $\beta_j^{\pm 1}$ and $\alpha_j^{\pm 1}$ coincide on $F$. Moreover $\beta(a_i^{-s}u^2)$ and $\omega(a_i^{-s}u^2)$ coincide on $F$, and the same holds for $\beta(a_i^s u^2)$ and $\omega(a_i^s u^2)$. Hence, one has

$$ \begin{aligned} \omega(u^{-2}a_i^{-s}a_{i'}a_i^{-s}u^2)x &= \beta(u^{-2}a_i^{-s})\tau\beta(a_i^{-s}u^2)x \\ &= \beta(u^{-2}a_i^{-s})\beta(a_i^s u^2)\varphi\beta(u^{-2}a_i^s)\beta(a_i^{-s}u^2)x = \varphi x \end{aligned} $$

for all $x \in d(\varphi)$. In other words, $\bar{\omega} = (\omega_1, \dots, \omega_k)$ is in $\mathcal{H}_{\varphi}$.

Finally, as $\omega_{i'}$ coincides with $\beta_{i'}^{-1}K \cup K$ and all $\beta_i$-orbits are infinite outside this set, $\omega$ also has all orbits infinite, that is $\bar{\omega}$ is in $\mathcal{A}$. Consequently, we obtain that $\omega$ is in $\mathcal{A} \cap \mathcal{H}_{\varphi}$, which concludes the proof that $\mathcal{A} \cap \mathcal{H}$ is dense $G_{\delta}$ in $\mathcal{A}$. One can use a similar, but much easier, argument to show that $\mathcal{A} \cap \mathcal{F}$ is a dense $G_{\delta}$ in $\mathcal{A}$. This is left to the reader. $\square$

## REFERENCES

[BM05] M. Bhattacharjee and H.D. Macpherson, A locally finite dense group acting on the random graph, *Forum Math.* **17** (2005) 513–517.

[Ca96] P. J. Cameron, Cofinitary permutation groups, *Bull. London Math. Soc.* **28** (1996) 1–17.

[Ca97] P. J. Cameron, The random graph, The mathematics of Paul Erdős, II, *Algorithms Combin.* **14**, Springer, Berlin (1997) 333–351.

[Ca99] P.J. Cameron, Permutation groups, *London Mathematical Society Student Texts.* **45** Cambridge University Press, Cambridge (1999).

[Dr85] M. Droste, Structure of partially ordered sets with transitive automorphism group, *Mem. Amer. Math. Soc.* **334** (1985).

[ER63] P. Erdős and A. Rényi. Asymmetric graphs, *Acta Math. Acad. Sci. Hungar.* **14** (1963) 295–315.

[FMS15] P. Fima, S. Moon and Y. Stalder. Highly transitive actions of groups acting on trees, *Proc. Amer. Math. Soc.* **143** (2015) 5083–5094.

[GMR93] A. M. W. Glass, S. H. McCleary and M. Rubin, Automorphism groups of countable highly homogeneous partially ordered sets, *Math. Z.* **214** (1993) 55–66.

[GK03] P.M. Gartside and R.W. Knight, Ubiquity of free groups, *Bull. Lond. Math. Soc.* **35** (2003) 624–634.

[GS15] S. Glaband and F. Strobin, Large free subgroups of automorphisms groups of ultrahomogeneous spaces, *Colloq. Math.* **140** (2015) 279–295.

[Ka92] R. Kaye, The automorphism group of a countable recursive saturated structure, *Proc. London Math. Soc.* (3) **65** (1992) 225–244.

[Mac11] H.D. Macpherson, A survey of homogeneous structures. *Discrete Math.* (15) **311** (2011) 1599–1634.
[Mac86] H.D. Macpherson, Groups of automorphisms of $\mathbb{Z}_0$-categorical structures, Quart. J. Math. (2) **37** (1986) 449–465.

[MS94] G. Melles and S. Shelah, Aut(M) has a large dense free subgroup for saturated M, *Bull. London Math. Soc.* **26** (1994), 339–344.

[MS13] S. Moon and Y. Stalder, Highly transitive actions of free products, *Algebr. Geom. Topol.* **13** (2013) 589–607.

[Neu76] P. M. Neumann, The structure of finitary permutation groups, *Arch. Math.* **27** (1976) 3–17.

[Ra64] R. Rado, Universal graphs and universal functions, *Acta Arith.* **9** (1964) 393–407.

[Se77] J.-P. Serre, Arbres, amalgames, $SL_2$, *Astérisque* **46**, Société Mathématique de France (1977).

[Tr85] J. K. Truss, The group of the countable universal graph, *Math. Proc. Cambridge Philos. Soc.* **98** (1985) 213–245.

PIERRE FIMA

UNIVERSITÉ DE PARIS, SORBONNE UNIVERSITÉ, CNRS, INSTITUT DE MATHÉMATIQUES DE JUSSIEU-PARIS
RIVE GAUCHE, F-75013, PARIS, FRANCE.

Email address: pierre.fima@imj-prg.fr

SOYOUNG MOON

UNIVERSITÉ DE BOURGOGNE, INSTITUT MATHÉMATIQUES DE BOURGOGNE, UMR 5584 CNRS, BP 47870,
21078 DIJON CEDEX FRANCE

Email address: soyoung.moon@u-bourgogne.fr

YVES STALDER

UNIVERSITÉ CLERMONT AUVERGNE, CNRS, LMBP, F-63000 CLERMONT-FERRAND, FRANCE

Email address: yves.stalder@uca.fr