# Density of random subsets and applications to group theory

Tsung-Hsuan Tsai

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

► To cite this version:

Tsung-Hsuan Tsai. Density of random subsets and applications to group theory. Journal of Combinatorial Algebra, 2021, 6 (3), pp.223-263. 10.4171/JCA/63. hal-03242300

HAL Id: hal-03242300

https://hal.science/hal-03242300

Submitted on 29 May 2024

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_2.png" /></figure>
# Density of random subsets and applications to group theory

Tsung-Hsuan Tsai

► To cite this version:

Tsung-Hsuan Tsai. Density of random subsets and applications to group theory. Journal of Combinatorial Algebra, 2021, 6 (3), pp.223-263. 10.4171/JCA/63. hal-03242300

HAL Id: hal-03242300

https://hal.science/hal-03242300v1

Submitted on 29 May 2024

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>
# Density of random subsets and applications to group theory

Tsung-Hsuan Tsai

**Abstract.** Developing an idea of M. Gromov (1993), we study the intersection formula for random subsets with density. The *density* of a subset *A* in a finite set *E* is defined by $\text{dens } A := \log_{|E|}(|A|)$. The aim of this article is to give a precise meaning of Gromov's *intersection formula*: "Random subsets" *A* and *B* of a finite set *E* satisfy $\text{dens}(A \cap B) = \text{dens } A + \text{dens } B - 1$.

As an application, we exhibit a phase transition phenomenon for random presentations of groups at density $\lambda/2$ for any $0 < \lambda < 1$, characterizing the $C'(\lambda)$-small cancellation condition. We also improve an important result of random groups by G. Arzhantseva and A. Ol'shanskii (1996) from density 0 to density $0 \le d < 1/(120m^2 \ln(2m))$.

## Introduction

**Density of subsets.** Let *A* be a subset of a finite set *E*. Denote $|E|$, $|A|$ their cardinalities. In [9, Section 9.A], M. Gromov defined the *density* of *A* in *E* as

$$ \text{dens}_E(A) := \log_{|E|}(|A|). $$

Namely, $\text{dens}_E(A)$ is the number $d \in \{-\infty\} \cup [0, 1]$ such that $|A| = |E|^d$. Note that $d = -\infty$ if and only if $A = \emptyset$. If the set *E* is fixed, we omit the subscript and simply denote the density by $\text{dens } A$.

In [9, p. 270], the *intersection formula* is stated as follows: *Random subsets A and B of a finite set E satisfy*

$$ \text{dens}(A \cap B) = \text{dens } A + \text{dens } B - 1 $$

with the convention

$$ \text{dens } A < 0 \iff A = \emptyset. $$

If *E* is a finite-dimensional vector space over a finite field, every affine subspace *A* satisfies $\text{dens } A = \text{dim } A / \text{dim } E$. The intersection formula is then a “random subset

<footnote n="2020">2020 Mathematics Subject Classification. Primary 60C05; Secondary 20F05, 20F06.</footnote>

<footnote>Keywords. Random group, intersection formula, cancellation theory.</footnote>
# Density of random subsets and applications to group theory

Tsung-Hsuan Tsai

**Abstract.** Developing an idea of M. Gromov (1993), we study the intersection formula for random subsets with density. The density of a subset $A$ in a finite set $E$ is defined by $\text{dens } A := \log_{|E|}(|A|)$. The aim of this article is to give a precise meaning of Gromov’s intersection formula: “Random subsets” $A$ and $B$ of a finite set $E$ satisfy $\text{dens}(A \cap B) = \text{dens } A + \text{dens } B - 1$.

As an application, we exhibit a phase transition phenomenon for random presentations of groups at density $\lambda/2$ for any $0 < \lambda < 1$, characterizing the $C'(\lambda)$-small cancellation condition. We also improve an important result of random groups by G. Arzhantseva and A. Ol’shanskii (1996) from density 0 to density $0 \le d < 1/(120m^2 \ln(2m))$.

## Introduction

**Density of subsets.** Let $A$ be a subset of a finite set $E$. Denote $|E|$, $|A|$ their cardinalities. In [9, Section 9.A], M. Gromov defined the density of $A$ in $E$ as

$$ \text{dens}_E(A) := \log_{|E|}(|A|). $$

Namely, $\text{dens}_E(A)$ is the number $d \in \{-\infty\} \cup [0, 1]$ such that $|A| = |E|^d$. Note that $d = -\infty$ if and only if $A = \emptyset$. If the set $E$ is fixed, we omit the subscript and simply denote the density by $\text{dens } A$.

In [9, p. 270], the intersection formula is stated as follows: Random subsets $A$ and $B$ of a finite set $E$ satisfy

$$ \text{dens}(A \cap B) = \text{dens } A + \text{dens } B - 1 $$

with the convention

$$ \text{dens } A < 0 \iff A = \emptyset. $$

If $E$ is a finite-dimensional vector space over a finite field, every affine subspace $A$ satisfies $\text{dens } A = \dim A / \dim E$. The intersection formula is then a “random subset

<footnote n="2020">2020 Mathematics Subject Classification. Primary 60C05; Secondary 20F05, 20F06.</footnote>

<footnote>Keywords. Random group, intersection formula, cancellation theory.</footnote>
version” of the well-known result for affine subspaces: *Transversal affine subspaces A and B of a vector space E satisfy*

$$ \dim(A \cap B) = \dim A + \dim B - \dim E $$

with the convention

$$ \dim A < 0 \iff A = \emptyset. $$

**Purpose of the paper.** In [9, p. 270], Gromov’s “explanation” did not give a precise definition of a random subset with density, neither a proof of the intersection formula. In [9, p. 272], he proposed that one can consider the class of random subsets defined by measures invariant under the permutations of E.

In this article, we discuss two basic models of random subsets that are contained in the permutation invariant model: The uniform density model and the Bernoulli density model. The first one is defined by the uniform distribution on all subsets of E with cardinality $|\{|E|^d\}|$. This model is used by Y. Ollivier in [14, 15, 17] to study the density model of random groups, and by A. Żuk in [19] to construct random triangular groups. For the Bernoulli density model, every element in E is taken independently with the same probability $|E|^{d-1}$. This model is considered by Antoniuk–Łuczak–Świątkowski in [1] to study random triangular groups.

The aim of this article is to establish a general framework for the study of random subsets with densities, and to prove the intersection formula for the class of random subsets that are densable and permutation invariant.

**Random subsets and the intersection formula.** In the first section, we introduce the notion of densable sequences of random subsets. Let E be a finite set. A random subset of E is a $\mathcal{P}(E)$-valued random variable, where $\mathcal{P}(E)$ is the set of subsets of E. Note that $|A|$ is a usual real-valued random variable. The density of A in E, defined by $\text{dens}_E A := \log_{|E|}(|A|)$, is hence a random variable with values in $\{-\infty\} \cup [0, 1]$.

As our approach is asymptotic when $|E| \to \infty$, we consider a sequence of finite sets $E = (E_n)_{n \in \mathbb{N}}$ where $|E_n| \to \infty$. A sequence of random subsets of E is a sequence $A = (A_n)$ where $A_n$ is a random subset of $E_n$ for all $n \in \mathbb{N}$. Such a sequence is densable with density $d \in \{-\infty\} \cup [0, 1]$ if the sequence of random variables $\text{dens}_{E_n}(A_n)$ converges weakly (i.e. converges in distribution) to the constant $d$ (cf. [9, p. 272]). For a sequence of properties $Q = (Q_n)$, we say that $Q_n$ is asymptotically almost surely (a.a.s.) satisfied if the probability that $Q_n$ is satisfied goes to 1 when $n \to \infty$. For example, for a sequence of random subsets $A = (A_n)$, $\text{dens} A = -\infty$ if and only if a.a.s. $A_n = \emptyset$.

In Section 2, we work on the permutation invariant model in [9, p. 272]. Let E be a finite set. A random subset A of E is permutation invariant if its law is invariant under the permutations of E. Namely, for any subset $a \in \mathcal{P}(E)$ and any permutation $\sigma \in S(E)$, we have $\text{Pr}(A = a) = \text{Pr}(A = \sigma(a))$.
version” of the well-known result for affine subspaces: *Transversal affine subspaces A and B of a vector space E satisfy*

$$ \dim(A \cap B) = \dim A + \dim B - \dim E $$

with the convention

$$ \dim A < 0 \iff A = \emptyset. $$

**Purpose of the paper.** In [9, p. 270], Gromov’s “explanation” did not give a precise definition of a random subset with density, neither a proof of the intersection formula. In [9, p. 272], he proposed that one can consider the class of random subsets defined by measures invariant under the permutations of E.

In this article, we discuss two basic models of random subsets that are contained in the permutation invariant model: The uniform density model and the Bernoulli density model. The first one is defined by the uniform distribution on all subsets of E with cardinality $|\{|E|^d\}|$. This model is used by Y. Ollivier in [14, 15, 17] to study the density model of random groups, and by A. Żuk in [19] to construct random triangular groups. For the Bernoulli density model, every element in E is taken independently with the same probability $|E|^{d-1}$. This model is considered by Antoniuk-Łuczak-Świątkowski in [1] to study random triangular groups.

The aim of this article is to establish a general framework for the study of random subsets with densities, and to prove the intersection formula for the class of random subsets that are densable and permutation invariant.

**Random subsets and the intersection formula.** In the first section, we introduce the notion of densable sequences of random subsets. Let E be a finite set. A random subset of E is a $\mathcal{P}(E)$-valued random variable, where $\mathcal{P}(E)$ is the set of subsets of E. Note that $|A|$ is a usual real-valued random variable. The density of A in E, defined by $\text{dens}_E A := \log_{|E|}(|A|)$, is hence a random variable with values in $\{-\infty\} \cup [0, 1]$.

As our approach is asymptotic when $|E| \to \infty$, we consider a sequence of finite sets $E = (E_n)_{n \in \mathbb{N}}$ where $|E_n| \to \infty$. A sequence of random subsets of E is a sequence $A = (A_n)$ where $A_n$ is a random subset of $E_n$ for all $n \in \mathbb{N}$. Such a sequence is densable with density $d \in \{-\infty\} \cup [0, 1]$ if the sequence of random variables $\text{dens}_{E_n}(A_n)$ converges weakly (i.e. converges in distribution) to the constant $d$ (cf. [9, p. 272]). For a sequence of properties $Q = (Q_n)$, we say that $Q_n$ is asymptotically almost surely (a.a.s.) satisfied if the probability that $Q_n$ is satisfied goes to 1 when $n \to \infty$. For example, for a sequence of random subsets $A = (A_n)$, $\text{dens} A = -\infty$ if and only if a.a.s. $A_n = \emptyset$.

In Section 2, we work on the permutation invariant model in [9, p. 272]. Let E be a finite set. A random subset A of E is permutation invariant if its law is invariant under the permutations of E. Namely, for any subset $a \in \mathcal{P}(E)$ and any permutation $\sigma \in S(E)$, we have $\text{Pr}(A = a) = \text{Pr}(A = \sigma(a))$.
Consider a sequence of finite sets $E = (E_n)$ with $|E_n| \to \infty$. Denote by $\mathcal{D}(E)$ the class of densable sequences of permutation invariant random subsets of $E$. We prove the intersection formula stated as follows:

**Theorem 1** (The intersection formula, Theorem 2.9). Let $A = (A_n)$, $B = (B_n)$ be independent sequences of random subsets in $\mathcal{D}(E)$ with densities $\alpha, \beta$. If $\alpha + \beta \neq 1$, then the sequence of random subsets $A \cap B$ is also in $\mathcal{D}(E)$. In addition:

$$ \text{dens}(A \cap B) = \begin{cases} \alpha + \beta - 1 & \text{if } \alpha + \beta > 1, \\ -\infty & \text{if } \alpha + \beta < 1. \end{cases} $$

The density $-\infty$ means that a.a.s. the random subset is empty.

In Section 3, we study the intersection between a random subset and a fixed subset. We develop a generalized form: the multi-dimensional intersection formula. Let $E = (E_n)$ be a sequence of finite sets with $|E_n| \to \infty$. Denote $E_n^{(k)}$ the set of pairwise distinct $k$-tuples of the set $E_n$. Let $A$ be a sequence of random subsets in $\mathcal{D}(E)$ (densable and permutation invariant). We are interested in the intersection between $A^{(k)}$ and a densable sequence of subsets $X$ of $E^{(k)}$.

For $k \ge 2$, the intersection formula is in general not correct (see Example 3.3). We show that by an additional self-intersection condition on $X$, we can achieve an intersection formula.

**Theorem 2** (The multi-dimensional intersection formula, Theorem 3.7). Let $A = (A_n)$ be a sequence of random subsets in $\mathcal{D}(E)$ with density $0 < d < 1$. Let $X = (X_n)$ be a densable sequence of fixed subsets of $E^{(k)}$ with density $\alpha$.

(i) If $d + \alpha < 1$, then a.a.s.

$$ A_n^{(k)} \cap X_n = \emptyset. $$

(ii) If $d + \alpha > 1$ and $X$ satisfies the $d$-small self intersection condition (Definition 3.6), then the sequence of random subsets $A^{(k)} \cap X$ is densable and

$$ \text{dens}(A^{(k)} \cap X) = \alpha + d - 1. $$

The intersection formula in $E$ between a random subset and a fixed subset is a special case of this theorem by taking $k = 1$.

**Applications to group theory: Random groups.** The last section is dedicated to applications to group theory, more precisely to small cancellation theory.

The first mention of generic property for finitely presented groups appears in the late '80s, in the works of V. S. Guba [10, Remark 2] and M. Gromov [8, Section 0.2]. In [10], the author showed that for "almost every" group presented by $m \ge 4$ generators and one "long" relator, any 2-generated subgroup is free. In [8, Section 0.2],
Consider a sequence of finite sets $E = (E_n)$ with $|E_n| \to \infty$. Denote by $\mathcal{D}(E)$ the class of densable sequences of permutation invariant random subsets of $E$. We prove the intersection formula stated as follows:

**Theorem 1** (The intersection formula, Theorem 2.9). Let $A = (A_n)$, $B = (B_n)$ be independent sequences of random subsets in $\mathcal{D}(E)$ with densities $\alpha, \beta$. If $\alpha + \beta \neq 1$, then the sequence of random subsets $A \cap B$ is also in $\mathcal{D}(E)$. In addition:

$$ \text{dens}(A \cap B) = \begin{cases} \alpha + \beta - 1 & \text{if } \alpha + \beta > 1, \\ -\infty & \text{if } \alpha + \beta < 1. \end{cases} $$

The density $-\infty$ means that a.a.s. the random subset is empty.

In Section 3, we study the intersection between a random subset and a fixed subset. We develop a generalized form: the multi-dimensional intersection formula. Let $E = (E_n)$ be a sequence of finite sets with $|E_n| \to \infty$. Denote $E_n^{(k)}$ the set of pairwise distinct $k$-tuples of the set $E_n$. Let $A$ be a sequence of random subsets in $\mathcal{D}(E)$ (densable and permutation invariant). We are interested in the intersection between $A^{(k)}$ and a densable sequence of subsets $X$ of $E^{(k)}$.

For $k \ge 2$, the intersection formula is in general not correct (see Example 3.3). We show that by an additional self-intersection condition on $X$, we can achieve an intersection formula.

**Theorem 2** (The multi-dimensional intersection formula, Theorem 3.7). Let $A = (A_n)$ be a sequence of random subsets in $\mathcal{D}(E)$ with density $0 < d < 1$. Let $X = (X_n)$ be a densable sequence of fixed subsets of $E^{(k)}$ with density $\alpha$.

(i) If $d + \alpha < 1$, then a.a.s.

$$ A_n^{(k)} \cap X_n = \emptyset. $$

(ii) If $d + \alpha > 1$ and $X$ satisfies the $d$-small self intersection condition (Definition 3.6), then the sequence of random subsets $A^{(k)} \cap X$ is densable and

$$ \text{dens}(A^{(k)} \cap X) = \alpha + d - 1. $$

The intersection formula in $E$ between a random subset and a fixed subset is a special case of this theorem by taking $k = 1$.

**Applications to group theory: Random groups.** The last section is dedicated to applications to group theory, more precisely to small cancellation theory.

The first mention of generic property for finitely presented groups appears in the late '80s, in the works of V. S. Guba [10, Remark 2] and M. Gromov [8, Section 0.2]. In [10], the author showed that for "almost every" group presented by $m \ge 4$ generators and one "long" relator, any 2-generated subgroup is free. In [8, Section 0.2],
Gromov defined two models of random group presentations with fixed number of generators and relators.

In 1993, Gromov introduced the *density model* of random groups in [9, Section 9.B]. The number of generators is still fixed, but the number of relators *grows exponentially* with the length of the relators, determined by a density parameter *d*. A *phase transition phenomenon* is then stated as follows: if *d* < 1/2, then a.a.s. the random group is infinite hyperbolic; whereas if *d* > 1/2, then a.a.s. the random group is trivial.

In a 1996 paper [5], G. Arzhantseva and A. Ol'shanskii generalized Guba's result. They proved that for "almost every" group presented by $m \ge 2$ generators and $k \ge 1$ long relators, any $(m-1)$-generated subgroup is free. In their model, the number of generators $k$ is fixed, as in Gromov's 1987 model [8, Section 0.2]. This model is called the Arzhantsev–Ol'shanskii model, or the *few relator model* of random groups.

For more detailed surveys on random groups, see (in chronological order) [7] by E. Ghys, [16] by Y. Ollivier, [12] by I. Kapovich and P. Schupp and [6] by F. Bassino, C. Nicaud and P. Weil.

Fix a set of alphabets $X = \{x_1, \dots, x_m\}$ as generators of groups. Denote by $B_\ell$ the set of cyclically reduced words of $X^\pm$ of lengths at most $\ell$. If $S_\ell$ is the set of cyclically reduced words of length exactly $\ell$, it is clear that

$$2m(2m-1)^{\ell-2}(2m-2) \le |S_\ell| \le 2m(2m-1)^{\ell-1}.$$

So,

$$\frac{2m}{2m-1}[(2m-1)^{\ell}-1] \le |B_{\ell}| \le \frac{2m}{2m-2}[(2m-1)^{\ell}-1].$$

As we are interested in asymptotic behaviors when $\ell \to \infty$, we can write $|B_\ell| = (2m-1)^{\ell+O(1)}$. Consider $\mathbf{B} = (B_\ell)_{\ell \ge 1}$ as our ambient sequence of sets. Let $d \in \{-\infty\} \cup [0, 1]$. A *sequence of random groups* with density $d$, denoted by $\mathbf{G}(m, d) = (G_\ell(m, d))$, is defined by random presentations $G_\ell(m, d) = \langle X | R_\ell \rangle$ where $R = (R_\ell)$ is a densable sequence of permutation invariant random subsets of $\mathbf{B}$ with density $d$.

The first mention of the $\lambda/2$ phase transition for the $C'(\lambda)$-small cancellation condition is by Gromov in [9, p. 273], showing that if $2d < \lambda$ then a random group at density $d$ satisfies $C'(\lambda)$. He remarked also that, in particular, if $d < 1/12$ then the group is hyperbolic; and if $d > 1/12$ then the group is not $C'(1/6)$. Ollivier-Wise gave a detailed proof of $d < \lambda/2$ implying $C'(\lambda)$ in [18, Proposition 1.8]. In [16, p. 31], Ollivier stated the phase transition : if $d > \lambda/2$ then $C'(\lambda)$ does not hold. However, his "dimension reasoning" is the 2-dimensional intersection formula between a random subset (pairs of distinct relators in a random group) and a fixed subset (pairs of distinct relators denying $C'(\lambda)$), which does not hold in general (as Example 3.3 shows).
Gromov defined two models of random group presentations with fixed number of generators and relators.

In 1993, Gromov introduced the *density model* of random groups in [9, Section 9.B]. The number of generators is still fixed, but the number of relators *grows exponentially* with the length of the relators, determined by a density parameter *d*. A *phase transition phenomenon* is then stated as follows: if *d* < 1/2, then a.a.s. the random group is infinite hyperbolic; whereas if *d* > 1/2, then a.a.s. the random group is trivial.

In a 1996 paper [5], G. Arzhantseva and A. Ol'shanskii generalized Guba's result. They proved that for "almost every" group presented by $m \ge 2$ generators and $k \ge 1$ long relators, any $(m-1)$-generated subgroup is free. In their model, the number of generators $k$ is fixed, as in Gromov's 1987 model [8, Section 0.2]. This model is called the Arzhantsev–Ol'shanskii model, or the *few relator model* of random groups.

For more detailed surveys on random groups, see (in chronological order) [7] by E. Ghys, [16] by Y. Ollivier, [12] by I. Kapovich and P. Schupp and [6] by F. Bassino, C. Nicaud and P. Weil.

Fix a set of alphabets $X = \{x_1, \dots, x_m\}$ as generators of groups. Denote by $B_\ell$ the set of cyclically reduced words of $X^\pm$ of lengths at most $\ell$. If $S_\ell$ is the set of cyclically reduced words of length exactly $\ell$, it is clear that

$$2m(2m-1)^{\ell-2}(2m-2) \le |S_\ell| \le 2m(2m-1)^{\ell-1}.$$

So,

$$\frac{2m}{2m-1}[(2m-1)^{\ell}-1] \le |B_{\ell}| \le \frac{2m}{2m-2}[(2m-1)^{\ell}-1].$$

As we are interested in asymptotic behaviors when $\ell \to \infty$, we can write $|B_\ell| = (2m-1)^{\ell+O(1)}$. Consider $\mathbf{B} = (B_\ell)_{\ell \ge 1}$ as our ambient sequence of sets. Let $d \in \{-\infty\} \cup [0, 1]$. A *sequence of random groups* with density $d$, denoted by $\mathbf{G}(m, d) = (G_\ell(m, d))$, is defined by random presentations $G_\ell(m, d) = \langle X | R_\ell \rangle$ where $R = (R_\ell)$ is a densable sequence of permutation invariant random subsets of $\mathbf{B}$ with density $d$.

The first mention of the $\lambda/2$ phase transition for the $C'(\lambda)$-small cancellation condition is by Gromov in [9, p. 273], showing that if $2d < \lambda$ then a random group at density $d$ satisfies $C'(\lambda)$. He remarked also that, in particular, if $d < 1/12$ then the group is hyperbolic; and if $d > 1/12$ then the group is not $C'(1/6)$. Ollivier-Wise gave a detailed proof of $d < \lambda/2$ implying $C'(\lambda)$ in [18, Proposition 1.8]. In [16, p. 31], Ollivier stated the phase transition : if $d > \lambda/2$ then $C'(\lambda)$ does not hold. However, his "dimension reasoning" is the 2-dimensional intersection formula between a random subset (pairs of distinct relators in a random group) and a fixed subset (pairs of distinct relators denying $C'(\lambda)$), which does not hold in general (as Example 3.3 shows).
Bassino–Nicaud–Weil gave a proof of $d > \lambda/2$ implying non-$C'(\lambda)$ in [6, Theorem 2.1]. Their argument showed that the pairs of distinct relators in a random group denying $C'(\lambda)$ is not empty, but did not give its density.

The $d$-small self-intersection condition (Definition 3.6) for a fixed subset is introduced to rule out this difficulty. By the multi-dimensional intersection formula (Theorem 2), we show that if $d > \lambda/2$, then the pairs of distinct relators in a random group denying $C'(\lambda)$ is with density $d - \lambda/2$ and hence not empty.

**Theorem 3** (Phase transition at density $\lambda/2$, Theorem 4.3). Let $G(m, d)=(G_\ell(m, d))$ be a random group with $m$ generators and with density $d$. Let $\lambda \in ]0, 1[$.

(1) If $d < \lambda/2$, then a.a.s. $G_\ell(m, d)$ satisfies $C'(\lambda)$.

(2) If $d > \lambda/2$, then a.a.s. $G_\ell(m, d)$ does not satisfy $C'(\lambda)$.

It was given as an “interesting problem” in [16, Section I.3.c] that some algebraic properties of random groups at density 0 (see [5] by Arzhantseva–Ol’shanskii, [2–4] by Arzhantseva, and [11] by Kapovich–Schupp) may extend to some positive density $d$. In [12, Theorem 7.5], Kapovich and Schupp extends Arzhantzeva’s “all $L$-generated subgroups of infinite index are free” result [2] (for a fixed $L > 0$) to some density $d > 0$ independent of $m$. A property is called “low-density random” by Kapovich–Schupp in [12, p. 3] if the corresponding density $d(m)$ is positive but converges to 0 when $m$ goes to infinity. They claimed that Arzhantseva–Ol’shanskii’s “all $(m-1)$-generated subgroups are free” result [5] is a low-density random property ([12, Theorems 1.1 (2) and 5.4 (2))], but the density $d(m)$ is not given.

In our study, the number of generators $m$ is fixed, and we look for a density $d(m)$ such that the “all $(m-1)$-generated subgroups are free” property holds for a random group with $m$ generators of density $d < d(m)$. Using Theorems 2 and 3, we give an explicit bound $d(m) = 1/(120m^2 \ln(2m))$ that extends Arzhantseva–Ol’shanskii’s result in [5] from density 0 to density $0 \le d < d(m)$.

**Theorem 4** (Every $(m-1)$-generated subgroup is free, Theorem 4.5). Let $(G_\ell(m, d))$ be a sequence of random groups with $m$ generators and with density

$$0 \le d < \frac{1}{120m^2 \ln(2m)}.$$

Then a.a.s. every $(m-1)$-generated subgroup of $G_\ell(m, d)$ is free.

Ollivier remarked in [16, p. 71] that at density $d > 1 - \log_{2m-1}(2m-3)$, the rank of a random group with $m$ generators with density $d$ is at most $m-1$, so the “all $(m-1)$-generated subgroups are free” property fails. There is still a large gap between $\log_{2m-1}(2m-3) \sim 1/(m \ln(2m))$ and $1/(120m^2 \ln(2m))$.
Bassino-Nicaud-Weil gave a proof of $d > \lambda/2$ implying non-$C'(\lambda)$ in [6, Theorem 2.1]. Their argument showed that the pairs of distinct relators in a random group denying $C'(\lambda)$ is not empty, but did not give its density.

The $d$-small self-intersection condition (Definition 3.6) for a fixed subset is introduced to rule out this difficulty. By the multi-dimensional intersection formula (Theorem 2), we show that if $d > \lambda/2$, then the pairs of distinct relators in a random group denying $C'(\lambda)$ is with density $d - \lambda/2$ and hence not empty.

**Theorem 3** (Phase transition at density $\lambda/2$, Theorem 4.3). Let $G(m, d)=(G_\ell(m, d))$ be a random group with $m$ generators and with density $d$. Let $\lambda \in ]0, 1[$.

(1) If $d < \lambda/2$, then a.a.s. $G_\ell(m, d)$ satisfies $C'(\lambda)$.

(2) If $d > \lambda/2$, then a.a.s. $G_\ell(m, d)$ does not satisfy $C'(\lambda)$.

It was given as an “interesting problem” in [16, Section I.3.c] that some algebraic properties of random groups at density 0 (see [5] by Arzhantseva-Ol’shanskii, [2–4] by Arzhantseva, and [11] by Kapovich-Schupp) may extend to some positive density $d$. In [12, Theorem 7.5], Kapovich and Schupp extends Arzhantzeva’s “all $L$-generated subgroups of infinite index are free” result [2] (for a fixed $L > 0$) to some density $d > 0$ independent of $m$. A property is called “low-density random” by Kapovich-Schupp in [12, p. 3] if the corresponding density $d(m)$ is positive but converges to 0 when $m$ goes to infinity. They claimed that Arzhantseva-Ol’shanskii’s “all $(m-1)$-generated subgroups are free” result [5] is a low-density random property ([12, Theorems 1.1 (2) and 5.4 (2)]), but the density $d(m)$ is not given.

In our study, the number of generators $m$ is fixed, and we look for a density $d(m)$ such that the “all $(m-1)$-generated subgroups are free” property holds for a random group with $m$ generators of density $d < d(m)$. Using Theorems 2 and 3, we give an explicit bound $d(m) = 1/(120m^2 \ln(2m))$ that extends Arzhantseva-Ol’shanskii’s result in [5] from density 0 to density $0 \le d < d(m)$.

**Theorem 4** (Every $(m-1)$-generated subgroup is free, Theorem 4.5). Let $(G_\ell(m, d))$ be a sequence of random groups with $m$ generators and with density

$$0 \le d < \frac{1}{120m^2 \ln(2m)}.$$

Then a.a.s. every $(m-1)$-generated subgroup of $G_\ell(m, d)$ is free.

Ollivier remarked in [16, p. 71] that at density $d > 1 - \log_{2m-1}(2m-3)$, the rank of a random group with $m$ generators with density $d$ is at most $m-1$, so the “all $(m-1)$-generated subgroups are free” property fails. There is still a large gap between $\log_{2m-1}(2m-3) \sim 1/(m \ln(2m))$ and $1/(120m^2 \ln(2m))$.
# 1. Definitions and basic models

## 1.1. Densable sequences of random subsets

Let $E$ be a finite set, denote $|E|$ its cardinality. The following definition is due to M. Gromov in [9, p. 269].

**Definition 1.1.** Let $E$ be a finite non-empty set and $A \subset E$. The density of $A$ in $E$ is defined by

$$ \operatorname{dens}_E A := \log_{|E|} |A| = \frac{\log |A|}{\log |E|}. $$

So that $d \in [0, 1] \cup \{-\infty\}$ is a real number such that $|E|^d = |A|$.

We will omit the subscript $E$ if the set is fixed and simply denote the density by $\operatorname{dens} A$. Note that $\operatorname{dens} A = -\infty$ if and only if $A = \emptyset$.

**Definition 1.2.** Let $E$ be a finite set. Denote $\mathcal{P}(E)$ the set of subsets of $E$. A random subset $A$ of $E$ is a $\mathcal{P}(E)$-valued random variable.

In this article, we use upper-case letters $A, B, C, \dots$ to denote random subsets and lower-case letters $a, b, c, \dots$ to denote fixed subsets. The law of a random subset $A$ is determined by instances $\mathbf{Pr}(A = a)$ through all subsets $a \in \mathcal{P}(E)$ (or $a \subset E$). Its cardinality $|A|$ is a usual real-valued random variable.

**Example 1.3.** We give three examples of random subsets.

(i) (Dirac model) A fixed subset $c \subset E$ can be regarded as a constant random subset. Its law is

$$ \mathbf{Pr}(A = a) = \begin{cases} 1 & \text{if } a = c, \\ 0 & \text{if } a \neq c. \end{cases} $$

(ii) (Uniform random subset) Fix an integer $k \le |E|$. Let $A$ be the uniform distribution on all subsets of $E$ of cardinality $k$. Its law is

$$ \mathbf{Pr}(A = a) = \begin{cases} \binom{|E|}{k}^{-1} & \text{if } |a| = k, \\ 0 & \text{if } |a| \neq k. \end{cases} $$

(iii) (Bernoulli random subset) Let $A$ be the Bernoulli sampling of parameter $p \in [0, 1]$ on the set $E$: The events $\{x \in A\}$ through all $x \in E$ are independent of the same probability $p$. The law of $A$ is

$$ \mathbf{Pr}(A = a) = p^{|a|} (1-p)^{|E|-|a|}. $$

In this case $|A|$ follows the binomial law $\mathcal{B}(|E|, p)$.
# 1. Definitions and basic models

## 1.1. Densable sequences of random subsets

Let $E$ be a finite set, denote $|E|$ its cardinality. The following definition is due to M. Gromov in [9, p. 269].

**Definition 1.1.** Let $E$ be a finite non-empty set and $A \subset E$. The density of $A$ in $E$ is defined by

$$ \operatorname{dens}_E A := \log_{|E|} |A| = \frac{\log |A|}{\log |E|}. $$

So that $d \in [0, 1] \cup \{-\infty\}$ is a real number such that $|E|^d = |A|$.

We will omit the subscript $E$ if the set is fixed and simply denote the density by $\operatorname{dens} A$. Note that $\operatorname{dens} A = -\infty$ if and only if $A = \emptyset$.

**Definition 1.2.** Let $E$ be a finite set. Denote $\mathcal{P}(E)$ the set of subsets of $E$. A random subset $A$ of $E$ is a $\mathcal{P}(E)$-valued random variable.

In this article, we use upper-case letters $A, B, C, \dots$ to denote random subsets and lower-case letters $a, b, c, \dots$ to denote fixed subsets. The law of a random subset $A$ is determined by instances $\mathbf{Pr}(A = a)$ through all subsets $a \in \mathcal{P}(E)$ (or $a \subset E$). Its cardinality $|A|$ is a usual real-valued random variable.

**Example 1.3.** We give three examples of random subsets.

(i) (Dirac model) A fixed subset $c \subset E$ can be regarded as a constant random subset. Its law is

$$ \mathbf{Pr}(A = a) = \begin{cases} 1 & \text{if } a = c, \\ 0 & \text{if } a \neq c. \end{cases} $$

(ii) (Uniform random subset) Fix an integer $k \le |E|$. Let $A$ be the uniform distribution on all subsets of $E$ of cardinality $k$. Its law is

$$ \mathbf{Pr}(A = a) = \begin{cases} \binom{|E|}{k}^{-1} & \text{if } |a| = k, \\ 0 & \text{if } |a| \neq k. \end{cases} $$

(iii) (Bernoulli random subset) Let $A$ be the Bernoulli sampling of parameter $p \in [0, 1]$ on the set $E$: The events $\{x \in A\}$ through all $x \in E$ are independent of the same probability $p$. The law of $A$ is

$$ \mathbf{Pr}(A = a) = p^{|a|} (1-p)^{|E|-|a|}. $$

In this case $|A|$ follows the binomial law $\mathcal{B}(|E|, p)$.
As usual random variables, a random subset can be constructed by other random subsets.

**Example 1.4** (Set theoretic operations). The intersection of two random subsets A, B of a finite set E is another random subset. The law of A ∩ B is

$$
\mathrm{Pr}(A \cap B = c) = \sum_{a,b \in \mathcal{P}(E); a \cap b = c} \mathrm{Pr}(A = a, B = b).
$$

In particular, if A, B are *independent* random subsets, then

$$
\mathrm{Pr}(A \cap B = c) = \sum_{a,b \in \mathcal{P}(E); a \cap b = c} \mathrm{Pr}(A = a)\mathrm{Pr}(B = b).
$$

The union of two subsets and the complement of a subset are similarly defined.

We are interested in the asymptotic behavior of random subsets when $|E| \to \infty$.
Consider a sequence of finite sets $E = (E_n)_{n \in \mathbb{N}}$ with $|E_n| \xrightarrow{n \to \infty} \infty$. Recall that the
density of a subset $a \subset E$ is defined by $\mathrm{dens}_E(a) := \log|E|/|a|$.

**Definition 1.5.** We define densable sequences of random subsets.

(i) A sequence of (fixed) subsets of $\mathcal{E} = (E_n)$ is a sequence $\mathbf{a} = (a_n)$ such that $a_n \subset E_n$ for all $n$.

A sequence of subsets **a** is *densable* with density *d* ∈ [0, 1] ∪ {−∞} if

$$
\mathrm{dens}_{E_n}(a_n) = \log_{|E_n|} |a_n| \xrightarrow{n \to \infty} d.
$$

(ii) Similarly, a sequence of random subsets of $\mathcal{E}$ is a sequence $\mathbf{A} = (A_n)$ such that $A_n$ is a random subset of $E_n$ for all $n$.

A sequence of random subsets **A** is *densable* with density *d* ∈ [0, 1] ∪ {-∞} if the sequence of real-valued random valuables *dens*<sub>*E*<sub>*n*</sub></sub>(*A*<sub>*n*</sub>) = log<sub>|*E*<sub>*n*</sub>|</sub> |*A*<sub>*n*</sub>| converges in distribution to the constant *d*.

(iii) Two sequences of random subsets $\mathbf{A} = (A_n)$, $\mathbf{B} = (B_n)$ of $\mathcal{E}$ are independent if $A_n$, $B_n$ are independent random subsets of $E_n$ for all $n$.

**Example 1.6.** Here are four examples of densable sequences of random subsets.

(i) For a fixed sequence of subsets **a** = (a_n), dens(**a**) = -∞ if and only if a_n = Ø for large enough n.

(ii) A densable sequence of subsets **a** = (a_n) can be regarded as a densable sequence of random subsets (Dirac model on each term). If we take |a_n| = ⌊|E_n|^d⌋ with some 0 ≤ d ≤ 1, then **a** is densable with density *d*.

(iii) (Uniform density model) Let $\mathbf{A}=(A_n)$ be a sequence of random subsets of $\mathcal{E}$.
We call $\mathbf{A}$ a sequence of uniform random subsets with density $d$ if $A_n$ is the uniform
As usual random variables, a random subset can be constructed by other random subsets.

**Example 1.4** (Set theoretic operations). The intersection of two random subsets A, B of a finite set E is another random subset. The law of A ∩ B is

$$
\mathrm{Pr}(A \cap B = c) = \sum_{a,b \in \mathcal{P}(E); a \cap b = c} \mathrm{Pr}(A = a, B = b).
$$

In particular, if A, B are *independent* random subsets, then

$$
\mathrm{Pr}(A \cap B = c) = \sum_{a,b \in \mathcal{P}(E); a \cap b = c} \mathrm{Pr}(A = a)\mathrm{Pr}(B = b).
$$

The union of two subsets and the complement of a subset are similarly defined.

We are interested in the asymptotic behavior of random subsets when $|E| \to \infty$.
Consider a sequence of finite sets $E = (E_n)_{n \in \mathbb{N}}$ with $|E_n| \xrightarrow{n \to \infty} \infty$. Recall that the
density of a subset $a \subset E$ is defined by $\mathrm{dens}_E(a) := \log|E|/|a|$.

**Definition 1.5.** We define densable sequences of random subsets.

(i) A sequence of (fixed) subsets of $\mathcal{E} = (E_n)$ is a sequence $\mathbf{a} = (a_n)$ such that $a_n \subset E_n$ for all $n$.

A sequence of subsets **a** is *densable* with density *d* ∈ [0, 1] ∪ {−∞} if

$$
\mathrm{dens}_{E_n}(a_n) = \log_{|E_n|} |a_n| \xrightarrow{n \to \infty} d.
$$

(ii) Similarly, a sequence of random subsets of $\mathcal{E}$ is a sequence $\mathbf{A} = (A_n)$ such that $A_n$ is a random subset of $E_n$ for all $n$.

A sequence of random subsets **A** is *densable* with density *d* ∈ [0, 1] ∪ {-∞} if the sequence of real-valued random valuables *dens*<sub>*E*<sub>*n*</sub></sub>(*A*<sub>*n*</sub>) = log<sub>|*E*<sub>*n*</sub>|</sub> |*A*<sub>*n*</sub>| converges in distribution to the constant *d*.

(iii) Two sequences of random subsets $\mathbf{A} = (A_n)$, $\mathbf{B} = (B_n)$ of $\mathcal{E}$ are independent if $A_n$, $B_n$ are independent random subsets of $E_n$ for all $n$.

**Example 1.6.** Here are four examples of densable sequences of random subsets.

(i) For a fixed sequence of subsets **a** = (a_n), dens(**a**) = -∞ if and only if a_n = Ø for large enough n.

(ii) A densable sequence of subsets **a** = (a_n) can be regarded as a densable sequence of random subsets (Dirac model on each term). If we take |a_n| = ⌊|E_n|^d⌋ with some 0 ≤ d ≤ 1, then **a** is densable with density *d*.

(iii) (Uniform density model) Let $\mathbf{A}=(A_n)$ be a sequence of random subsets of $\mathcal{E}$.
We call $\mathbf{A}$ a sequence of uniform random subsets with density $d$ if $A_n$ is the uniform
distribution on all subsets of $E_n$ of cardinality $\lfloor|E_n|^d\rfloor$. Its law is

$$ \mathbf{Pr}(A_n = a) = \begin{cases} \binom{|E_n|}{\lfloor|E_n|^d\rfloor}^{-1} & \text{if } |a| = \lfloor|E_n|^d\rfloor, \\ 0 & \text{if } |a| \neq \lfloor|E_n|^d\rfloor. \end{cases} $$

(iv) (Bernoulli density model) Let $d > 0$. If $A_n$ is a Bernoulli sampling of $E_n$ with parameter $|E_n|^{d-1}$, then $A = (A_n)$ is a sequence of densable random subsets of $E$. It is rather not obvious that such sequences are densable (see Proposition 1.12).

**Definition 1.7.** Let $Q = (Q_n)$ be a sequence of events. The event $Q_n$ is asymptotically almost surely true if $\mathrm{Pr}(Q_n) \xrightarrow{n \to \infty} 1$.

Equivalently, for any $p < 1$ arbitrary close to 1 we have $\mathrm{Pr}(Q_n) > p$ for $n$ large enough. We denote briefly a.a.s. $Q_n$.

For example, if $A$ is a sequence of random subsets with dens $A = -\infty$, then $\mathrm{Pr}(|A_n| = 0) \xrightarrow{n \to \infty} 1$, which is equivalent to a.a.s. $|A_n| = 0$, or a.a.s. $A_n = \emptyset$.

**Proposition 1.8 (Characterization of densability).** Let $A$ be a sequence of random subsets of $E$. Let $d \ge 0$. $A$ is densable with density $d$ if and only if

$$ \forall \varepsilon > 0 \text{ a.a.s. } |E_n|^{d-\varepsilon} \le |A_n| \le |E_n|^{d+\varepsilon}. $$

*Proof.* The convergence in distribution to a constant is equivalent to the convergence in probability. So $\log_{|E_n|} |A_n|$ converges in distribution to $d$ if and only if

$$ \forall \varepsilon > 0 \quad \mathrm{Pr}(|\log_{|E_n|} |A_n| - d| \le \varepsilon) \xrightarrow{n \to \infty} 1, $$

which gives the estimation

$$ \forall \varepsilon > 0 \text{ a.a.s. } |E_n|^{d-\varepsilon} \le |A_n| \le |E_n|^{d+\varepsilon}. \quad \blacksquare $$

In general, the intersection of two densable sequences is not necessarily densable. The intersection formula is then *not* satisfied by the class of densable sequences of random subsets. Here is a simple example.

**Example 1.9.** Let $E = (E_n)$ be a sequence of sets with $|E_n| = 2n$. Let $a = (a_n)$, $b = (b_n)$ be sequences of subsets of $E$ such that $b_n = E_n \setminus a_n$ and $|a_n| = |b_n| = n$. They are both densable subsets with density 1 because $\log(n)/\log(2n) \to 1$. Whereas $\mathrm{dens}(a \cap b) = -\infty$. They do not verify the intersection formula.

Define another sequence of subset $c = (c_n)$ by $c_n := a_n$ if $n$ is odd and $c_n := b_n$ if $n$ is even. By its definition, $c$ is densable with density 1. But the intersection $b \cap c$ is empty when $n$ is odd and non-empty when $n$ is even, so $b \cap c$ is not densable.
distribution on all subsets of $E_n$ of cardinality $\lfloor|E_n|^d\rfloor$. Its law is

$$ \mathbf{Pr}(A_n = a) = \begin{cases} \binom{|E_n|}{\lfloor|E_n|^d\rfloor}^{-1} & \text{if } |a| = \lfloor|E_n|^d\rfloor, \\ 0 & \text{if } |a| \neq \lfloor|E_n|^d\rfloor. \end{cases} $$

(iv) (Bernoulli density model) Let $d > 0$. If $A_n$ is a Bernoulli sampling of $E_n$ with parameter $|E_n|^{d-1}$, then $A = (A_n)$ is a sequence of densable random subsets of $E$. It is rather not obvious that such sequences are densable (see Proposition 1.12).

**Definition 1.7.** Let $Q = (Q_n)$ be a sequence of events. The event $Q_n$ is asymptotically almost surely true if $\Pr(Q_n) \xrightarrow{n \to \infty} 1$.

Equivalently, for any $p < 1$ arbitrary close to 1 we have $\Pr(Q_n) > p$ for $n$ large enough. We denote briefly a.a.s. $Q_n$.

For example, if $A$ is a sequence of random subsets with dens $A = -\infty$, then $\Pr(|A_n| = 0) \xrightarrow{n \to \infty} 1$, which is equivalent to a.a.s. $|A_n| = 0$, or a.a.s. $A_n = \emptyset$.

**Proposition 1.8 (Characterization of densability).** Let $A$ be a sequence of random subsets of $E$. Let $d \ge 0$. $A$ is densable with density $d$ if and only if

$$ \forall \varepsilon > 0 \text{ a.a.s. } |E_n|^{d-\varepsilon} \le |A_n| \le |E_n|^{d+\varepsilon}. $$

*Proof.* The convergence in distribution to a constant is equivalent to the convergence in probability. So $\log_{|E_n|} |A_n|$ converges in distribution to $d$ if and only if

$$ \forall \varepsilon > 0 \quad \Pr(|\log_{|E_n|} |A_n| - d| \le \varepsilon) \xrightarrow{n \to \infty} 1, $$

which gives the estimation

$$ \forall \varepsilon > 0 \text{ a.a.s. } |E_n|^{d-\varepsilon} \le |A_n| \le |E_n|^{d+\varepsilon}. \quad \blacksquare $$

In general, the intersection of two densable sequences is not necessarily densable. The intersection formula is then *not* satisfied by the class of densable sequences of random subsets. Here is a simple example.

**Example 1.9.** Let $E = (E_n)$ be a sequence of sets with $|E_n| = 2n$. Let $a = (a_n)$, $b = (b_n)$ be sequences of subsets of $E$ such that $b_n = E_n \setminus a_n$ and $|a_n| = |b_n| = n$. They are both densable subsets with density 1 because $\log(n)/\log(2n) \to 1$. Whereas $\text{dens}(a \cap b) = -\infty$. They do not verify the intersection formula.

Define another sequence of subset $c = (c_n)$ by $c_n := a_n$ if $n$ is odd and $c_n := b_n$ if $n$ is even. By its definition, $c$ is densable with density 1. But the intersection $b \cap c$ is empty when $n$ is odd and non-empty when $n$ is even, so $b \cap c$ is not densable.
## 1.2. The Bernoulli density model

Let $E = (E_n)$ with $|E_n| \to \infty$ be the ambient sequence of sets.

**Definition 1.10 (Bernoulli density model).** Let $d \le 1$. Let $A = (A_n)$ be a sequence of random subsets of $E$. It is a sequence of Bernoulli random subsets with density $d$ if $A_n$ is a Bernoulli sampling of $E_n$ with parameter $|E_n|^{d-1}$.

This model is particularly easy to manipulate. We will see that it is densable, closed under intersection and verifies the intersection formula.

Recall that the real-valued random variable $|A_n|$ follows the binomial law

$$ \mathcal{B}(|E_n|, |E_n|^{d-1}). $$

$$ \text{Thus, } \mathbb{E}(|A_n|) = |E_n|^d. $$

**Lemma 1.11 (Concentration lemma).** Let $A$ be a sequence of Bernoulli random subsets with density $d > 0$. Then a.a.s.

$$ |A_n| - |E_n|^d \le \frac{1}{2}|E_n|^d. $$

*Proof.* By Chebyshev's inequality,

$$ \mathrm{Pr} \left( \left| |A_n| - |E_n|^d \right| > \frac{1}{2} |E_n|^d \right) \le \frac{\mathrm{Var}(|A_n|)}{\frac{1}{4} |E_n|^{2d}} \le \frac{4|E_n|^d (1 - |E_n|^{d-1})}{|E_n|^{2d}} \xrightarrow{n \to \infty} 0. \blacksquare $$

**Proposition 1.12.** Let $A$ be a sequence of Bernoulli random subsets with density $d$. If $d \ne 0$, then $A$ is densable and

$$ \text{dens } A = \begin{cases} d & \text{if } 0 < d \le 1, \\ -\infty & \text{if } d < 0. \end{cases} $$

*Proof.* We separate the two cases $d < 0$ and $0 < d \le 1$.

(i) If $d < 0$, by Markov's inequality

$$ \mathrm{Pr}(|A_n| \ge 1) \le |E_n|^d \to 0, $$

$$ \text{so } \mathrm{Pr}(A_n = \emptyset) \to 1 \text{ and } \mathrm{Pr}(\log_{|E_n|} |A_n| = -\infty) \to 1. $$

(ii) If $0 < d \le 1$, by Lemma 1.11, a.a.s.

$$ \frac{1}{2}|E_n|^d \le |A_n| \le \frac{3}{2}|E_n|^d. $$

For every $\varepsilon > 0$, the inequality $|E_n|^{d-\varepsilon} < \frac{1}{2}|E_n|^d < \frac{3}{2}|E_n|^d < |E_n|^{d+\varepsilon}$ holds for $n$ large enough. Thus, a.a.s.

$$ |E_n|^{d-\varepsilon} \le |A_n| \le |E_n|^{d+\varepsilon}. $$

Hence, $A = (A_n)$ is densable with density $d$ by Proposition 1.8. ■
## 1.2. The Bernoulli density model

Let $\mathcal{E} = (E_n)$ with $|E_n| \to \infty$ be the ambient sequence of sets.

**Definition 1.10 (Bernoulli density model).** Let $d \le 1$. Let $\mathcal{A} = (A_n)$ be a sequence of random subsets of $\mathcal{E}$. It is a sequence of Bernoulli random subsets with density $d$ if $A_n$ is a Bernoulli sampling of $E_n$ with parameter $|E_n|^{d-1}$.

This model is particularly easy to manipulate. We will see that it is densable, closed under intersection and verifies the intersection formula.

Recall that the real-valued random variable $|A_n|$ follows the binomial law

$$ \mathcal{B}(|E_n|, |E_n|^{d-1}). $$

$$ \text{Thus, } \mathbb{E}(|A_n|) = |E_n|^d. $$

**Lemma 1.11 (Concentration lemma).** Let $\mathcal{A}$ be a sequence of Bernoulli random subsets with density $d > 0$. Then a.a.s.

$$ |A_n| - |E_n|^d \le \frac{1}{2}|E_n|^d. $$

*Proof.* By Chebyshev's inequality,

$$ \mathrm{Pr} \left( \left| |A_n| - |E_n|^d \right| > \frac{1}{2} |E_n|^d \right) \le \frac{\mathrm{Var}(|A_n|)}{\frac{1}{4} |E_n|^{2d}} \le \frac{4|E_n|^d (1 - |E_n|^{d-1})}{|E_n|^{2d}} \xrightarrow{n \to \infty} 0. \blacksquare $$

**Proposition 1.12.** Let $\mathcal{A}$ be a sequence of Bernoulli random subsets with density $d$. If $d \ne 0$, then $\mathcal{A}$ is densable and

$$ \text{dens } \mathcal{A} = \begin{cases} d & \text{if } 0 < d \le 1, \\ -\infty & \text{if } d < 0. \end{cases} $$

*Proof.* We separate the two cases $d < 0$ and $0 < d \le 1$.

(i) If $d < 0$, by Markov's inequality

$$ \mathrm{Pr}(|A_n| \ge 1) \le |E_n|^d \to 0, $$

$$ \text{so } \mathrm{Pr}(A_n = \emptyset) \to 1 \text{ and } \mathrm{Pr}(\log_{|E_n|} |A_n| = -\infty) \to 1. $$

(ii) If $0 < d \le 1$, by Lemma 1.11, a.a.s.

$$ \frac{1}{2}|E_n|^d \le |A_n| \le \frac{3}{2}|E_n|^d. $$

For every $\varepsilon > 0$, the inequality $|E_n|^{d-\varepsilon} < \frac{1}{2}|E_n|^d < \frac{3}{2}|E_n|^d < |E_n|^{d+\varepsilon}$ holds for $n$ large enough. Thus, a.a.s.

$$ |E_n|^{d-\varepsilon} \le |A_n| \le |E_n|^{d+\varepsilon}. $$

Hence, $\mathcal{A} = (A_n)$ is densable with density $d$ by Proposition 1.8. ■
**Theorem 1.13** (The intersection formula for Bernoulli density model). Let $A, B$ be independent sequences of Bernoulli random subsets of $E = (E_n)$ with densities $\alpha, \beta$. Then $A \cap B$ is a sequence of Bernoulli random subsets of $E$ with density $\alpha + \beta - 1$, and

$$ \mathrm{dens}(A \cap B) = \begin{cases} \alpha + \beta - 1 & \text{if } \alpha + \beta > 1, \\ -\infty & \text{if } \alpha + \beta < 1. \end{cases} $$

*Proof.* For every element $x \in E_n$, we have

$$ \mathrm{Pr}(x \in A_n \cap B_n) = \mathrm{Pr}(x \in A_n)\mathrm{Pr}(x \in B_n) = |E_n|^{(\alpha+\beta-1)-1}. $$

In addition, for every pair of distinct elements $x, y$ in $E_n$, we have

$$ \begin{aligned} \mathrm{Pr}(x, y \in A_n \cap B_n) &= \mathrm{Pr}(x, y \in A_n)\mathrm{Pr}(x, y \in B_n) \\ &= \mathrm{Pr}(x \in A_n)\mathrm{Pr}(y \in A_n)\mathrm{Pr}(x \in B_n)\mathrm{Pr}(y \in B_n) \\ &= \mathrm{Pr}(x \in A_n \cap B_n)\mathrm{Pr}(y \in A_n \cap B_n). \end{aligned} $$

So $A \cap B$ is a sequence of Bernoulli random subsets with density $\alpha + \beta - 1$. Proposition 1.12 gives its density. ■

As the theorem shows, the class of Bernoulli random subsets is closed under intersections. Thereby the intersection formula works for multiple independent sequences of random subsets. The formula is more concise in terms of codensities.

**Definition 1.14** (cf. [9, p. 269]). Let $A$ be a densable sequence of random subsets such that $\mathrm{dens} \ A \in [0, 1]$. Then the codensity of $A$ is defined by

$$ \mathrm{codens} \ A = 1 - \mathrm{dens} \ A. $$

Theorem 1.13 can be rephrase as (compare [9, p. 270]):

**Theorem 1.13'** (The intersection formula by codensities). Let $A, B$ be independent sequences of Bernoulli random subsets of $E$ with positive densities. If $\mathrm{codens} \ A + \mathrm{codens} \ B < 1$, then

$$ \mathrm{codens}(A \cap B) = \mathrm{codens} \ A + \mathrm{codens} \ B. $$

If $\mathrm{codens} \ A + \mathrm{codens} \ B > 1$, then $\mathrm{dens}(A \cap B) = -\infty$.

**Corollary 1.15** (Generalized intersection formula by codensities). Let $A_1, \dots, A_k$ be independent sequences of Bernoulli random subsets with positive densities. If $\sum_{i=1}^k \mathrm{codens} \ A_i < 1$, then

$$ \mathrm{codens} \left( \bigcap_{i=1}^{k} A_i \right) = \sum_{i=1}^{k} \mathrm{codens} \ A_i. $$
**Theorem 1.13** (The intersection formula for Bernoulli density model). Let $A, B$ be independent sequences of Bernoulli random subsets of $E = (E_n)$ with densities $\alpha, \beta$. Then $A \cap B$ is a sequence of Bernoulli random subsets of $E$ with density $\alpha + \beta - 1$, and

$$ \mathrm{dens}(A \cap B) = \begin{cases} \alpha + \beta - 1 & \text{if } \alpha + \beta > 1, \\ -\infty & \text{if } \alpha + \beta < 1. \end{cases} $$

*Proof.* For every element $x \in E_n$, we have

$$ \mathrm{Pr}(x \in A_n \cap B_n) = \mathrm{Pr}(x \in A_n) \mathrm{Pr}(x \in B_n) = |E_n|^{(\alpha+\beta-1)-1}. $$

In addition, for every pair of distinct elements $x, y$ in $E_n$, we have

$$ \begin{aligned} \mathrm{Pr}(x, y \in A_n \cap B_n) &= \mathrm{Pr}(x, y \in A_n) \mathrm{Pr}(x, y \in B_n) \\ &= \mathrm{Pr}(x \in A_n) \mathrm{Pr}(y \in A_n) \mathrm{Pr}(x \in B_n) \mathrm{Pr}(y \in B_n) \\ &= \mathrm{Pr}(x \in A_n \cap B_n) \mathrm{Pr}(y \in A_n \cap B_n). \end{aligned} $$

So $A \cap B$ is a sequence of Bernoulli random subsets with density $\alpha + \beta - 1$. Proposition 1.12 gives its density. ■

As the theorem shows, the class of Bernoulli random subsets is closed under intersections. Thereby the intersection formula works for multiple independent sequences of random subsets. The formula is more concise in terms of codensities.

**Definition 1.14** (cf. [9, p. 269]). Let $A$ be a densable sequence of random subsets such that $\mathrm{dens} \ A \in [0, 1]$. Then the codensity of $A$ is defined by

$$ \mathrm{codens} \ A = 1 - \mathrm{dens} \ A. $$

Theorem 1.13 can be rephrase as (compare [9, p. 270]):

**Theorem 1.13'** (The intersection formula by codensities). Let $A, B$ be independent sequences of Bernoulli random subsets of $E$ with positive densities. If $\mathrm{codens} \ A + \mathrm{codens} \ B < 1$, then

$$ \mathrm{codens}(A \cap B) = \mathrm{codens} \ A + \mathrm{codens} \ B. $$

If $\mathrm{codens} \ A + \mathrm{codens} \ B > 1$, then $\mathrm{dens}(A \cap B) = -\infty$.

**Corollary 1.15** (Generalized intersection formula by codensities). Let $A_1, \dots, A_k$ be independent sequences of Bernoulli random subsets with positive densities. If $\sum_{i=1}^k \mathrm{codens} \ A_i < 1$, then

$$ \mathrm{codens} \left( \bigcap_{i=1}^{k} A_i \right) = \sum_{i=1}^{k} \mathrm{codens} \ A_i. $$
If $\sum_{i=1}^k \text{codens } A_i > 1$, then

$$ \text{dens}\left(\bigcap_{i=1}^k A_i\right) = -\infty. $$

As an exception, a Bernoulli sequence of random subsets with density $d = 0$ is not densable.

**Proposition 1.16.** Let A be a Bernoulli sequence with density $d = 0$. Then A is not densable. In fact,

$$ \text{Pr}(\text{dens } A_n = -\infty) \xrightarrow{n \to \infty} 1/e. $$

*Proof.* $\text{Pr}(|A_n| = 0) = (1 - |E_n|^{-1})^{|E_n|} \xrightarrow{n \to \infty} 1/e$, which gives

$$ \text{Pr}(\text{dens } A_n = -\infty) \xrightarrow{n \to \infty} 1/e. $$

This justifies that the sequence of random variables $(\text{dens}_{E_n} A_n)$ does not converge to any constant distribution. ■

### 1.3. The uniform density model

The uniform density model is the first example of densable sequences of random subsets. It was introduced by M.Gromov [9, p. 270] to construct random groups with fixed generators, and later developed by Y. Ollivier [15, p. 1]. It was also used by A. Żuk [19] to study random triangular groups.

Let $E = (E_n)$ be a sequence of sets. To simplify, we assume that $|E_n| = n$ in this subsection. For an arbitrary sequence $E$ with $|E_n| \to \infty$ we can proceed similar proofs by replacing $n$ by $|E_n|$. Note that $|E_n|^d = n^d \sim [n^d]$, while $n \to \infty$ for $d \in [0, 1]$.

Recall that a sequence of uniform random subsets (Example 1.6 (iv)) of $(E_n)$ with density $d$ is a sequence of random subsets $(A_n)$ with the following laws:

$$ \text{Pr}(A_n = a) = \begin{cases} \binom{n}{\lfloor n^d \rfloor}^{-1} & \text{if } |a| = \lfloor n^d \rfloor, \\ 0 & \text{if } |a| \neq \lfloor n^d \rfloor. \end{cases} $$

We give here a concentration lemma for uniform density model, similar to Lemma 1.11. For the proof, we will need Lemmas 2.2 and 2.3 given in the next section.

**Lemma 1.17 (Concentration lemma for uniform density model).** Let A, B be independent sequences of uniform random subsets of E with densities $\alpha, \beta \in [0, 1]$. Then:

$$ (i) \quad n^{\alpha+\beta-1} - 2 \le \mathbb{E}(|A_n \cap B_n|) \le n^{\alpha+\beta-1}. $$
If $\sum_{i=1}^k \text{codens } A_i > 1$, then

$$ \text{dens}\left(\bigcap_{i=1}^k A_i\right) = -\infty. $$

As an exception, a Bernoulli sequence of random subsets with density $d = 0$ is not densable.

**Proposition 1.16.** Let A be a Bernoulli sequence with density $d = 0$. Then A is not densable. In fact,

$$ \text{Pr}(\text{dens } A_n = -\infty) \xrightarrow{n \to \infty} 1/e. $$

*Proof.* $\text{Pr}(|A_n| = 0) = (1 - |E_n|^{-1})^{|E_n|} \xrightarrow{n \to \infty} 1/e$, which gives

$$ \text{Pr}(\text{dens } A_n = -\infty) \xrightarrow{n \to \infty} 1/e. $$

This justifies that the sequence of random variables $(\text{dens}_{E_n} A_n)$ does not converge to any constant distribution. ■

## 1.3. The uniform density model

The uniform density model is the first example of densable sequences of random subsets. It was introduced by M.Gromov [9, p. 270] to construct random groups with fixed generators, and later developed by Y. Ollivier [15, p. 1]. It was also used by A. Żuk [19] to study random triangular groups.

Let $E = (E_n)$ be a sequence of sets. To simplify, we assume that $|E_n| = n$ in this subsection. For an arbitrary sequence $E$ with $|E_n| \to \infty$ we can proceed similar proofs by replacing $n$ by $|E_n|$. Note that $|E_n|^d = n^d \sim \lfloor n^d \rfloor$, while $n \to \infty$ for $d \in [0, 1]$.

Recall that a sequence of uniform random subsets (Example 1.6 (iv)) of $(E_n)$ with density $d$ is a sequence of random subsets $(A_n)$ with the following laws:

$$ \text{Pr}(A_n = a) = \begin{cases} \binom{n}{\lfloor n^d \rfloor}^{-1} & \text{if } |a| = \lfloor n^d \rfloor, \\ 0 & \text{if } |a| \neq \lfloor n^d \rfloor. \end{cases} $$

We give here a concentration lemma for uniform density model, similar to Lemma 1.11. For the proof, we will need Lemmas 2.2 and 2.3 given in the next section.

**Lemma 1.17 (Concentration lemma for uniform density model).** Let A, B be independent sequences of uniform random subsets of E with densities $\alpha, \beta \in [0, 1]$. Then:

$$ (i) \quad n^{\alpha+\beta-1} - 2 \le \mathbb{E}(|A_n \cap B_n|) \le n^{\alpha+\beta-1}. $$
(ii) If $\alpha < 1$ and $\beta < 1$, then

$$ \mathrm{Var}(|A_n \cap B_n|) \sim n^{\alpha+\beta-1}. $$

Moreover, if $n \ge 3$, then

$$ \mathrm{Var}(|A_n \cap B_n|) \le 3n^{\alpha+\beta-1}. $$

(iii) Let $0 < c < 1$. If $\alpha + \beta - 1 > 0$ and $n \ge (\frac{4}{c})^{1/(\alpha+\beta-1)}$, then

$$ \mathbf{Pr}(|A_n \cap B_n| - n^{\alpha+\beta-1} > cn^{\alpha+\beta-1}) \le \frac{12}{c^2 n^{\alpha+\beta-1}} \xrightarrow{n \to \infty} 0. $$

In particular, a.a.s.

$$ ||A_n \cap B_n| - n^{\alpha+\beta-1}| \le cn^{\alpha+\beta-1}. $$

*Proof.* We consider each item.

(i) By Lemma 2.2, $A_n \cap B_n$ is a permutation invariant random set of $E_n$. Apply Lemma 2.3:

$$ \begin{aligned} \mathbb{E}(|A_n \cap B_n|) &= n\mathbf{Pr}(x \in A_n \cap B_n) = n\mathbf{Pr}(x \in A_n)\mathbf{Pr}(x \in B_n) \\ &= n \frac{\mathbb{E}(|A_n|)}{n} \frac{\mathbb{E}(|B_n|)}{n} = [n^\alpha][n^\beta]n^{-1} \sim n^{\alpha+\beta-1}. \end{aligned} $$

For the inequality, as $\alpha, \beta \le 1$:

$$ n^{\alpha+\beta-1} - 2 \le n^{\alpha+\beta-1} - n^{\alpha-1} - n^{\beta-1} + n^{-1} \le [n^{\alpha}][n^{\beta}]n^{-1} \le n^{\alpha+\beta-1}. $$

(ii) Let $x, y$ be distinct elements in $E$. The number of subsets of $E$ containing $x, y$ of cardinality $[n^\alpha]$ is $\binom{n-2}{\lfloor n^\alpha \rfloor - 2}$, so

$$ \mathbf{Pr}(x, y \in A_n) = \frac{\binom{n-2}{\lfloor n^\alpha \rfloor - 2}}{\binom{n}{\lfloor n^\alpha \rfloor}} = \frac{\lfloor n^\alpha \rfloor (\lfloor n^\alpha \rfloor - 1)}{n(n-1)}. $$

Similarly,

$$ \mathbf{Pr}(x, y \in B_n) = \frac{\lfloor n^\beta \rfloor (\lfloor n^\beta \rfloor - 1)}{n(n-1)}. $$

Denote $k = \lfloor n^\alpha \rfloor$ and $l = \lfloor n^\beta \rfloor$ to simplify the notation. Note that $k = o(n)$ and $l = o(n)$ as $\alpha < 1$ and $\beta < 1$. Recall that $\mathbb{E}(|A_n \cap B_n|) = kln^{-1}$. Apply Lemma 2.3, the variance of $|A_n \cap B_n|$ is

$$ \begin{aligned} \mathrm{Var}(|A_n \cap B_n|) &= kln^{-1} + n(n-1)\mathrm{Pr}(x, y \in A_n)\mathrm{Pr}(x, y \in B_n) - (kln^{-1})^2 \\ &= kln^{-1} + \frac{k(k-1)l(l-1)}{n(n-1)} - (kln^{-1})^2 \end{aligned} $$
(ii) If $\alpha < 1$ and $\beta < 1$, then

$$ \mathrm{Var}(|A_n \cap B_n|) \sim n^{\alpha+\beta-1}. $$

Moreover, if $n \ge 3$, then

$$ \mathrm{Var}(|A_n \cap B_n|) \le 3n^{\alpha+\beta-1}. $$

(iii) Let $0 < c < 1$. If $\alpha + \beta - 1 > 0$ and $n \ge (\frac{4}{c})^{1/(\alpha+\beta-1)}$, then

$$ \mathbf{Pr}(|A_n \cap B_n| - n^{\alpha+\beta-1}| > cn^{\alpha+\beta-1}) \le \frac{12}{c^2 n^{\alpha+\beta-1}} \xrightarrow{n \to \infty} 0. $$

In particular, a.a.s.

$$ ||A_n \cap B_n| - n^{\alpha+\beta-1}| \le cn^{\alpha+\beta-1}. $$

*Proof.* We consider each item.

(i) By Lemma 2.2, $A_n \cap B_n$ is a permutation invariant random set of $E_n$. Apply Lemma 2.3:

$$ \begin{aligned} \mathbb{E}(|A_n \cap B_n|) &= n \mathbf{Pr}(x \in A_n \cap B_n) = n \mathbf{Pr}(x \in A_n) \mathbf{Pr}(x \in B_n) \\ &= n \frac{\mathbb{E}(|A_n|)}{n} \frac{\mathbb{E}(|B_n|)}{n} = [n^\alpha] [n^\beta] n^{-1} \sim n^{\alpha+\beta-1}. \end{aligned} $$

For the inequality, as $\alpha, \beta \le 1$:

$$ n^{\alpha+\beta-1} - 2 \le n^{\alpha+\beta-1} - n^{\alpha-1} - n^{\beta-1} + n^{-1} \le [n^{\alpha}] [n^{\beta}] n^{-1} \le n^{\alpha+\beta-1}. $$

(ii) Let $x, y$ be distinct elements in $E$. The number of subsets of $E$ containing $x, y$ of cardinality $[n^\alpha]$ is $\binom{n-2}{\lfloor n^\alpha \rfloor - 2}$, so

$$ \mathbf{Pr}(x, y \in A_n) = \frac{\binom{n-2}{\lfloor n^\alpha \rfloor - 2}}{\binom{n}{\lfloor n^\alpha \rfloor}} = \frac{\lfloor n^\alpha \rfloor (\lfloor n^\alpha \rfloor - 1)}{n(n-1)}. $$

Similarly,

$$ \mathbf{Pr}(x, y \in B_n) = \frac{\lfloor n^\beta \rfloor (\lfloor n^\beta \rfloor - 1)}{n(n-1)}. $$

Denote $k = \lfloor n^\alpha \rfloor$ and $l = \lfloor n^\beta \rfloor$ to simplify the notation. Note that $k = o(n)$ and $l = o(n)$ as $\alpha < 1$ and $\beta < 1$. Recall that $\mathbb{E}(|A_n \cap B_n|) = kln^{-1}$. Apply Lemma 2.3, the variance of $|A_n \cap B_n|$ is

$$ \begin{aligned} \mathrm{Var}(|A_n \cap B_n|) &= kln^{-1} + n(n-1)\mathrm{Pr}(x, y \in A_n)\mathrm{Pr}(x, y \in B_n) - (kln^{-1})^2 \\ &= kln^{-1} + \frac{k(k-1)l(l-1)}{n(n-1)} - (kln^{-1})^2 \end{aligned} $$
$$
= \frac{kl}{n^2(n-1)}(n^2-n+nkl-nl-nk+n-nkl+kl) \\
\sim \frac{kl}{n^2(n-1)} \cdot n^2 \sim n^{\alpha+\beta-1}.
$$

Moreover, if $n \ge 3$, then

$$
\mathrm{Var}(|A_n \cap B_n|) = \frac{kl}{n^2(n-1)}(n^2-nl-nk+kl) \le \frac{2kl}{n-1} \le \frac{2n^{\alpha+\beta}}{n-1} \le 3n^{\alpha+\beta-1}.
$$

(iii) By (i) if $n \ge (\frac{4}{c})^{1/(\alpha+\beta-1)} \ge 4$, then

$$
|\mathbb{E}(|A_n \cap B_n|) - n^{\alpha+\beta-1}| \le \frac{c}{2} n^{\alpha+\beta-1}.
$$

If $\alpha = 1$ or $\beta = 1$ then the result is true as the $A_n = E_n$ or $B_n = E_n$. Otherwise by (ii)
and Chebyshev's inequality, if $n \ge (\frac{4}{c})^{1/(\alpha+\beta-1)}$ then

$$
\begin{align*}
& \mathrm{Pr}(|A_n \cap B_n| - n^{\alpha+\beta-1}| > c n^{\alpha+\beta-1}) \\
\le {} & \mathrm{Pr}(|A_n \cap B_n| - \mathbb{E}(|A_n \cap B_n|)| > \frac{c}{2} n^{\alpha+\beta-1}) \\
\le {} & \frac{4 \mathrm{Var}(|A_n \cap B_n|)}{c^2 n^{2\alpha+2\beta-2}} \le \frac{12}{c^2 n^{\alpha+\beta-1}}. \quad \blacksquare
\end{align*}
$$

**Proposition 1.18** (The intersection formula for uniform density model). Let **A**, **B**
be independent sequences of uniform random subsets of **E** with densities α, β. If
α + β ≠ 1, then the sequence **A** ∩ **B** is densable and

$$
\mathrm{dens}(\mathbf{A} \cap \mathbf{B}) = \begin{cases} \alpha + \beta - 1 & \text{if } \alpha + \beta > 1, \\ -\infty & \text{if } \alpha + \beta < 1. \end{cases}
$$

Proof. We separate the two cases $\alpha + \beta < 1$ and $\alpha + \beta > 1$.

(i) If $\alpha + \beta < 1$, then by Markov's inequality and Lemma 1.17 (i):

$$
\mathrm{Pr}(|A_n \cap B_n| \ge 1) \le \mathbb{E}(|A_n \cap B_n|) \xrightarrow{n \to \infty} 0,
$$

which implies a.a.s. $A_n \cap B_n = \emptyset$ and $\mathrm{dens}(A \cap B) = -\infty$.

(ii) If $\alpha + \beta > 1$, by Lemma 1.17 (iii) (with $c = 1/2$) a.a.s.

$$
||A_n \cap B_n| - n^{\alpha+\beta-1}| \le \frac{1}{2} n^{\alpha+\beta-1},
$$

so for all $\varepsilon > 0$ a.a.s.

$$
n^{\alpha+\beta-1-\epsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\epsilon}.
$$

Hence, by Proposition 1.8, $\mathbf{A} \cap \mathbf{B}$ is densable with density $\alpha + \beta - 1$. $\blacksquare$
$$ 
\begin{aligned}
&= \frac{kl}{n^2(n-1)}(n^2 - n + nkl - nl - nk + n - nkl + kl) \\
&\sim \frac{kl}{n^2(n-1)} \cdot n^2 \sim n^{\alpha+\beta-1}.
\end{aligned}
$$

Moreover, if $n \ge 3$, then

$$ \mathrm{Var}(|A_n \cap B_n|) = \frac{kl}{n^2(n-1)}(n^2-nl-nk+kl) \le \frac{2kl}{n-1} \le \frac{2n^{\alpha+\beta}}{n-1} \le 3n^{\alpha+\beta-1}. $$

(iii) By (i) if $n \ge (\frac{4}{c})^{1/(\alpha+\beta-1)} \ge 4$, then

$$ |\mathbb{E}(|A_n \cap B_n|) - n^{\alpha+\beta-1}| \le \frac{c}{2} n^{\alpha+\beta-1}. $$

If $\alpha = 1$ or $\beta = 1$ then the result is true as the $A_n = E_n$ or $B_n = E_n$. Otherwise by (ii) and Chebyshev's inequality, if $n \ge (\frac{4}{c})^{1/(\alpha+\beta-1)}$ then

$$ 
\begin{aligned}
& \mathrm{Pr}(|A_n \cap B_n| - n^{\alpha+\beta-1}| > cn^{\alpha+\beta-1}) \\
& \le \mathrm{Pr}(|A_n \cap B_n| - \mathbb{E}(|A_n \cap B_n|)| > \frac{c}{2}n^{\alpha+\beta-1}) \\
& \le \frac{4 \mathrm{Var}(|A_n \cap B_n|)}{c^2 n^{2\alpha+2\beta-2}} \le \frac{12}{c^2 n^{\alpha+\beta-1}}.
\end{aligned}
\quad \blacksquare $$

**Proposition 1.18** (The intersection formula for uniform density model). Let $A, B$ be independent sequences of uniform random subsets of $E$ with densities $\alpha, \beta$. If $\alpha + \beta \ne 1$, then the sequence $A \cap B$ is densable and

$$ \mathrm{dens}(A \cap B) = \begin{cases} \alpha + \beta - 1 & \text{if } \alpha + \beta > 1, \\ -\infty & \text{if } \alpha + \beta < 1. \end{cases} $$

*Proof.* We separate the two cases $\alpha + \beta < 1$ and $\alpha + \beta > 1$.

(i) If $\alpha + \beta < 1$, then by Markov's inequality and Lemma 1.17 (i):

$$ \mathrm{Pr}(|A_n \cap B_n| \ge 1) \le \mathbb{E}(|A_n \cap B_n|) \xrightarrow{n \to \infty} 0, $$

which implies a.a.s. $A_n \cap B_n = \emptyset$ and $\mathrm{dens}(A \cap B) = -\infty$.

(ii) If $\alpha + \beta > 1$, by Lemma 1.17 (iii) (with $c = 1/2$) a.a.s.

$$ ||A_n \cap B_n| - n^{\alpha+\beta-1}| \le \frac{1}{2} n^{\alpha+\beta-1}, $$

so for all $\varepsilon > 0$ a.a.s.

$$ n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon}. $$

Hence, by Proposition 1.8, $A \cap B$ is densable with density $\alpha + \beta - 1$. ■
The cardinality of $A_n \cap B_n$ is close to $n^{\alpha+\beta-1}$ with high probability, but not always. If $\alpha \neq 1$ and $\beta \neq 1$, then for $n$ large enough $\lfloor n^\alpha \rfloor + \lfloor n^\beta \rfloor < n$, so

$$ \Pr(A_n \cap B_n = \emptyset) \neq 0. $$

Which means that $A \cap B$ is not a sequence of uniform random subsets, so the class of sequences of uniform random subsets is *not* closed under intersection.

## 2. The general model: Densable and permutation invariant

### 2.1. Densable sequences of permutation invariant random subsets

Let $E$ be a finite set with cardinality $|E| = n$. Denote $S(E)$ as the group of permutations of $E$. The action of $S(E)$ on $E$ can be extended on $\mathcal{P}(E)$, defined by $\sigma(\{x_1, \dots, x_k\}) := \{\sigma(x_1), \dots, \sigma(x_k)\}$.

Note that this action has $(n+1)$ orbits of the form $\{a \in S(E) \mid |a| = k\}$ for $k \in \{0, \dots, n\}$. Moreover, the action commutes with set theoretic operations: $\sigma(E\backslash a) = E\backslash\sigma(a)$, $\sigma(a \cap b) = \sigma(a) \cap \sigma(b)$ and $\sigma(a \cup b) = \sigma(a) \cup \sigma(b)$.

**Definition 2.1** (Permutation invariant random subsets). Let $A$ be a random subset of $E$. It is permutation invariant if its law is invariant by the permutations of $E$. i.e.

$$ \forall a \in \mathcal{P}(E) \quad \forall \sigma \in S(E) \quad \Pr(A = a) = \Pr(A = \sigma(a)). $$

Equivalently, subsets of $E$ of the same cardinality are equiprobable. There exists real numbers $p_0, \dots, p_n \in [0, 1]$ satisfying

$$ \sum_{k=0}^{n} \binom{n}{k} p_k = 1 $$

such that

$$ \forall a \in \mathcal{P}(E) \quad |a| = k \Rightarrow \Pr(A = a) = p_k. $$

By definition, uniform random subsets and Bernoulli random subsets are permutation invariant. The advantage of such class of random subsets is that it is closed under set theoretic operations, especially under intersections.

**Lemma 2.2** (Closed under set operations). Let $E$ be a finite set. The class of permutation invariant random subsets of $E$ is closed under set theoretic operations (union, complement and intersection).
The cardinality of $A_n \cap B_n$ is close to $n^{\alpha+\beta-1}$ with high probability, but not always. If $\alpha \neq 1$ and $\beta \neq 1$, then for $n$ large enough $\lfloor n^\alpha \rfloor + \lfloor n^\beta \rfloor < n$, so

$$ \Pr(A_n \cap B_n = \emptyset) \neq 0. $$

Which means that $A \cap B$ is not a sequence of uniform random subsets, so the class of sequences of uniform random subsets is *not* closed under intersection.

## 2. The general model: Densable and permutation invariant

### 2.1. Densable sequences of permutation invariant random subsets

Let $E$ be a finite set with cardinality $|E| = n$. Denote $S(E)$ as the group of permutations of $E$. The action of $S(E)$ on $E$ can be extended on $\mathcal{P}(E)$, defined by $\sigma(\{x_1, \dots, x_k\}) := \{\sigma(x_1), \dots, \sigma(x_k)\}$.

Note that this action has $(n+1)$ orbits of the form $\{a \in S(E) \mid |a| = k\}$ for $k \in \{0, \dots, n\}$. Moreover, the action commutes with set theoretic operations: $\sigma(E\backslash a) = E\backslash\sigma(a)$, $\sigma(a \cap b) = \sigma(a) \cap \sigma(b)$ and $\sigma(a \cup b) = \sigma(a) \cup \sigma(b)$.

**Definition 2.1** (Permutation invariant random subsets). Let $A$ be a random subset of $E$. It is permutation invariant if its law is invariant by the permutations of $E$. i.e.

$$ \forall a \in \mathcal{P}(E) \quad \forall \sigma \in S(E) \quad \Pr(A = a) = \Pr(A = \sigma(a)). $$

Equivalently, subsets of $E$ of the same cardinality are equiprobable. There exists real numbers $p_0, \dots, p_n \in [0, 1]$ satisfying

$$ \sum_{k=0}^{n} \binom{n}{k} p_k = 1 $$

such that

$$ \forall a \in \mathcal{P}(E) \quad |a| = k \Rightarrow \Pr(A = a) = p_k. $$

By definition, uniform random subsets and Bernoulli random subsets are permutation invariant. The advantage of such class of random subsets is that it is closed under set theoretic operations, especially under intersections.

**Lemma 2.2** (Closed under set operations). Let $E$ be a finite set. The class of permutation invariant random subsets of $E$ is closed under set theoretic operations (union, complement and intersection).
*Proof.* We treat the three set theoretic operations (complement, intersection and union) separately.

(i) (Complement) Let $A$ be a permutation invariant random subset. Let $a \in \mathcal{P}(E)$ and $\sigma \in \mathcal{S}(E)$. Then

$$ 
\begin{aligned}
\mathbf{Pr}(E\backslash A = a) &= \mathbf{Pr}(A = E\backslash a) = \mathbf{Pr}(A = \sigma(E\backslash a)) \\
&= \mathbf{Pr}(A = E\backslash \sigma(a)) = \mathbf{Pr}(E\backslash A = \sigma(a)).
\end{aligned}
$$

(ii) (Intersection) Let $A, B$ be independent permutation invariant random subsets. Then for $\sigma \in \mathcal{S}(E)$,

$$ 
\begin{aligned}
\mathbf{Pr}(A \cap B = c) &= \sum_{a,b \in \mathcal{P}(E); a \cap b = c} \mathbf{Pr}(A = a)\mathbf{Pr}(B = b) \\
&= \sum_{a,b \in \mathcal{P}(E); \sigma(a) \cap \sigma(b) = \sigma(c)} \mathbf{Pr}(A = \sigma(a))\mathbf{Pr}(B = \sigma(b)) \\
&= \sum_{a',b' \in \mathcal{P}(E); a' \cap b' = \sigma(c)} \mathbf{Pr}(A = a')\mathbf{Pr}(B = b') \quad (\text{by substitution}) \\
&= \mathbf{Pr}(A \cap B = \sigma(c)).
\end{aligned}
$$

(iii) (Union) Let $A, B$ be independent permutation invariant random subsets. Then $A \cup B = E\backslash((E\backslash A) \cap (E\backslash B))$. So $A \cup B$ is permutation invariant. $\blacksquare$

We shall express the expectation and the variance of the random variable $|A|$ in terms of $\mathbf{Pr}(x \in A)$ and $\mathbf{Pr}(x \in A, y \in A)$, where $x, y$ are distinct elements in $E$.

**Lemma 2.3.** Let $A$ be a permutation invariant random subset of $E$. Let $x, y$ be distinct elements in $E$. Then:

(i) $\mathbb{E}(|A|) = n\mathbf{Pr}(x \in A),$

(ii) $\mathrm{Var}(|A|) = \mathbb{E}(|A|) + n(n-1)\mathbf{Pr}(x \in A, y \in A) - \mathbb{E}(|A|^2).$

*Proof.* We consider each item.

(i) By definition the probability $\mathbf{Pr}(z \in A)$ does not depend on the choice of element $z \in E$. So,

$$ \mathbb{E}(|A|) = \mathbb{E}\left(\sum_{z \in E} \mathbb{1}_{z \in A}\right) = \sum_{z \in E} \mathbf{Pr}(z \in A) = n\mathbf{Pr}(x \in A). $$

(ii) By the same argument, the probability $\mathbf{Pr}(z \in A, w \in A)$ does not depend on the choice of pair of distinct elements $(z, w)$ in $E$. So,

$$ \mathbb{E}(|A|^2) = \mathbb{E}\left[\left(\sum_{z \in E} \mathbb{1}_{z \in A}\right)^2\right] $$
*Proof.* We treat the three set theoretic operations (complement, intersection and union) separately.

(i) (Complement) Let $A$ be a permutation invariant random subset. Let $a \in \mathcal{P}(E)$ and $\sigma \in \mathcal{S}(E)$. Then

$$ 
\begin{aligned}
\mathbf{Pr}(E\backslash A = a) &= \mathbf{Pr}(A = E\backslash a) = \mathbf{Pr}(A = \sigma(E\backslash a)) \\
&= \mathbf{Pr}(A = E\backslash \sigma(a)) = \mathbf{Pr}(E\backslash A = \sigma(a)).
\end{aligned}
$$

(ii) (Intersection) Let $A, B$ be independent permutation invariant random subsets. Then for $\sigma \in \mathcal{S}(E)$,

$$ 
\begin{aligned}
\mathbf{Pr}(A \cap B = c) &= \sum_{a,b \in \mathcal{P}(E); a \cap b = c} \mathbf{Pr}(A = a)\mathbf{Pr}(B = b) \\
&= \sum_{a,b \in \mathcal{P}(E); \sigma(a) \cap \sigma(b) = \sigma(c)} \mathbf{Pr}(A = \sigma(a))\mathbf{Pr}(B = \sigma(b)) \\
&= \sum_{a',b' \in \mathcal{P}(E); a' \cap b' = \sigma(c)} \mathbf{Pr}(A = a')\mathbf{Pr}(B = b') \quad (\text{by substitution}) \\
&= \mathbf{Pr}(A \cap B = \sigma(c)).
\end{aligned}
$$

(iii) (Union) Let $A, B$ be independent permutation invariant random subsets. Then $A \cup B = E \setminus ((E \setminus A) \cap (E \setminus B))$. So $A \cup B$ is permutation invariant. $\blacksquare$

We shall express the expectation and the variance of the random variable $|A|$ in terms of $\mathbf{Pr}(x \in A)$ and $\mathbf{Pr}(x \in A, y \in A)$, where $x, y$ are distinct elements in $E$.

**Lemma 2.3.** Let $A$ be a permutation invariant random subset of $E$. Let $x, y$ be distinct elements in $E$. Then:

(i) $\mathbb{E}(|A|) = n\mathbf{Pr}(x \in A)$,

(ii) $\mathrm{Var}(|A|) = \mathbb{E}(|A|) + n(n-1)\mathbf{Pr}(x \in A, y \in A) - \mathbb{E}(|A|^2)$.

*Proof.* We consider each item.

(i) By definition the probability $\mathbf{Pr}(z \in A)$ does not depend on the choice of element $z \in E$. So,

$$ \mathbb{E}(|A|) = \mathbb{E}\left(\sum_{z \in E} \mathbb{1}_{z \in A}\right) = \sum_{z \in E} \mathbf{Pr}(z \in A) = n\mathbf{Pr}(x \in A). $$

(ii) By the same argument, the probability $\mathbf{Pr}(z \in A, w \in A)$ does not depend on the choice of pair of distinct elements $(z, w)$ in $E$. So,

$$ \mathbb{E}(|A|^2) = \mathbb{E}\left[\left(\sum_{z \in E} \mathbb{1}_{z \in A}\right)^2\right] $$
$$
\begin{align*}
&= \sum_{z \in E} \Pr(z \in A) + \sum_{(z,w) \in E^2; z \neq w} \Pr(z \in A, w \in A) \\
&= \mathbb{E}(|A|) + n(n-1)\Pr(x \in A, y \in A). \tag*{\blacksquare}
\end{align*}
$$

A permutation invariant random subset can be decomposed into uniform random
subsets.

**Proposition 2.4** (Decomposition into uniform random subsets). Let *A* be a permuta-
tion invariant random subset of *E*.

(i) If $\mathbf{Pr}(|A| = k) \neq 0$, then the random subset $A$ under the condition $\{|A| = k\}$ is a uniform random subset on all subsets of $E$ of cardinality $k$.

(ii) Let $Q$ be an event described by $A$ (for example, $Q = \{x \in A\}$). Denote $\mathbb{N}_A = \{k \in \mathbb{N} | \mathbf{Pr}(|A|=k) \neq 0\}$, then

$$
\mathbf{Pr}(Q) = \sum_{k \in \mathbb{N}_A} \mathbf{Pr}(Q \mid |A|=k) \mathbf{Pr}(|A|=k).
$$

Proof. Suppose that $\mathbf{Pr}(|A| = k) \neq 0$. Let $a \subset E$ of cardinal $k$. As $A$ is permutation invariant,

$$
\Pr(|A| = k) = \binom{n}{k} \Pr(A = a).
$$

Hence,

$$
\mathbf{Pr}(A = a \mid |A| = k) = \frac{\mathbf{Pr}(A = a)}{\mathbf{Pr}(|A| = k)} = \left(\binom{n}{k}\right)^{-1}.
$$

If $|a| \neq k$ then $\Pr(A = a \mid |A| = k) = 0$.

The second assertion is the formula of total probability. ■

**Definition 2.5.** Let $A = (A_n)$ be a sequence of random subsets of $E = (E_n)$. It is a sequence of permutation invariant random subset if $A_n$ is a permutation invariant random subset of $E_n$ for all $n$.

**Notation.** Let $E = (E_n)$ be a sequence of finite sets. Denote $\mathcal{D}(E)$ the class of densable sequences of permutation invariant random subsets of $E$.

**Example 2.6.** We give three examples of sequences of random subsets that are dens-
able and permutation invariant.

1. Sequences of Bernoulli random subsets of *E* with density *d* ≠ 0 are in the class *D(E)*.

2. Sequences of uniform random subsets of *E* are in the class *D(E)*.
$$ 
\begin{aligned}
&= \sum_{z \in E} \mathbf{Pr}(z \in A) + \sum_{(z,w) \in E^2; z \neq w} \mathbf{Pr}(z \in A, w \in A) \\
&= \mathbb{E}(|A|) + n(n-1)\mathbf{Pr}(x \in A, y \in A).
\end{aligned}
\quad \blacksquare
$$

A permutation invariant random subset can be decomposed into uniform random subsets.

**Proposition 2.4** (Decomposition into uniform random subsets). Let A be a permutation invariant random subset of E.

(i) If $\mathbf{Pr}(|A| = k) \neq 0$, then the random subset A under the condition $\{|A| = k\}$ is a uniform random subset on all subsets of E of cardinality k.

(ii) Let $Q$ be an event described by A (for example, $Q = \{x \in A\}$). Denote $\mathbb{N}_A = \{k \in \mathbb{N} | \mathbf{Pr}(|A| = k) \neq 0\}$, then

$$ \mathbf{Pr}(Q) = \sum_{k \in \mathbb{N}_A} \mathbf{Pr}(Q \mid |A| = k)\mathbf{Pr}(|A| = k). $$

*Proof.* Suppose that $\mathbf{Pr}(|A| = k) \neq 0$. Let $a \subset E$ of cardinal k. As A is permutation invariant,

$$ \mathbf{Pr}(|A| = k) = \binom{n}{k} \mathbf{Pr}(A = a). $$

Hence,

$$ \mathbf{Pr}(A = a \mid |A| = k) = \frac{\mathbf{Pr}(A = a)}{\mathbf{Pr}(|A| = k)} = \binom{n}{k}^{-1}. $$

If $|a| \neq k$ then $\mathbf{Pr}(A = a \mid |A| = k) = 0$.

The second assertion is the formula of total probability. ■

**Definition 2.5.** Let $A = (A_n)$ be a sequence of random subsets of $E = (E_n)$. It is a sequence of permutation invariant random subset if $A_n$ is a permutation invariant random subset of $E_n$ for all n.

**Notation.** Let $E = (E_n)$ be a sequence of finite sets. Denote $\mathcal{D}(E)$ the class of densable sequences of permutation invariant random subsets of E.

**Example 2.6.** We give three examples of sequences of random subsets that are densable and permutation invariant.

1. Sequences of Bernoulli random subsets of E with density $d \neq 0$ are in the class $\mathcal{D}(E)$.

2. Sequences of uniform random subsets of E are in the class $\mathcal{D}(E)$.
3. Let $A, B$ be independent sequences of uniform random subsets. By Lemma 2.2, the sequence $A \cap B$ is permutation invariant. By Proposition 1.18, if $\text{dens } A + \text{dens } B \neq 1$, then $A \cap B$ is densable. In this case the sequence $A \cap B$ is in the class $\mathcal{D}(E)$.

Except for some special cases, the class $\mathcal{D}(E)$ is closed under set theoretic operations:

**Proposition 2.7.** Let $A, B \in \mathcal{D}(E)$ with densities $\alpha, \beta$. Then the union $A \cup B$ is in $\mathcal{D}(E)$ and $\text{dens}(A \cup B) = \max(\alpha, \beta)$.

*Proof.* By Lemma 2.2, the sequence of random subset $A \cup B$ is permutation invariant. The cases $\alpha = -\infty$ or $\beta = -\infty$ can be easily shown. Without loss of generality, assume that $\alpha \ge \beta \ge 0$.

Let $\varepsilon > 0$. By densabilities of $A$ and $B$, a.a.s.

$$n^{\alpha-\varepsilon/2} \le |A_n| \le n^{\alpha+\varepsilon/2},$$

$$n^{\beta-\varepsilon/2} \le |B_n| \le n^{\beta+\varepsilon/2}.$$

Thus, a.a.s.

$$n^{\alpha-\varepsilon} \le |A_n| \le |A_n \cup B_n| \le n^{\alpha+\varepsilon/2} + n^{\beta+\varepsilon/2} \le 2n^{\alpha+\varepsilon/2} \le n^{\alpha+\varepsilon}. \quad \blacksquare$$

**Proposition 2.8.** Let $A \in \mathcal{D}(E)$ with density $\alpha < 1$. Then the complement $E \setminus A$ is in $\mathcal{D}(E)$ and $\text{dens}(E \setminus A) = 1$.

*Proof.* Again by Lemma 2.2 the sequence of random subset $E \setminus A$ is permutation invariant.

Let $0 < \varepsilon < (1 - \alpha)/2$. By densablility of $A$, a.a.s.

$$|A_n| \le n^{\alpha+\varepsilon}.$$

As $n^{\alpha+\varepsilon} + n^{1-\varepsilon} \le n$ for $n$ large enough, a.a.s.

$$|E_n \setminus A_n| \ge n - n^{\alpha+\varepsilon} \ge n^{1-\varepsilon}. \quad \blacksquare$$

## 2.2. The intersection formula

In this subsection we shall prove the intersection formula for the class of densable sequences of permutation invariant random subsets.

**Theorem 2.9** (The intersection formula). Let $A, B$ be independent sequences in $\mathcal{D}(E)$ with densities $\alpha, \beta$. If $\alpha + \beta \neq 1$, then the sequence $A \cap B$ is in $\mathcal{D}(E)$ and

$$\text{dens}(A \cap B) = \begin{cases} \alpha + \beta - 1 & \text{if } \alpha + \beta > 1, \\ -\infty & \text{if } \alpha + \beta < 1. \end{cases}$$
3. Let $A, B$ be independent sequences of uniform random subsets. By Lemma 2.2, the sequence $A \cap B$ is permutation invariant. By Proposition 1.18, if $\text{dens } A + \text{dens } B \neq 1$, then $A \cap B$ is densable. In this case the sequence $A \cap B$ is in the class $\mathcal{D}(E)$.

Except for some special cases, the class $\mathcal{D}(E)$ is closed under set theoretic operations:

**Proposition 2.7.** Let $A, B \in \mathcal{D}(E)$ with densities $\alpha, \beta$. Then the union $A \cup B$ is in $\mathcal{D}(E)$ and $\text{dens}(A \cup B) = \max(\alpha, \beta)$.

*Proof.* By Lemma 2.2, the sequence of random subset $A \cup B$ is permutation invariant. The cases $\alpha = -\infty$ or $\beta = -\infty$ can be easily shown. Without loss of generality, assume that $\alpha \ge \beta \ge 0$.

Let $\varepsilon > 0$. By densabilities of $A$ and $B$, a.a.s.

$$n^{\alpha-\varepsilon/2} \le |A_n| \le n^{\alpha+\varepsilon/2},$$

$$n^{\beta-\varepsilon/2} \le |B_n| \le n^{\beta+\varepsilon/2}.$$

Thus, a.a.s.

$$n^{\alpha-\varepsilon} \le |A_n| \le |A_n \cup B_n| \le n^{\alpha+\varepsilon/2} + n^{\beta+\varepsilon/2} \le 2n^{\alpha+\varepsilon/2} \le n^{\alpha+\varepsilon}. \quad \blacksquare$$

**Proposition 2.8.** Let $A \in \mathcal{D}(E)$ with density $\alpha < 1$. Then the complement $E \setminus A$ is in $\mathcal{D}(E)$ and $\text{dens}(E \setminus A) = 1$.

*Proof.* Again by Lemma 2.2 the sequence of random subset $E \setminus A$ is permutation invariant.

Let $0 < \varepsilon < (1 - \alpha)/2$. By densablility of $A$, a.a.s.

$$|A_n| \le n^{\alpha+\varepsilon}.$$

As $n^{\alpha+\varepsilon} + n^{1-\varepsilon} \le n$ for $n$ large enough, a.a.s.

$$|E_n \setminus A_n| \ge n - n^{\alpha+\varepsilon} \ge n^{1-\varepsilon}. \quad \blacksquare$$

## 2.2. The intersection formula

In this subsection we shall prove the intersection formula for the class of densable sequences of permutation invariant random subsets.

**Theorem 2.9** (The intersection formula). Let $A, B$ be independent sequences in $\mathcal{D}(E)$ with densities $\alpha, \beta$. If $\alpha + \beta \neq 1$, then the sequence $A \cap B$ is in $\mathcal{D}(E)$ and

$$\text{dens}(A \cap B) = \begin{cases} \alpha + \beta - 1 & \text{if } \alpha + \beta > 1, \\ -\infty & \text{if } \alpha + \beta < 1. \end{cases}$$
**Lemma 2.10.** Let $\alpha, \beta \in [0, 1]$ such that $\alpha + \beta > 1$. Let $0 < \varepsilon < \alpha + \beta - 1$. Let $A, B$ independent sequences of uniform random subsets of $E$ with densities $\alpha', \beta'$ with $\alpha' \in [\alpha - \varepsilon/3, \alpha + \varepsilon/3]$ and $\beta' \in [\beta - \varepsilon/3, \beta + \varepsilon/3]$. If $n \ge \max\{2^{3/\varepsilon}, 8^{1/(\alpha+\beta-1-\varepsilon)}\}$, then

$$ \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon}) \ge 1 - \frac{48}{n^{\alpha+\beta-1-\varepsilon}} \xrightarrow{n \to \infty} 1. $$

*Proof.* By hypothesis $\alpha' + \beta' - 1 \ge \alpha + \beta - 2\varepsilon/3 - 1 > 0$. Apply Lemma 1.17 (iii) with $c = \frac{1}{2}$, for $n \ge 8^{1/(\alpha+\beta-1-\varepsilon)} \ge 8^{1/(\alpha'+\beta'-1)}$, we have

$$ \Pr\left(\left|A_n \cap B_n\right| - n^{\alpha' + \beta' - 1} \ge \frac{1}{2} n^{\alpha' + \beta' - 1}\right) \le \frac{48}{n^{\alpha' + \beta' - 1}}. $$

Considering the complement event, this inequality is equivalent to

$$ \Pr\left(\frac{1}{2} n^{\alpha' + \beta' - 1} < |A_n \cap B_n| < \frac{3}{2} n^{\alpha' + \beta' - 1}\right) > 1 - \frac{48}{n^{\alpha' + \beta' - 1}}. $$

Again by hypothesis,

$$ \alpha + \beta - 1 - 2\varepsilon/3 \le \alpha' + \beta' - 1 \le \alpha + \beta - 1 + 2\varepsilon/3. $$

If $n \ge 2^{3/\varepsilon}$, then

$$ n^{\alpha+\beta-1-\varepsilon} \le \frac{1}{2} n^{\alpha+\beta-1-2\varepsilon/3} \le \frac{3}{2} n^{\alpha+\beta-1+2\varepsilon/3} \le n^{\alpha+\beta-1+\varepsilon}, $$

so,

$$ \begin{aligned} \Pr(n^{\alpha+\beta-1-\varepsilon} &\le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon}) \\ &\ge \Pr\left(\frac{1}{2} n^{\alpha+\beta-1-2\varepsilon/3} \le |A_n \cap B_n| \le \frac{3}{2} n^{\alpha+\beta-1+2\varepsilon/3}\right) \\ &\ge \Pr\left(\frac{1}{2} n^{\alpha'+\beta'-1} < |A_n \cap B_n| < \frac{3}{2} n^{\alpha'+\beta'-1}\right). \end{aligned} $$

Combine two estimations on $n$. If $n \ge \max\{2^{3/\varepsilon}, 8^{1/(\alpha+\beta-1-\varepsilon)}\}$, then:

$$ \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon}) \ge 1 - \frac{48}{n^{\alpha+\beta-1-\varepsilon}} \ge 1 - \frac{48}{n^{\alpha+\beta-1-\varepsilon}}. $$

As $\alpha + \beta - 1 - \varepsilon > 0$, when $n$ goes to infinity

$$ \frac{48}{n^{\alpha+\beta-1-\varepsilon}} \xrightarrow{n \to \infty} 0. $$

■

*Proof of Theorem 2.9.* By Lemma 2.2, the intersection $A \cap B$ is a sequence of per-mutation invariant random subsets. In either case, denote $(Q_n)$ the sequence of events defined by

$$ Q_n = \{n^{\alpha-\varepsilon/3} \le |A_n| \le n^{\alpha+\varepsilon/3} \text{ and } n^{\beta-\varepsilon/3} \le |B_n| \le n^{\beta+\varepsilon/3}\} $$
**Lemma 2.10.** Let $\alpha, \beta \in [0, 1]$ such that $\alpha + \beta > 1$. Let $0 < \varepsilon < \alpha + \beta - 1$. Let $A, B$ independent sequences of uniform random subsets of $E$ with densities $\alpha', \beta'$ with $\alpha' \in [\alpha - \varepsilon/3, \alpha + \varepsilon/3]$ and $\beta' \in [\beta - \varepsilon/3, \beta + \varepsilon/3]$. If $n \ge \max\{2^{3/\varepsilon}, 8^{1/(\alpha+\beta-1-\varepsilon)}\}$, then

$$ \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon}) \ge 1 - \frac{48}{n^{\alpha+\beta-1-\varepsilon}} \xrightarrow{n \to \infty} 1. $$

*Proof.* By hypothesis $\alpha' + \beta' - 1 \ge \alpha + \beta - 2\varepsilon/3 - 1 > 0$. Apply Lemma 1.17 (iii) with $c = \frac{1}{2}$, for $n \ge 8^{1/(\alpha+\beta-1-\varepsilon)} \ge 8^{1/(\alpha'+\beta'-1)}$, we have

$$ \Pr\left(\left|A_n \cap B_n\right| - n^{\alpha' + \beta' - 1} \ge \frac{1}{2} n^{\alpha' + \beta' - 1}\right) \le \frac{48}{n^{\alpha' + \beta' - 1}}. $$

Considering the complement event, this inequality is equivalent to

$$ \Pr\left(\frac{1}{2}n^{\alpha' + \beta' - 1} < |A_n \cap B_n| < \frac{3}{2}n^{\alpha' + \beta' - 1}\right) > 1 - \frac{48}{n^{\alpha' + \beta' - 1}}. $$

Again by hypothesis,

$$ \alpha + \beta - 1 - 2\varepsilon/3 \le \alpha' + \beta' - 1 \le \alpha + \beta - 1 + 2\varepsilon/3. $$

If $n \ge 2^{3/\varepsilon}$, then

$$ n^{\alpha+\beta-1-\varepsilon} \le \frac{1}{2} n^{\alpha+\beta-1-2\varepsilon/3} \le \frac{3}{2} n^{\alpha+\beta-1+2\varepsilon/3} \le n^{\alpha+\beta-1+\varepsilon}, $$

so,

$$ \begin{aligned} \Pr(n^{\alpha+\beta-1-\varepsilon} &\le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon}) \\ &\ge \Pr\left(\frac{1}{2}n^{\alpha+\beta-1-2\varepsilon/3} \le |A_n \cap B_n| \le \frac{3}{2}n^{\alpha+\beta-1+2\varepsilon/3}\right) \\ &\ge \Pr\left(\frac{1}{2}n^{\alpha'+\beta'-1} < |A_n \cap B_n| < \frac{3}{2}n^{\alpha'+\beta'-1}\right). \end{aligned} $$

Combine two estimations on $n$. If $n \ge \max\{2^{3/\varepsilon}, 8^{1/(\alpha+\beta-1-\varepsilon)}\}$, then:

$$ \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon}) \ge 1 - \frac{48}{n^{\alpha+\beta-1-\varepsilon}} \ge 1 - \frac{48}{n^{\alpha+\beta-1-\varepsilon}}. $$

As $\alpha + \beta - 1 - \varepsilon > 0$, when $n$ goes to infinity

$$ \frac{48}{n^{\alpha+\beta-1-\varepsilon}} \xrightarrow{n \to \infty} 0. $$

■

*Proof of Theorem 2.9.* By Lemma 2.2, the intersection $A \cap B$ is a sequence of per-mutation invariant random subsets. In either case, denote $(Q_n)$ the sequence of events defined by

$$ Q_n = \{n^{\alpha-\varepsilon/3} \le |A_n| \le n^{\alpha+\varepsilon/3} \text{ and } n^{\beta-\varepsilon/3} \le |B_n| \le n^{\beta+\varepsilon/3}\} $$
for some small $\varepsilon > 0$. By the densabilities of $\mathbf{A}$ and $\mathbf{B}$, a.a.s. $Q_n$ is true. Note that $Q_n$ is a union of events of type $\{|A_n| = k, |B_n| = l\}$. Denote

$$
\mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2 := \{(k, l) \in \mathbb{N}^2 | n^{\alpha-\varepsilon/3} \le k \le n^{\alpha+\varepsilon/3}, n^{\beta-\varepsilon/3} \le l \le n^{\beta+\varepsilon/3} \\
\text{and } \mathbf{Pr}(|A_n| = k, |B_n| = l) \ne 0\}.
$$

For $(k, l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2$, we may do a change of variables $k = n^{\alpha'}$, $l = n^{\beta'}$ so that
$$ \alpha - \varepsilon/3 \le \alpha' \le \alpha + \varepsilon/3 \quad \text{and} \quad \beta - \varepsilon/3 \le \beta' \le \beta + \varepsilon/3. $$

(i) Suppose that $\alpha + \beta < 1$. Let $0 < \varepsilon < 1 - \alpha - \beta$. We shall prove that a.a.s.
$A_n \cap B_n = \emptyset$. By the formula of total probability and Markov's inequality,

$$
\begin{align*}
\Pr(A_n \cap B_n \neq \emptyset) &\le \Pr(|A_n \cap B_n| \ge 1 | Q_n)\Pr(Q_n) + \Pr(\overline{Q_n}) \\
&\le \sum_{(k,l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2} \left[ \Pr(|A_n \cap B_n| \ge 1 | |A_n| = k, |B_n| = l) \Pr(|A_n| = k, |B_n| = l) \right] + \Pr(\overline{Q_n}) \\
&\le \sum_{(k,l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2} \left[ \mathbb{E}(|A_n \cap B_n| | |A_n| = k, |B_n| = l) \Pr(|A_n| = k, |B_n| = l) \right] + \Pr(\overline{Q_n}).
\end{align*}
$$

For any $(k, l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2$, by Lemma 1.17 (i), we have

$$
\begin{align*}
\mathbb{E}(|A_n \cap B_n| \mid |A_n| = k, |B_n| = l) &= \mathbb{E}(|A_n \cap B_n| \mid |A_n| = n^{\alpha'}, |B_n| = n^{\beta'}) \\
&\le n^{\alpha' + \beta' - 1} \le n^{\alpha + \beta + 2/3\varepsilon - 1} \le n^{-1/3\varepsilon}.
\end{align*}
$$

Hence,

$$
\mathbf{Pr}(A_n \cap B_n \neq \emptyset) \leq n^{-1/3\varepsilon} \mathbf{Pr}(Q_n) + \mathbf{Pr}(\overline{Q_n}) \xrightarrow{n \to \infty} 0.
$$

(ii) Suppose that $\alpha + \beta > 1$. Let $0 < \varepsilon < \alpha + \beta - 1$. We shall prove that a.a.s.

$$
n^{\alpha+\beta-1-\varepsilon} \leq |A_n \cap B_n| \leq n^{\alpha+\beta-1+\varepsilon}.
$$

By the formula of total probability,

$$
\begin{align*}
& \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon}) \\
& \ge \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon} | Q_n) \Pr(Q_n) \\
& = \sum_{(k,l) \in \mathbb{N}_{\mathbf{A},\mathbf{B},n,\varepsilon}^2} \left[ \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon} | |A_n|=k, |B_n|=l) \right. \\
& \qquad \left. \Pr(|A_n|=k, |B_n|=l) \right].
\end{align*}
$$
for some small $\varepsilon > 0$. By the densabilities of $\mathbf{A}$ and $\mathbf{B}$, a.a.s. $Q_n$ is true. Note that $Q_n$ is a union of events of type $\{|A_n| = k, |B_n| = l\}$. Denote

$$
\mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2 := \{(k, l) \in \mathbb{N}^2 | n^{\alpha-\varepsilon/3} \le k \le n^{\alpha+\varepsilon/3}, n^{\beta-\varepsilon/3} \le l \le n^{\beta+\varepsilon/3} \\
\text{and } \mathbf{Pr}(|A_n| = k, |B_n| = l) \ne 0\}.
$$

For $(k, l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2$, we may do a change of variables $k = n^{\alpha'}$, $l = n^{\beta'}$ so that
$$ \alpha - \varepsilon/3 \le \alpha' \le \alpha + \varepsilon/3 \quad \text{and} \quad \beta - \varepsilon/3 \le \beta' \le \beta + \varepsilon/3. $$

(i) Suppose that $\alpha + \beta < 1$. Let $0 < \varepsilon < 1 - \alpha - \beta$. We shall prove that a.a.s.
$A_n \cap B_n = \emptyset$. By the formula of total probability and Markov's inequality,

$$
\begin{align*}
\Pr(A_n \cap B_n \neq \emptyset) &\le \Pr(|A_n \cap B_n| \ge 1 | Q_n)\Pr(Q_n) + \Pr(\overline{Q_n}) \\
&\le \sum_{(k,l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2} \left[ \Pr(|A_n \cap B_n| \ge 1 | |A_n| = k, |B_n| = l) \Pr(|A_n| = k, |B_n| = l) \right] + \Pr(\overline{Q_n}) \\
&\le \sum_{(k,l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2} \left[ \mathbb{E}(|A_n \cap B_n| | |A_n| = k, |B_n| = l) \Pr(|A_n| = k, |B_n| = l) \right] + \Pr(\overline{Q_n}).
\end{align*}
$$

For any $(k, l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2$, by Lemma 1.17 (i), we have

$$
\begin{align*}
\mathbb{E}(|A_n \cap B_n| \mid |A_n| = k, |B_n| = l) &= \mathbb{E}(|A_n \cap B_n| \mid |A_n| = n^{\alpha'}, |B_n| = n^{\beta'}) \\
&\le n^{\alpha' + \beta' - 1} \le n^{\alpha + \beta + 2/3\varepsilon - 1} \le n^{-1/3\varepsilon}.
\end{align*}
$$

Hence,

$$
\mathbf{Pr}(A_n \cap B_n \neq \emptyset) \leq n^{-1/3\varepsilon} \mathbf{Pr}(Q_n) + \mathbf{Pr}(\overline{Q_n}) \xrightarrow{n \to \infty} 0.
$$

(ii) Suppose that $\alpha + \beta > 1$. Let $0 < \varepsilon < \alpha + \beta - 1$. We shall prove that a.a.s.

$$
n^{\alpha+\beta-1-\varepsilon} \leq |A_n \cap B_n| \leq n^{\alpha+\beta-1+\varepsilon}.
$$

By the formula of total probability,

$$
\begin{align*}
& \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon}) \\
& \ge \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon} | Q_n) \Pr(Q_n) \\
& = \sum_{(k,l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \varepsilon}^2} \left[ \Pr(n^{\alpha+\beta-1-\varepsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\varepsilon} | |A_n| = k, |B_n| = l) \right. \\
& \qquad \left. \Pr(|A_n| = k, |B_n| = l) \right].
\end{align*}
$$
By Lemma 2.10 and Proposition 2.4. If $n \ge \max\{2^{3/\epsilon}, 8^{1/(\alpha+\beta-1-\epsilon)}\}$, then for any $(k, l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \epsilon}^2$, we have

$$
\begin{aligned}
& \mathrm{Pr}(n^{\alpha+\beta-1-\epsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\epsilon} \quad |A_n| = k, |B_n| = l) \\
& = \mathrm{Pr}(n^{\alpha+\beta-1-\epsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\epsilon} \quad |A_n| = n^{\alpha'}, |B_n| = n^{\beta'}) \\
& \ge 1 - \frac{48}{n^{\alpha+\beta-1+\epsilon}} \xrightarrow{n \to \infty} 1.
\end{aligned}
$$

Hence, for $n \ge \max\{2^{3/\epsilon}, 8^{1/(\alpha+\beta-1-\epsilon)}\}$, we obtain

$$
\begin{aligned}
& \mathrm{Pr}(n^{\alpha+\beta-1-\epsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\epsilon}) \\
& \ge \sum_{(k,l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \epsilon}^2} \left(1 - \frac{48}{n^{\alpha+\beta-1+\epsilon}}\right) \mathrm{Pr}(|A_n| = k, |B_n| = l) \\
& \ge \left(1 - \frac{48}{n^{\alpha+\beta-1+\epsilon}}\right) \mathrm{Pr}(Q_n) \xrightarrow{n \to \infty} 1.
\end{aligned}
\qquad \blacksquare
$$

Remark that when $\alpha + \beta = 1$, the density is not determined, as Proposition 1.16 showed for Bernoulli random subsets. As the class is closed under intersection, we can conclude on multiple intersections.

**Corollary 2.11.** Let $A_1, \dots, A_k$ be independent sequences in $\mathcal{D}(E)$ of positive densities. If $\sum_{i=1}^k$ codens $A_i < 1$, then

$$ \text{codens} \left( \bigcap_{i=1}^{k} A_i \right) = \sum_{i=1}^{k} \text{codens} A_i. $$

If $\sum_{i=1}^k$ codens $A_i > 1$, then

$$ \mathrm{dens} \left( \bigcap_{i=1}^{k} A_i \right) = -\infty. $$

## 2.3. Another model: Random functions

We give here another natural model of random subsets: image of a random function, which can be found in [9, p.270] “Self-intersection formula” by Gromov. This is also a variance of random groups considered by Ollivier in [16, Lemma 59]. In this subsection, we prove that such a model is densable and permutation invariant.

**Definition 2.12.** Let $E, F$ be finite subsets of cardinalities $n, m$. Denote $E^F$ the set of functions from $F$ to $E$. A random function $\Phi$ from $F$ to $E$ is a $E^F$-valued random variable.
By Lemma 2.10 and Proposition 2.4. If $n \ge \max\{2^{3/\epsilon}, 8^{1/(\alpha+\beta-1-\epsilon)}\}$, then for any $(k, l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \epsilon}^2$, we have

$$
\begin{aligned}
& \mathrm{Pr}(n^{\alpha+\beta-1-\epsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\epsilon} \quad |A_n| = k, |B_n| = l) \\
& = \mathrm{Pr}(n^{\alpha+\beta-1-\epsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\epsilon} \quad |A_n| = n^{\alpha'}, |B_n| = n^{\beta'}) \\
& \ge 1 - \frac{48}{n^{\alpha+\beta-1+\epsilon}} \xrightarrow{n \to \infty} 1.
\end{aligned}
$$

Hence, for $n \ge \max\{2^{3/\epsilon}, 8^{1/(\alpha+\beta-1-\epsilon)}\}$, we obtain

$$
\begin{aligned}
& \mathrm{Pr}(n^{\alpha+\beta-1-\epsilon} \le |A_n \cap B_n| \le n^{\alpha+\beta-1+\epsilon}) \\
& \ge \sum_{(k,l) \in \mathbb{N}_{\mathbf{A}, \mathbf{B}, n, \epsilon}^2} \left(1 - \frac{48}{n^{\alpha+\beta-1+\epsilon}}\right) \mathrm{Pr}(|A_n| = k, |B_n| = l) \\
& \ge \left(1 - \frac{48}{n^{\alpha+\beta-1+\epsilon}}\right) \mathrm{Pr}(Q_n) \xrightarrow{n \to \infty} 1.
\end{aligned}
\qquad \blacksquare
$$

Remark that when $\alpha + \beta = 1$, the density is not determined, as Proposition 1.16 showed for Bernoulli random subsets. As the class is closed under intersection, we can conclude on multiple intersections.

**Corollary 2.11.** Let $A_1, \dots, A_k$ be independent sequences in $\mathcal{D}(E)$ of positive densities. If $\sum_{i=1}^k$ codens $A_i < 1$, then

$$
\text{codens} \left( \bigcap_{i=1}^{k} A_i \right) = \sum_{i=1}^{k} \text{codens } A_i.
$$

If $\sum_{i=1}^k$ codens $A_i > 1$, then

$$
\mathrm{dens}\left(\bigcap_{i=1}^{k} A_{i}\right)=-\infty.
$$

**2.3. Another model: Random functions**

We give here another natural model of random subsets: image of a random function, which can be found in [9, p.270] “Self-intersection formula” by Gromov. This is also a variance of random groups considered by Ollivier in [16, Lemma 59]. In this subsection, we prove that such a model is densable and permutation invariant.

**Definition 2.12.** Let $E, F$ be finite subsets of cardinalities $n, m$. Denote $E^F$ the set of functions from $F$ to $E$. A random function $\Phi$ from $F$ to $E$ is a $E^F$-valued random variable.
Let $\Phi$ be a random function from $F$ to $E$. Its law is determined by

$$ \mathbf{Pr}(\Phi = \varphi) $$

through all $\varphi \in E^F$.

The random function $\Phi$ can be regarded as a vector of $E$-valued random variables (or random elements of $E$) $(\Phi(y))_{y \in F}$ indexed by $F$. Note that these random elements are not necessarily independent. The image $\mathrm{Im}(\Phi) = \Phi(F) := \{\Phi(y)|y \in F\}$ is then a random subset of $E$.

**Example 2.13** (Uniform random function). Let $\Phi$ be the uniform distribution on all functions from $F$ to $E$. Its law is

$$ \mathbf{Pr}(\Phi = \varphi) = \frac{1}{|E^F|} = \frac{1}{n^m} $$

through all $\varphi \in E^F$.

**Proposition 2.14.** Let $\Phi$ be a uniform random function from $F$ to $E$. Then the random elements $(\Phi(y))_{y \in F}$ are independent (identical) uniform distributions on $E$.

*Proof.* Let $x \in E$, $y \in F$. The number of functions $\varphi$ from $F$ to $E$ such that $\varphi(y) = x$ is $n^{m-1}$. So the law of $\Phi(y)$ is

$$ \mathbf{Pr}(\Phi(y) = x) = \frac{n^{m-1}}{n^m} = \frac{1}{n}. $$

Which is a uniform distribution on $E$.

Denote $F = \{y_1, \dots, y_m\}$. Let $(x_1, \dots, x_m)$ be a vector of $m$ elements in $E$. Let $\varphi \in E^F$ such that $\varphi(y_i) = x_i$ for all $1 \le i \le m$. Then

$$ \mathbf{Pr}\left(\bigwedge_{i=1}^{m} \Phi(y_i) = x_i\right) = \mathbf{Pr}(\Phi = \varphi) = \frac{1}{n^m} = \prod_{i=1}^{m} \mathbf{Pr}(\Phi(y_i) = x_i). \quad \blacksquare $$

**Proposition 2.15.** The image of a uniform random function is a permutation invariant random subset.

*Proof.* Let $\Phi$ be a uniform random function from $F$ to $E$. Let $\sigma \in S(E)$, then for all $\varphi \in E^F$, we have

$$ \mathbf{Pr}(\Phi = \varphi) = \mathbf{Pr}(\Phi = \sigma \circ \varphi) = \mathbf{Pr}(\sigma^{-1} \circ \Phi = \varphi). $$

The random function $\sigma^{-1} \circ \Phi$ has the same law of $\Phi$. Now let $a \subset E$, then

$$ \mathbf{Pr}(\mathrm{Im}(\Phi) = a) = \mathbf{Pr}(\mathrm{Im}(\sigma^{-1} \circ \Phi) = a) = \mathbf{Pr}(\mathrm{Im}(\Phi) = \sigma(a)). \quad \blacksquare $$
Let $\Phi$ be a random function from $F$ to $E$. Its law is determined by

$$ \mathbf{Pr}(\Phi = \varphi) $$

through all $\varphi \in E^F$.

The random function $\Phi$ can be regarded as a vector of $E$-valued random variables (or random elements of $E$) $(\Phi(y))_{y \in F}$ indexed by $F$. Note that these random elements are not necessarily independent. The image $\mathrm{Im}(\Phi) = \Phi(F) := \{\Phi(y)|y \in F\}$ is then a random subset of $E$.

**Example 2.13** (Uniform random function). Let $\Phi$ be the uniform distribution on all functions from $F$ to $E$. Its law is

$$ \mathbf{Pr}(\Phi = \varphi) = \frac{1}{|E^F|} = \frac{1}{n^m} $$

through all $\varphi \in E^F$.

**Proposition 2.14.** Let $\Phi$ be a uniform random function from $F$ to $E$. Then the random elements $(\Phi(y))_{y \in F}$ are independent (identical) uniform distributions on $E$.

*Proof.* Let $x \in E$, $y \in F$. The number of functions $\varphi$ from $F$ to $E$ such that $\varphi(y) = x$ is $n^{m-1}$. So the law of $\Phi(y)$ is

$$ \mathbf{Pr}(\Phi(y) = x) = \frac{n^{m-1}}{n^m} = \frac{1}{n}. $$

Which is a uniform distribution on $E$.

Denote $F = \{y_1, \dots, y_m\}$. Let $(x_1, \dots, x_m)$ be a vector of $m$ elements in $E$. Let $\varphi \in E^F$ such that $\varphi(y_i) = x_i$ for all $1 \le i \le m$. Then

$$ \mathbf{Pr}\left(\bigwedge_{i=1}^{m} \Phi(y_i) = x_i\right) = \mathbf{Pr}(\Phi = \varphi) = \frac{1}{n^m} = \prod_{i=1}^{m} \mathbf{Pr}(\Phi(y_i) = x_i). \quad \blacksquare $$

**Proposition 2.15.** The image of a uniform random function is a permutation invariant random subset.

*Proof.* Let $\Phi$ be a uniform random function from $F$ to $E$. Let $\sigma \in S(E)$, then for all $\varphi \in E^F$, we have

$$ \mathbf{Pr}(\Phi = \varphi) = \mathbf{Pr}(\Phi = \sigma \circ \varphi) = \mathbf{Pr}(\sigma^{-1} \circ \Phi = \varphi). $$

The random function $\sigma^{-1} \circ \Phi$ has the same law of $\Phi$. Now let $a \subset E$, then

$$ \mathbf{Pr}(\mathrm{Im}(\Phi) = a) = \mathbf{Pr}(\mathrm{Im}(\sigma^{-1} \circ \Phi) = a) = \mathbf{Pr}(\mathrm{Im}(\Phi) = \sigma(a)). \quad \blacksquare $$
### 3. The multi-dimensional intersection formula

Let $E = (E_n)$ be a sequence of finite sets with $|E_n| = n$ and $k \ge 2$ be an integer. The set of pairwise different $k$-tuples of $E_n$ is

$$E_n^{(k)} := \{(x_1, \dots, x_k) \in E_n^k \mid x_i \neq x_j \ \forall i \neq j\}.$$

Denote $E^{(k)} = (E_n^{(k)})_{n \in \mathbb{N}}$.

Similarly, for a sequence of random subsets $A = (A_n)$ of $E$, we can define

$$A_n^{(k)} := \{(x_1, \dots, x_k) \in A_n^k \mid x_i \neq x_j \ \forall i \neq j\},$$

which is a random subset of $E_n^{(k)}$. Denote also $A^{(k)} = (A_n^{(k)})$. We will establish an intersection formula between a sequence of random subsets of type $A^{(k)}$ and a sequence of fixed subsets $X = (X_n)$ of $E^{(k)}$.

**Proposition 3.1.** Let $A$ be a densable sequence of random subsets of $E$ with density $d > 0$. Then $A^{(k)}$ is a densable sequence of random subsets of $E^{(k)}$ with density $d$. Namely,

$$\mathrm{dens}_{E^{(k)}}(A^{(k)}) = \mathrm{dens}_{E}(A).$$

*Proof.* Note that $n^k - k^2(n-1)^k \le |E_n^{(k)}| \le n^k$, so $|E_n^{(k)}| = n^{k+o(1)}$.

Let $\varepsilon > 0$. By densability a.a.s. $n^{d-\varepsilon/2} \le |A_n| \le n^{d+\varepsilon/2}$. By the same argument above, a.a.s. $|A_n^{(k)}| = |A_n|^{k+o(1)}$ as random variables. Hence, a.a.s.

$$(n^k)^{d-\varepsilon/2+o(1)} \le |A_n^{(k)}| \le (n^k)^{d+\varepsilon/2+o(1)},$$

so a.a.s.

$$|E_n^{(k)}|^{d-\varepsilon} \le |A_n^{(k)}| \le |E_n^{(k)}|^{d+\varepsilon}. \quad \blacksquare$$

Although the densability is preserved, it is not the case for being permutation invariant. Given a permutation invariant random subset $A_n$ of $E_n$, the random subset $A_n^{(k)}$ is not permutation invariant in $E_n^{(k)}$ for $k \ge 2$. See the following example.

**Example 3.2.** Let $(A_n)$ be a sequence of Bernoulli random subsets of $(E_n)$ with density $0 < d < 1$. Recall that subsets of the same cardinality have the same probability to be included in a permutation invariant random subset. Let $x_1, \dots, x_4$ be distinct elements in $E_n$.

$$\mathrm{Pr}(\{(x_1, x_2), (x_3, x_4)\} \subset A_n^{(2)}) = \mathrm{Pr}(\{x_1, x_2, x_3, x_4\} \subset A_n) = n^{4(d-1)},$$

while

$$\mathrm{Pr}(\{(x_1, x_2), (x_2, x_3)\} \subset A_n^{(2)}) = \mathrm{Pr}(\{x_1, x_2, x_3\} \subset A_n) = n^{3(d-1)}.$$
**3. The multi-dimensional intersection formula**

Let $\mathbf{E} = (E_n)$ be a sequence of finite sets with $|E_n| = n$ and $k \ge 2$ be an integer. The set of pairwise different $k$-tuples of $E_n$ is

$$E_n^{(k)} := \{(x_1, \dots, x_k) \in E_n^k \mid x_i \neq x_j \ \forall i \neq j\}.$$

Denote $\mathbf{E}^{(k)} = (E_n^{(k)})_{n \in \mathbb{N}}$.

Similarly, for a sequence of random subsets $\mathbf{A} = (A_n)$ of $\mathbf{E}$, we can define

$$A_n^{(k)} := \{(x_1, \dots, x_k) \in A_n^k \mid x_i \neq x_j \ \forall i \neq j\},$$

which is a random subset of $E_n^{(k)}$. Denote also $\mathbf{A}^{(k)} = (A_n^{(k)})$. We will establish an intersection formula between a sequence of random subsets of type $\mathbf{A}^{(k)}$ and a sequence of fixed subsets $\mathbf{X} = (X_n)$ of $\mathbf{E}^{(k)}$.

**Proposition 3.1.** Let $\mathbf{A}$ be a densable sequence of random subsets of $\mathbf{E}$ with density $d > 0$. Then $\mathbf{A}^{(k)}$ is a densable sequence of random subsets of $\mathbf{E}^{(k)}$ with density $d$. Namely,

$$\mathrm{dens}_{\mathbf{E}^{(k)}}(\mathbf{A}^{(k)}) = \mathrm{dens}_{\mathbf{E}}(\mathbf{A}).$$

*Proof.* Note that $n^k - k^2(n-1)^k \le |E_n^{(k)}| \le n^k$, so $|E_n^{(k)}| = n^{k+o(1)}$.

Let $\varepsilon > 0$. By densability a.a.s. $n^{d-\varepsilon/2} \le |A_n| \le n^{d+\varepsilon/2}$. By the same argument above, a.a.s. $|A_n^{(k)}| = |A_n|^{k+o(1)}$ as random variables. Hence, a.a.s.

$$(n^k)^{d-\varepsilon/2+o(1)} \le |A_n^{(k)}| \le (n^k)^{d+\varepsilon/2+o(1)},$$

so a.a.s.

$$|E_n^{(k)}|^{d-\varepsilon} \le |A_n^{(k)}| \le |E_n^{(k)}|^{d+\varepsilon}. \quad \blacksquare$$

Although the densability is preserved, it is not the case for being permutation invariant. Given a permutation invariant random subset $A_n$ of $E_n$, the random subset $A_n^{(k)}$ is not permutation invariant in $E_n^{(k)}$ for $k \ge 2$. See the following example.

**Example 3.2.** Let $(A_n)$ be a sequence of Bernoulli random subsets of $(E_n)$ with density $0 < d < 1$. Recall that subsets of the same cardinality have the same probability to be included in a permutation invariant random subset. Let $x_1, \dots, x_4$ be distinct elements in $E_n$.

$$\mathbf{Pr}(\{(x_1, x_2), (x_3, x_4)\} \subset A_n^{(2)}) = \mathbf{Pr}(\{x_1, x_2, x_3, x_4\} \subset A_n) = n^{4(d-1)},$$

while

$$\mathbf{Pr}(\{(x_1, x_2), (x_2, x_3)\} \subset A_n^{(2)}) = \mathbf{Pr}(\{x_1, x_2, x_3\} \subset A_n) = n^{3(d-1)}.$$
As a result the classical intersection formula (Theorem 2.9) can not be applied in this context. Actually, for $k \ge 2$ the intersection formula does not work for some choices of $X$. We give here a counter example.

**Example 3.3.** Let $\mathcal{A}$ be a sequence of random subsets in $\mathcal{D}(\mathcal{E})$ with density $3/4$. Let $X = (X_n)$ be a sequence of subsets defined by

$$X_n = \{x_n\} \times (E_n \setminus \{x_n\}) \subset E_n^{(2)}$$

with some $x_n \in E_n$. By its construction $\text{dens}_{E^{(2)}}(X) = 1/2$, so we expected that $\text{dens}(\mathcal{A}^{(2)} \cap X) = 3/4 + 1/2 - 1 = 1/4$. However, we have

$$\text{dens}(\mathcal{A}^{(2)} \cap X) = 0$$

because a.a.s. $A_n \cap \{x_n\} = \emptyset$.

For the intersection formula between $\mathcal{A}^{(k)}$ and $X$, we need an additional condition on $X$. More precisely, $X$ can not have too much “self-intersection”. We will discuss this condition in Section 3.1.

Following the path for proving the intersection formula (Theorem 2.9), we shall study the case that $\mathcal{A}$ is a sequence of Bernoulli random subsets with density $d$ (Section 3.2). We then adapt the proof for the uniform density model by estimating the probabilities $\text{Pr}(\{x_1, \dots, x_r\} \subset A_n)$ (Section 3.3).

For the general case (Section 3.4), according to Proposition 2.4, we can decompose a permutation invariant random subset into uniform random subsets. We then need to bound $|A_n^{(k)} \cap X_n|$ for sequences of uniform random subsets, uniformly in a small neighborhood of densities $d' \in [d - \varepsilon, d + \varepsilon]$.

**3.1. Statement of the theorem**

**Definition 3.4 (Self-intersection partition).** Let $X = (X_n)$ be a sequence of fixed subsets of $\mathcal{E}^{(k)}$ with density $\alpha$. For $0 \le i \le k$, the $i$th self-intersection of $X_n$ is

$$Y_{i,n} := \{(x, y) \in X_n^2 \mid |x \cap y| = i\},$$

where $|x \cap y|$ is the number of common elements in $x = (x_1, \dots, x_k)$ and $y = (y_1, \dots, y_k)$.

In particular, $Y_{0,n}$ is the set of pairs $(x, y)$ in $X_n^2$ having no intersection; $Y_{k,n}$ is the set of pairs $(x, x)$ in $X_n^2$. Note that $(Y_{i,n})_{0 \le i \le k}$ is a partition of $X_n^2$, called the self-intersection partition of $X_n$. Namely,

$$X_n^2 = \bigsqcup_{i=0}^{k} Y_{i,n}.$$
As a result the classical intersection formula (Theorem 2.9) can not be applied in this context. Actually, for $k \ge 2$ the intersection formula *does not work* for some choices of $X$. We give here a counter example.

**Example 3.3.** Let $\mathcal{A}$ be a sequence of random subsets in $\mathcal{D}(\mathcal{E})$ with density 3/4. Let $X = (X_n)$ be a sequence of subsets defined by

$$X_n = \{x_n\} \times (E_n \setminus \{x_n\}) \subset E_n^{(2)}$$

with some $x_n \in E_n$. By its construction $\text{dens}_{E^{(2)}}(X) = 1/2$, so we expected that $\text{dens}(\mathcal{A}^{(2)} \cap X) = 3/4 + 1/2 - 1 = 1/4$. However, we have

$$\text{dens}(\mathcal{A}^{(2)} \cap X) = 0$$

because a.a.s. $A_n \cap \{x_n\} = \emptyset$.

For the intersection formula between $\mathcal{A}^{(k)}$ and $X$, we need an additional condition on $X$. More precisely, $X$ can not have too much “self-intersection”. We will discuss this condition in Section 3.1.

Following the path for proving the intersection formula (Theorem 2.9), we shall study the case that $\mathcal{A}$ is a sequence of Bernoulli random subsets with density $d$ (Section 3.2). We then adapt the proof for the uniform density model by estimating the probabilities $\text{Pr}(\{x_1, \dots, x_r\} \subset A_n)$ (Section 3.3).

For the general case (Section 3.4), according to Proposition 2.4, we can decompose a permutation invariant random subset into uniform random subsets. We then need to bound $|A_n^{(k)} \cap X_n|$ for sequences of uniform random subsets, uniformly in a small neighborhood of densities $d' \in [d - \varepsilon, d + \varepsilon]$.

**3.1. Statement of the theorem**

**Definition 3.4 (Self-intersection partition).** Let $X = (X_n)$ be a sequence of fixed subsets of $\mathcal{E}^{(k)}$ with density $\alpha$. For $0 \le i \le k$, the $i$th self-intersection of $X_n$ is

$$Y_{i,n} := \{(x, y) \in X_n^2 \mid |x \cap y| = i\},$$

where $|x \cap y|$ is the number of common elements in $x = (x_1, \dots, x_k)$ and $y = (y_1, \dots, y_k)$.

In particular, $Y_{0,n}$ is the set of pairs $(x, y)$ in $X_n^2$ having no intersection; $Y_{k,n}$ is the set of pairs $(x, x)$ in $X_n^2$. Note that $(Y_{i,n})_{0 \le i \le k}$ is a partition of $X_n^2$, called the *self-intersection partition* of $X_n$. Namely,

$$X_n^2 = \bigsqcup_{i=0}^{k} Y_{i,n}.$$
The sequence $\mathbf{Y}_i = (Y_{i,n})_{n \in \mathbb{N}}$ is called the $i$ th self intersection of $\mathbf{X}$. The family of sequences $(\mathbf{Y}_i)_{0 \le i \le k}$ is called the self-intersection partition of $\mathbf{X}$. Namely,

$$ \mathbf{X}^2 = \bigsqcup_{i=0}^{k} \mathbf{Y}_i. $$

Remark that the sequences $\mathbf{X}^2$ and $\mathbf{Y}_i$ are sequences of fixed subsets of $(\mathbf{E}^{(k)})^2 = ((E_n^{(k)})^2)_{n \in \mathbb{N}}$. Note that $\text{dens}_{(\mathbf{E}^{(k)})_2}(\mathbf{X}^2) = \text{dens}_{\mathbf{E}^{(k)}}(\mathbf{X}) = \alpha$. To give a condition on $\mathbf{Y}_i$, we need the notion of *upper density*, defined by an upper limit:

**Definition 3.5.** Let $\mathbf{Y} = (Y_n)$ be a sequence of subsets of $\mathbf{E} = (E_n)$. The upper density of $\mathbf{Y}$ in $\mathbf{E}$ is

$$ \overline{\text{dens}}_{\mathbf{E}} \mathbf{Y} := \varlimsup_{n \to \infty} \log_{|E_n|} (|Y_n|). $$

We introduce here, for a sequence of densable fixed subsets $\mathbf{X}$ of $\mathbf{E}^{(k)}$ with density $\alpha$, the small self-intersection condition.

**Definition 3.6.** Let $\mathbf{X}$ be a sequence of subsets of $\mathbf{E}^{(k)}$ with density $\alpha$ and let $(\mathbf{Y}_i)_{0 \le i \le k}$ be its self-intersection partition. Let $d > 1 - \alpha$. We say that $\mathbf{X}$ satisfies the $d$-small self-intersection condition if, for every $1 \le i \le k - 1$,

$$ \overline{\text{dens}}_{(\mathbf{E}^{(k)})_2}(\mathbf{Y}_i) < \alpha - (1 - d) \times \frac{i}{2k}. $$

Remark that the right-hand side of the inequality is between 0 and $\alpha$ because $\alpha > 1 - d > 0$. Note that $|Y_{k,n}| = |\{(x, y) \in X_n^2 | x = y\}| = |X_n|$, so

$$ \text{dens}_{(\mathbf{E}^{(k)})_2} \mathbf{Y}_k = \frac{\alpha}{2} < \alpha - (1 - d) \frac{k}{2k}, $$

which satisfies automatically the inequality. On the other hand, as the upper densities of $\mathbf{Y}_i$ for $1 \le i \le k$ are all smaller than $\alpha$ and $|Y_{0,n}| = |X_n^2| - \sum_{i=1}^k |Y_{i,n}|$, by Proposition 2.8, the sequence $\mathbf{Y}_0$ is densable and

$$ \text{dens} \mathbf{Y}_0 = \text{dens} \mathbf{X}^2 = \alpha. $$

The purpose of this section is to demonstrate the following theorem.

**Theorem 3.7 (Multi-dimensional intersection formula).** Let $\mathbf{A}$ be a densable sequence of permutation invariant random subsets of $\mathbf{E}$ with density $0 < d < 1$. Let $\mathbf{X} = (X_n)$ be a sequence of (fixed) subsets of $\mathbf{E}^{(k)}$ with density $\alpha$.

(i) If $d + \alpha < 1$, then $\mathbf{A}^{(k)} \cap \mathbf{X}$ is densable and

$$ \text{dens}(\mathbf{A}^{(k)} \cap \mathbf{X}) = -\infty. $$
The sequence $\mathbf{Y}_i = (Y_{i,n})_{n \in \mathbb{N}}$ is called the $i$ th self intersection of $\mathbf{X}$. The family of sequences $(\mathbf{Y}_i)_{0 \le i \le k}$ is called the self-intersection partition of $\mathbf{X}$. Namely,

$$ \mathbf{X}^2 = \bigsqcup_{i=0}^{k} \mathbf{Y}_i. $$

Remark that the sequences $\mathbf{X}^2$ and $\mathbf{Y}_i$ are sequences of fixed subsets of $(\mathbf{E}^{(k)})^2 = ((E_n^{(k)})^2)_{n \in \mathbb{N}}$. Note that $\text{dens}_{(\mathbf{E}^{(k)})_2}(\mathbf{X}^2) = \text{dens}_{\mathbf{E}^{(k)}}(\mathbf{X}) = \alpha$. To give a condition on $\mathbf{Y}_i$, we need the notion of *upper density*, defined by an upper limit:

**Definition 3.5.** Let $\mathbf{Y} = (Y_n)$ be a sequence of subsets of $\mathbf{E} = (E_n)$. The upper density of $\mathbf{Y}$ in $\mathbf{E}$ is

$$ \overline{\text{dens}}_{\mathbf{E}} \mathbf{Y} := \varlimsup_{n \to \infty} \log_{|E_n|} (|Y_n|). $$

We introduce here, for a sequence of densable fixed subsets $\mathbf{X}$ of $\mathbf{E}^{(k)}$ with density $\alpha$, the small self-intersection condition.

**Definition 3.6.** Let $\mathbf{X}$ be a sequence of subsets of $\mathbf{E}^{(k)}$ with density $\alpha$ and let $(\mathbf{Y}_i)_{0 \le i \le k}$ be its self-intersection partition. Let $d > 1 - \alpha$. We say that $\mathbf{X}$ satisfies the $d$-small self-intersection condition if, for every $1 \le i \le k - 1$,

$$ \overline{\text{dens}}_{(\mathbf{E}^{(k)})_2}(\mathbf{Y}_i) < \alpha - (1 - d) \times \frac{i}{2k}. $$

Remark that the right-hand side of the inequality is between 0 and $\alpha$ because $\alpha > 1 - d > 0$. Note that $|Y_{k,n}| = |\{(x, y) \in X_n^2 | x = y\}| = |X_n|$, so

$$ \text{dens}_{(\mathbf{E}^{(k)})_2} \mathbf{Y}_k = \frac{\alpha}{2} < \alpha - (1 - d) \frac{k}{2k}, $$

which satisfies automatically the inequality. On the other hand, as the upper densities of $\mathbf{Y}_i$ for $1 \le i \le k$ are all smaller than $\alpha$ and $|Y_{0,n}| = |X_n^2| - \sum_{i=1}^k |Y_{i,n}|$, by Proposition 2.8, the sequence $\mathbf{Y}_0$ is densable and

$$ \text{dens} \mathbf{Y}_0 = \text{dens} \mathbf{X}^2 = \alpha. $$

The purpose of this section is to demonstrate the following theorem.

**Theorem 3.7 (Multi-dimensional intersection formula).** Let $\mathbf{A}$ be a densable sequence of permutation invariant random subsets of $\mathbf{E}$ with density $0 < d < 1$. Let $\mathbf{X} = (X_n)$ be a sequence of (fixed) subsets of $\mathbf{E}^{(k)}$ with density $\alpha$.

(i) If $d + \alpha < 1$, then $\mathbf{A}^{(k)} \cap \mathbf{X}$ is densable and

$$ \text{dens}(\mathbf{A}^{(k)} \cap \mathbf{X}) = -\infty. $$
(ii) If $d + \alpha > 1$ and $X$ satisfies the $d$-small self intersection condition (Definition 3.6), then $A^{(k)} \cap X$ is densable and

$$ \mathrm{dens}(A^{(k)} \cap X) = \alpha + d - 1. $$

Note that when $k = 1$, we have the intersection formula between a random subset and a fixed subset. In this case, the self intersection partition of $X$ contains only $Y_0$ and $Y_1$, and we do not need to check the self intersection condition.

**Corollary 3.8 (Random-fixed intersection formula).** Let $A$ be a densable sequence of permutation invariant random subsets of $E$ with density $d$. Let $X$ be a sequence of (fixed) subsets of $E$ with density $\alpha$. If $d + \alpha \neq 1$, then the sequence of random subsets $A \cap X$ is densable and

$$ \mathrm{dens}(A \cap X) = \begin{cases} d + \alpha - 1 & \text{if } d + \alpha > 1, \\ -\infty & \text{if } d + \alpha < 1. \end{cases} $$

We shall first represent the expected value and the variance of the random variable $|A_n^{(k)} \cap X_n|$ by probabilities of the type $\mathbf{Pr}(\{x_1, \dots, x_r\} \subset A_n)$. The following result generalizes Lemma 2.3.

**Lemma 3.9.** Let $E$, $A$ and $X$ be given as in Theorem 3.7 and let $(Y_i)_{0 \le i \le k}$ be the self-intersection partition of $X$. Let $x_1, \dots, x_{2k}$ be distinct $2k$ elements of $E_n$.

(i) $\mathbb{E}(|A_n^{(k)} \cap X_n|) = |X_n|\mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n)$.

(ii) $\mathrm{Var}(|A_n^{(k)} \cap X_n|) = |X_n|^2 (\mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n))^2 + \sum_{i=1}^k |Y_{i,n}| (\mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n))$.

*Proof.* We consider each item.

(i) As $A_n$ is permutation invariant, the probability $\mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n)$ does not depend on the choice of $\{x_1, \dots, x_k\}$. So,

$$ \begin{aligned} \mathbb{E}(|A_n^{(k)} \cap X_n|) &= \mathbb{E}\left(\sum_{x \in X_n} \mathbb{1}_{x \in A_n^{(k)}}\right) = \sum_{x \in X_n} \mathbf{Pr}(x \in A_n^{(k)}) \\ &= |X_n| \mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n). \end{aligned} $$

(ii) By the same reason $\mathbf{Pr}(\{x_1, \dots, x_r\} \subset A_n)$ does not depend on the choice of $\{x_1, \dots, x_r\}$ for all $r \in \mathbb{N}$. Note that

$$ \mathrm{Var}(|A_n^{(k)} \cap X_n|) = \mathbb{E}(|A_n^{(k)} \cap X_n|^2) - \mathbb{E}(|A_n^{(k)} \cap X_n|^2). $$
(ii) If $d + \alpha > 1$ and $X$ satisfies the $d$-small self intersection condition (Definition 3.6), then $A^{(k)} \cap X$ is densable and

$$ \mathrm{dens}(A^{(k)} \cap X) = \alpha + d - 1. $$

Note that when $k = 1$, we have the intersection formula between a random subset and a fixed subset. In this case, the self intersection partition of $X$ contains only $Y_0$ and $Y_1$, and we do not need to check the self intersection condition.

**Corollary 3.8 (Random-fixed intersection formula).** Let $A$ be a densable sequence of permutation invariant random subsets of $E$ with density $d$. Let $X$ be a sequence of (fixed) subsets of $E$ with density $\alpha$. If $d + \alpha \neq 1$, then the sequence of random subsets $A \cap X$ is densable and

$$ \mathrm{dens}(A \cap X) = \begin{cases} d + \alpha - 1 & \text{if } d + \alpha > 1, \\ -\infty & \text{if } d + \alpha < 1. \end{cases} $$

We shall first represent the expected value and the variance of the random variable $|A_n^{(k)} \cap X_n|$ by probabilities of the type $\mathrm{Pr}(\{x_1, \dots, x_r\} \subset A_n)$. The following result generalizes Lemma 2.3.

**Lemma 3.9.** Let $E$, $A$ and $X$ be given as in Theorem 3.7 and let $(Y_i)_{0 \le i \le k}$ be the self-intersection partition of $X$. Let $x_1, \dots, x_{2k}$ be distinct $2k$ elements of $E_n$.

(i) $\mathbb{E}(|A_n^{(k)} \cap X_n|) = |X_n|\mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)$.

(ii) $\mathrm{Var}(|A_n^{(k)} \cap X_n|) = |X_n|^2 (\mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2) + \sum_{i=1}^k |Y_{i,n}| (\mathrm{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n))$.

*Proof.* We consider each item.

(i) As $A_n$ is permutation invariant, the probability $\mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)$ does not depend on the choice of $\{x_1, \dots, x_k\}$. So,

$$ \begin{aligned} \mathbb{E}(|A_n^{(k)} \cap X_n|) &= \mathbb{E}\left(\sum_{x \in X_n} \mathbb{1}_{x \in A_n^{(k)}}\right) = \sum_{x \in X_n} \mathrm{Pr}(x \in A_n^{(k)}) \\ &= |X_n| \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n). \end{aligned} $$

(ii) By the same reason $\mathrm{Pr}(\{x_1, \dots, x_r\} \subset A_n)$ does not depend on the choice of $\{x_1, \dots, x_r\}$ for all $r \in \mathbb{N}$. Note that

$$ \mathrm{Var}(|A_n^{(k)} \cap X_n|) = \mathbb{E}(|A_n^{(k)} \cap X_n|^2) - \mathbb{E}(|A_n^{(k)} \cap X_n|^2). $$
If $(x, y) \in Y_{i,n}$, then there are $2k - i$ different elements of $E_n$ in $x$ and $y$, so

$$ \mathbf{Pr}(x, y \in A_n^{(k)}) = \mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n). $$

Hence,

$$ \begin{aligned} \mathbb{E}(|A_n^{(k)} \cap X_n|^2) &= \mathbb{E}\left(\left(\sum_{x \in X_n} \mathbb{1}_{x \in A_n^{(k)}}\right)^2\right) = \sum_{x, y \in X_n} \mathbf{Pr}(x, y \in A_n^{(k)}) \\ &= \sum_{i=0}^{k} \sum_{(x,y) \in Y_{i,n}} \mathbf{Pr}(x, y \in A_n^{(k)}) \\ &= \sum_{i=0}^{k} |Y_{i,n}| \mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n). \end{aligned} $$

Recall that $|Y_{0,n}| = |X_n^2| - \sum_{i=1}^k |Y_{i,n}|$. The above can be rewritten as

$$ \begin{aligned} \mathbb{E}(|A_n^{(k)} \cap X_n|^2) &= \left(|X_n^2| - \sum_{i=1}^k |Y_{i,n}|\right) \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) \\ &\quad + \sum_{i=1}^k |Y_{i,n}| \mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) \\ &= |X_n^2| \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) \\ &\quad + \sum_{i=1}^k \left(\mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n)\right). \end{aligned} $$

Combined with $\mathbb{E}(|A_n^{(k)} \cap X_n|^2) = |X_n|^2 \mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2$, we have

$$ \begin{aligned} \mathrm{Var}(|A_n^{(k)} \cap X_n|) = |X_n|^2 &\left(\mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2\right) \\ &+ \sum_{i=1}^k |Y_{i,n}| \left(\mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n)\right). \quad \blacksquare \end{aligned} $$

Remark that Lemma 2.3 is a special case of Lemma 3.9, by taking $k=1$ and $X_n = E_n$. Note that if $k=1$, then $X^2 = Y_0 \cup Y_1$ and there is no need to introduce condition (3.6).

## 3.2. The Bernoulli density model

Let $X$ be a fixed sequence of subsets of $E^{(k)}$ with density $\alpha$. In this subsection, we study the intersection $A^{(k)} \cap X$ in the case that $A$ is a sequence of Bernoulli random
If $(x, y) \in Y_{i,n}$, then there are $2k - i$ different elements of $E_n$ in $x$ and $y$, so

$$ \mathrm{Pr}(x, y \in A_n^{(k)}) = \mathrm{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n). $$

Hence,

$$ \begin{aligned} \mathbb{E}(|A_n^{(k)} \cap X_n|^2) &= \mathbb{E}\left(\left(\sum_{x \in X_n} \mathbb{1}_{x \in A_n^{(k)}}\right)^2\right) = \sum_{x, y \in X_n} \mathrm{Pr}(x, y \in A_n^{(k)}) \\ &= \sum_{i=0}^{k} \sum_{(x,y) \in Y_{i,n}} \mathrm{Pr}(x, y \in A_n^{(k)}) \\ &= \sum_{i=0}^{k} |Y_{i,n}| \mathrm{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n). \end{aligned} $$

Recall that $|Y_{0,n}| = |X_n^2| - \sum_{i=1}^k |Y_{i,n}|$. The above can be rewritten as

$$ \begin{aligned} \mathbb{E}(|A_n^{(k)} \cap X_n|^2) &= \left(|X_n^2| - \sum_{i=1}^k |Y_{i,n}|\right) \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) \\ &\quad + \sum_{i=1}^k |Y_{i,n}| \mathrm{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) \\ &= |X_n^2| \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) \\ &\quad + \sum_{i=1}^k \left(\mathrm{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n)\right). \end{aligned} $$

Combined with $\mathbb{E}(|A_n^{(k)} \cap X_n|^2) = |X_n|^2 \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2$, we have

$$ \begin{aligned} \mathrm{Var}(|A_n^{(k)} \cap X_n|) = &|X_n|^2 \left( \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n) \right)^2 \\ &+ \sum_{i=1}^k |Y_{i,n}| \left( \mathrm{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) \right). \quad \blacksquare \end{aligned} $$

Remark that Lemma 2.3 is a special case of Lemma 3.9, by taking $k=1$ and $X_n = E_n$. Note that if $k=1$, then $X^2 = Y_0 \cup Y_1$ and there is no need to introduce condition (3.6).

## 3.2. The Bernoulli density model

Let $X$ be a fixed sequence of subsets of $E^{(k)}$ with density $\alpha$. In this subsection, we study the intersection $A^{(k)} \cap X$ in the case that $A$ is a sequence of Bernoulli random
subsets of $\mathcal{E}$ with density $0 < d < 1$. Note that for any integer $r \in \mathbb{N}$ and any distinct elements $x_1, \dots, x_r$ in $E_n$, we have

$$
\begin{aligned}
\mathrm{Pr}(\{x_1, \dots, x_r\} \subset A_n) &= \mathrm{Pr}(\{x_1 \in A_n\}, \dots, \{x_r \in A_n\}) \\
&= \prod_{i=1}^{r} \mathrm{Pr}(x_i \in A_n) = n^{r(d-1)}
\end{aligned}
$$

by independence of the events $\mathrm{Pr}(x_i \in A_n)$. Because of this equality, the proof of
Theorem 3.7 for the Bernoulli density model is much simpler.

*Proof of Theorem 3.7 for Bernoulli density model.* We consider each item.

(i) Suppose that $\alpha + d < 1$. To prove that $\mathrm{dens}(A^{(k)} \cap X) = -\infty$, it is enough to prove that

$$
\mathrm{Pr}(A_n^{(k)} \cap X_n \neq \emptyset) \xrightarrow{n \to \infty} 0.
$$

By Markov's inequality and Lemma 3.9,

$$
\begin{align*}
\mathrm{Pr}(A_n^{(k)} \cap X_n \neq \emptyset) &= \mathrm{Pr}(|A_n^{(k)} \cap X_n| \geq 1) \\
&\leq \mathrm{E}(|A_n^{(k)} \cap X_n|) = |X_n| \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n) \\
&\leq n^{k\alpha+o(1)} n^{k(d-1)} \\
&\leq n^{k(\alpha+d-1)+o(1)} \xrightarrow{n \to \infty} 0
\end{align*}
$$

as $\alpha + d - 1 < 0$.

(ii) Suppose that $\alpha + d > 1$. To simplify the notation, denote $B_n = A_n^{(k)} \cap X_n$ and $\mathbf{B} = \mathbf{X} \cap \mathbf{A}^{(k)}$.

We shall prove that $\mathrm{dens} \, \mathbf{B} = \alpha + d - 1$. Let $\varepsilon > 0$ be an arbitrary small real number. We need prove that a.a.s.

$$
n^{k(\alpha+d-1-\varepsilon)} \leq |B_n| \leq n^{k(\alpha+d-1+\varepsilon)}.
$$

By Lemma 3.9,

$$
\begin{align*}
\mathbb{E}(|B_n|) &= |X_n| \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n) = |X_n| n^{k(d-1)} \\
&= n^{k(\alpha+d-1)+o(1)}.
\end{align*}
$$

For $n$ large enough,

$$
n^{k(\alpha+d-1-\epsilon)} < \frac{1}{2} n^{k(\alpha+d-1)+o(1)} < \frac{3}{2} n^{k(\alpha+d-1)+o(1)} < n^{k(\alpha+d-1+\epsilon)}.
$$

So it is enough to prove that a.a.s.

$$
\frac{1}{2} \mathbb{E}(|B_n|) < |B_n| < \frac{3}{2} \mathbb{E}(|B_n|),
$$
subsets of $\mathcal{E}$ with density $0 < d < 1$. Note that for any integer $r \in \mathbb{N}$ and any distinct elements $x_1, \dots, x_r$ in $E_n$, we have

$$
\begin{aligned}
\mathrm{Pr}(\{x_1, \dots, x_r\} \subset A_n) &= \mathrm{Pr}(\{x_1 \in A_n\}, \dots, \{x_r \in A_n\}) \\
&= \prod_{i=1}^{r} \mathrm{Pr}(x_i \in A_n) = n^{r(d-1)}
\end{aligned}
$$

by independence of the events $\textbf{Pr}(x_i \in A_n)$. Because of this equality, the proof of
Theorem 3.7 for the Bernoulli density model is much simpler.

*Proof of Theorem 3.7 for Bernoulli density model.* We consider each item.

(i) Suppose that $\alpha + d < 1$. To prove that $\text{dens}(A^{(k)} \cap X) = -\infty$, it is enough to prove that

$$
\mathbf{Pr}(A_n^{(k)} \cap X_n \neq \emptyset) \xrightarrow{n \to \infty} 0.
$$

By Markov's inequality and Lemma 3.9,

$$
\begin{align*}
\mathrm{Pr}(A_n^{(k)} \cap X_n \neq \emptyset) &= \mathrm{Pr}(|A_n^{(k)} \cap X_n| \geq 1) \\
&\leq \mathbb{E}(|A_n^{(k)} \cap X_n|) = |X_n| \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n) \\
&\leq n^{k\alpha+o(1)} n^{k(d-1)} \\
&\leq n^{k(\alpha+d-1)+o(1)} \xrightarrow{n \to \infty} 0
\end{align*}
$$

as $\alpha + d - 1 < 0$.

(ii) Suppose that $\alpha + d > 1$. To simplify the notation, denote $B_n = A_n^{(k)} \cap X_n$
and $\mathbf{B} = \mathbf{X} \cap \mathbf{A}^{(k)}$.

We shall prove that $\text{dens } \mathbf{B} = \alpha + d - 1$. Let $\varepsilon > 0$ be an arbitrary small real number. We need prove that a.a.s.

$$
n^{k(\alpha+d-1-\varepsilon)} \le |B_n| \le n^{k(\alpha+d-1+\varepsilon)}.
$$

By Lemma 3.9,

$$
\begin{align*}
\mathbb{E}(|B_n|) &= |X_n| \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n) = |X_n| n^{k(d-1)} \\
&= n^{k(\alpha+d-1)+o(1)}.
\end{align*}
$$

For $n$ large enough,

$$
n^{k(\alpha+d-1-\epsilon)} < \frac{1}{2} n^{k(\alpha+d-1)+o(1)} < \frac{3}{2} n^{k(\alpha+d-1)+o(1)} < n^{k(\alpha+d-1+\epsilon)}.
$$

So it is enough to prove that a.a.s.

$$
\frac{1}{2} \mathbb{E}(|B_n|) < |B_n| < \frac{3}{2} \mathbb{E}(|B_n|),
$$
which means that a.a.s.

$$|B_n| - \mathbb{E}(|B_n|) < \frac{1}{2} \mathbb{E}(|B_n|).$$

By Chebyshev's inequality,

$$\mathbf{Pr}(|B_n| - \mathbb{E}(|B_n|) \geq \frac{1}{2}\mathbb{E}(|B_n|)) \leq \frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)}.$$

We shall prove that this quantity goes to zero when $n$ goes to infinity. By Lemma 3.9,

$$\begin{align*}
\mathrm{Var}(|B_n|) &= |X_n|^2 (\mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2) \\
&\quad + \sum_{i=1}^k |Y_{i,n}| (\mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n)) \\
&= \sum_{i=1}^k |Y_{i,n}| (n^{(2k-i)(d-1)} - n^{2k(d-1)}) \\
&\leq \sum_{i=1}^k |Y_{i,n}| n^{(2k-i)(d-1)}.
\end{align*}$$

Note that $n^{(2k-i)(d-1)} > n^{2k(d-1)}$ because $d < 1$. By the $d$-small self-intersection condition (3.6), there exists $\varepsilon > 0$ such that for all $1 \leq i \leq k$,

$$|Y_{i,n}| \leq n^{2k(\alpha+(d-1)i/2k)-\varepsilon}$$

for $n$ large enough. Hence, for $n$ large enough

$$\mathrm{Var}(|B_n|) \leq k n^{2k(\alpha+d-1)-\varepsilon}.$$

Recall that $\mathbb{E}(|B_n|^2) = n^{2k(\alpha+d-1)+o(1)}$, so

$$\frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)} \xrightarrow{n \to \infty} 0.$$

### 3.3. The uniform density model

Note that when $A$ is a sequence of Bernoulli random subsets with density $d$, we have

$$\mathbf{Pr}(\{x_1, \dots, x_r\} \subset A_n) = n^{r(d-1)},$$

and consequently,

$$\mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2 - \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) = 0.$$

In order to proceed the same proof, we shall estimate these two quantities for the uniform density model.
which means that a.a.s.

$$|B_n| - \mathbb{E}(|B_n|) < \frac{1}{2} \mathbb{E}(|B_n|).$$

By Chebyshev's inequality,

$$\mathbf{Pr}(|B_n| - \mathbb{E}(|B_n|) \geq \frac{1}{2}\mathbb{E}(|B_n|)) \leq \frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)}.$$

We shall prove that this quantity goes to zero when $n$ goes to infinity. By Lemma 3.9,

$$\begin{align*}
\mathrm{Var}(|B_n|) &= |X_n|^2 (\mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2) \\
&\quad + \sum_{i=1}^k |Y_{i,n}| (\mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n)) \\
&= \sum_{i=1}^k |Y_{i,n}| (n^{(2k-i)(d-1)} - n^{2k(d-1)}) \\
&\leq \sum_{i=1}^k |Y_{i,n}| n^{(2k-i)(d-1)}.
\end{align*}$$

Note that $n^{(2k-i)(d-1)} > n^{2k(d-1)}$ because $d < 1$. By the $d$-small self-intersection condition (3.6), there exists $\varepsilon > 0$ such that for all $1 \leq i \leq k$,

$$|Y_{i,n}| \leq n^{2k(\alpha+(d-1)i/2k)-\varepsilon}$$

for $n$ large enough. Hence, for $n$ large enough

$$\mathrm{Var}(|B_n|) \leq k n^{2k(\alpha+d-1)-\varepsilon}.$$

Recall that $\mathbb{E}(|B_n|^2) = n^{2k(\alpha+d-1)+o(1)}$, so

$$\frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)} \xrightarrow{n \to \infty} 0.$$

### 3.3. The uniform density model

Note that when $A$ is a sequence of Bernoulli random subsets with density $d$, we have

$$\mathbf{Pr}(\{x_1, \dots, x_r\} \subset A_n) = n^{r(d-1)},$$

and consequently,

$$\mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2 - \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) = 0.$$

In order to proceed the same proof, we shall estimate these two quantities for the uniform density model.
**Lemma 3.10.** Let A be a sequence of uniform random subsets of E with density d. Let $0 < \varepsilon < d$ be a small real number and let $k \ge 1$ be an integer. If $n \ge (1 + 2k)^{1/\varepsilon}$, then

(i) for all integers $1 \le r \le 2k$,

$$n^{r(d-1-\varepsilon)} \le \Pr(\{x_1, \dots, x_r\} \subset A_n) \le n^{r(d-1+\varepsilon)};$$

(ii) $0 \le \Pr(\{x_1, \dots, x_k\} \subset A_n)^2 - \Pr(\{x_1, \dots, x_{2k}\} \subset A_n) \le n^{2k(d-1+\varepsilon)-d}$.

*Proof.* Recall that $|E_n| = n$ and that $A_n$ is uniform on all subsets of $E_n$ of cardinality $\lfloor n^d \rfloor$.

(i) Note that $\lfloor n^d \rfloor \ge n^\varepsilon - 1 \ge 2k \ge r$. Among all subsets of $E_n$ of cardinality $\lfloor n^d \rfloor$, there are $\binom{n-r}{\lfloor n^d \rfloor - r}$ subsets that include $\{x_1, \dots, x_r\}$. So,

$$\Pr(\{x_1, \dots, x_r\} \subset A_n) = \frac{\binom{n-r}{\lfloor n^d \rfloor - r}}{\binom{n}{\lfloor n^d \rfloor}} = \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - r + 1)}{n \dots (n-r-1)}.$$

We estimate that

$$\left(\frac{n^d - r}{n}\right)^r \le \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - r + 1)}{n \dots (n-r-1)} \le \left(\frac{n^d}{n-r}\right)^r.$$

The condition $n \ge (1 + 2k)^{1/\varepsilon} \ge (1 + r)^{1/\varepsilon}$ implies

$$\begin{cases} n \ge n^{1-\varepsilon}(1+r), \\ n^d \ge n^{d-\varepsilon}(1+r), \end{cases}$$

so

$$\begin{cases} n^{1-\varepsilon} \le n-r, \\ n^{d-\varepsilon} \le n^d-r. \end{cases}$$

Hence,

$$(n^{d-1-\varepsilon})^r \le \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - r + 1)}{n \dots (n-r-1)} \le (n^{d-1+\varepsilon})^r.$$

(ii) By the same argument,

$$\begin{align*} \Pr(\{x_1, \dots, x_k\} \subset A_n)^2 - \Pr(\{x_1, \dots, x_{2k}\} \subset A_n) & \\ &= \left( \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - k + 1)}{n \dots (n-k-1)} \right)^2 - \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - 2k + 1)}{n \dots (n-2k-1)} \\ &= \left( \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - k + 1)}{n \dots (n-k-1)} \right) \\ & \quad \cdot \left( \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - k + 1)}{n \dots (n-k-1)} - \frac{(\lfloor n^d \rfloor - k) \dots (\lfloor n^d \rfloor - 2k + 1)}{(n-k) \dots (n-2k-1)} \right). \end{align*}$$
**Lemma 3.10.** Let $\mathcal{A}$ be a sequence of uniform random subsets of $\mathcal{E}$ with density $d$. Let $0 < \varepsilon < d$ be a small real number and let $k \ge 1$ be an integer. If $n \ge (1+2k)^{1/\varepsilon}$, then

(i) for all integers $1 \le r \le 2k$,

$$n^{r(d-1-\varepsilon)} \le \Pr(\{x_1, \dots, x_r\} \subset A_n) \le n^{r(d-1+\varepsilon)};$$

(ii) $0 \le \Pr(\{x_1, \dots, x_k\} \subset A_n)^2 - \Pr(\{x_1, \dots, x_{2k}\} \subset A_n) \le n^{2k(d-1+\varepsilon)-d}$.

*Proof.* Recall that $|E_n| = n$ and that $A_n$ is uniform on all subsets of $E_n$ of cardinality $\lfloor n^d \rfloor$.

(i) Note that $\lfloor n^d \rfloor \ge n^\varepsilon - 1 \ge 2k \ge r$. Among all subsets of $E_n$ of cardinality $\lfloor n^d \rfloor$, there are $\binom{n-r}{\lfloor n^d \rfloor-r}$ subsets that include $\{x_1, \dots, x_r\}$. So,

$$\Pr(\{x_1, \dots, x_r\} \subset A_n) = \frac{\binom{n-r}{\lfloor n^d \rfloor-r}}{\binom{n}{\lfloor n^d \rfloor}} = \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - r + 1)}{n \dots (n-r-1)}.$$

We estimate that

$$\left(\frac{n^d - r}{n}\right)^r \le \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - r + 1)}{n \dots (n-r-1)} \le \left(\frac{n^d}{n-r}\right)^r.$$

The condition $n \ge (1+2k)^{1/\varepsilon} \ge (1+r)^{1/\varepsilon}$ implies

$$\begin{cases} n \ge n^{1-\varepsilon}(1+r), \\ n^d \ge n^{d-\varepsilon}(1+r), \end{cases}$$

so

$$\begin{cases} n^{1-\varepsilon} \le n-r, \\ n^{d-\varepsilon} \le n^d-r. \end{cases}$$

Hence,

$$(n^{d-1-\varepsilon})^r \le \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - r + 1)}{n \dots (n-r-1)} \le (n^{d-1+\varepsilon})^r.$$

(ii) By the same argument,

$$\begin{align*} \Pr(\{x_1, \dots, x_k\} \subset A_n)^2 - \Pr(\{x_1, \dots, x_{2k}\} \subset A_n) & \\ &= \left( \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - k + 1)}{n \dots (n-k-1)} \right)^2 - \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - 2k + 1)}{n \dots (n-2k-1)} \\ &= \left( \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - k + 1)}{n \dots (n-k-1)} \right) \\ & \quad \cdot \left( \frac{\lfloor n^d \rfloor \dots (\lfloor n^d \rfloor - k + 1)}{n \dots (n-k-1)} - \frac{(\lfloor n^d \rfloor - k) \dots (\lfloor n^d \rfloor - 2k + 1)}{(n-k) \dots (n-2k-1)} \right). \end{align*}$$
This quantity is positive because $\frac{|n^d| - i}{n - i} \ge \frac{|n^d| - i - k}{n - i - k}$ for every $0 \le i \le k - 1$.
Now we estimate that

$$ 
\begin{aligned}
& \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2 - \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) \\
& \le \left(\frac{n^d}{n-k}\right)^k \left(\frac{n^{dk}}{(n-k)^k} - \frac{(n^d - 2k)^k}{(n-k)^k}\right) \\
& \le \frac{n^{dk}}{(n-k)^{2k}} \left(n^{dk} - \sum_{i=0}^k \binom{k}{i} n^{d(k-i)} (-2k)^i\right) \\
& \le \frac{n^{dk}}{(n-k)^{2k}} (1+2k)^k n^{d(k-1)} = \left(\frac{n^d \sqrt{1+2k}}{n-k}\right)^{2k} n^{-d}.
\end{aligned}
$$

As $n^\epsilon \ge 1+2k$, we have

$$ 
\begin{aligned}
n-k &\ge n^{1-\epsilon}(1+2k)-k \\
&\ge n^{1-\epsilon}(1+k) \\
&\ge n^{1-\epsilon}\sqrt{1+2k}.
\end{aligned}
$$

Hence,

$$ \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2 - \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) \le n^{2k(d-1+\epsilon)-d}. \quad \blacksquare $$

**Notation.** Let $X$ be a sequence of subsets of $E^{(k)}$ with density $\alpha$ and let $(Y_i)_{0\le i \le k}$ be its self-intersection partition. Denote the density difference

$$ \epsilon_0(d) = \min_{1 \le i \le k} \left\{ \alpha + (d-1) \frac{i}{2k} - \overline{\mathrm{dens}} Y_i \right\}. $$

Remark that $X$ has $d$-small self-intersection if and only if $\epsilon_0(d) > 0$. In addition, for every small real number $0 < \epsilon < \epsilon_0(d)/10$ there exists $n_\epsilon \in \mathbb{N}$ such that for all $n \ge n_\epsilon$ we have, simultaneously for all $1 \le i \le k$,

$$ |Y_{n,i}| \le n^{2k(\alpha+(d-1)i/2k-10\epsilon)} = n^{2k\alpha+(d-1)i-2k \times 10\epsilon}. $$

By densability of $X$, we can choose $n_\epsilon$ such that at the same time

$$ n^{k(\alpha-\epsilon)} \le |X_n| \le n^{k(\alpha+\epsilon)}. $$

Combined with Lemma 3.10, we can now estimate the expected value and the variance of $|A_n^{(k)} \cap X_n|$ for the uniform density model.

**Lemma 3.11.** Let $A$ be a sequence of uniform random subsets of $E$ with density $d$. Let $X$ be a sequence of subsets of $E^{(k)}$ with density $\alpha$. Let $0 < \epsilon < \min\{\epsilon_0(d)/10, d\}$ be a small real number. If $n \ge \max\{n_\epsilon, (1+2k)^{1/\epsilon}\}$, then
This quantity is positive because $\frac{|n^d| - i}{n - i} \ge \frac{|n^d| - i - k}{n - i - k}$ for every $0 \le i \le k - 1$.
Now we estimate that

$$ 
\begin{aligned}
& \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2 - \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) \\
& \le \left(\frac{n^d}{n-k}\right)^k \left(\frac{n^{dk}}{(n-k)^k} - \frac{(n^d-2k)^k}{(n-k)^k}\right) \\
& \le \frac{n^{dk}}{(n-k)^{2k}} \left(n^{dk} - \sum_{i=0}^k \binom{k}{i} n^{d(k-i)} (-2k)^i\right) \\
& \le \frac{n^{dk}}{(n-k)^{2k}} (1+2k)^k n^{d(k-1)} = \left(\frac{n^d \sqrt{1+2k}}{n-k}\right)^{2k} n^{-d}.
\end{aligned}
$$

As $n^\epsilon \ge 1+2k$, we have

$$ 
\begin{aligned}
n-k &\ge n^{1-\epsilon}(1+2k)-k \\
&\ge n^{1-\epsilon}(1+k) \\
&\ge n^{1-\epsilon}\sqrt{1+2k}.
\end{aligned}
$$

Hence,

$$ \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2 - \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) \le n^{2k(d-1+\epsilon)-d}. \quad \blacksquare $$

**Notation.** Let $X$ be a sequence of subsets of $E^{(k)}$ with density $\alpha$ and let $(Y_i)_{0\le i\le k}$ be its self-intersection partition. Denote the density difference

$$ \epsilon_0(d) = \min_{1 \le i \le k} \left\{ \alpha + (d-1) \frac{i}{2k} - \overline{\mathrm{dens}} Y_i \right\}. $$

Remark that $X$ has $d$-small self-intersection if and only if $\epsilon_0(d) > 0$. In addition, for every small real number $0 < \epsilon < \epsilon_0(d)/10$ there exists $n_\epsilon \in \mathbb{N}$ such that for all $n \ge n_\epsilon$ we have, simultaneously for all $1 \le i \le k$,

$$ |Y_{n,i}| \le n^{2k(\alpha+(d-1)i/2k-10\epsilon)} = n^{2k\alpha+(d-1)i-2k \times 10\epsilon}. $$

By densability of $X$, we can choose $n_\epsilon$ such that at the same time

$$ n^{k(\alpha-\epsilon)} \le |X_n| \le n^{k(\alpha+\epsilon)}. $$

Combined with Lemma 3.10, we can now estimate the expected value and the variance of $|A_n^{(k)} \cap X_n|$ for the uniform density model.

**Lemma 3.11.** Let $A$ be a sequence of uniform random subsets of $E$ with density $d$. Let $X$ be a sequence of subsets of $E^{(k)}$ with density $\alpha$. Let $0 < \epsilon < \min\{\epsilon_0(d)/10, d\}$ be a small real number. If $n \ge \max\{n_\epsilon, (1+2k)^{1/\epsilon}\}$, then
(i) $n^{k(\alpha+d-1-2\epsilon)} \le \mathbb{E}(|A_n^{(k)} \cap X_n|) \le n^{k(\alpha+d-1+2\epsilon)}$.

(ii) If in addition $\alpha + d - 1 > 2\epsilon > 0$ and $X$ has $d$-small self-intersection, then

$$ \mathrm{Var}(|A_n^{(k)} \cap X_n|) \le k n^{2k(\alpha+d-1-9\epsilon)}. $$

*Proof.* We consider each item.

(i) By Lemma 3.9,

$$ \mathbb{E}(|A_n^{(k)} \cap X_n|) = |X_n| \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n). $$

So by Lemma 3.10 and $n^{k(\alpha-\epsilon)} \le |X_n| \le n^{k(\alpha+\epsilon)}$, we have

$$ n^{k(\alpha-\epsilon)} n^{k(d-1-\epsilon)} \le \mathbb{E}(|A_n^{(k)} \cap X_n|) \le n^{k(\alpha+\epsilon)} n^{k(d-1+\epsilon)}. $$

(ii) By Lemma 3.10 (ii)

$$ \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2 \le 0. $$

Apply Lemma 3.9, eliminate negative parts:

$$ \begin{aligned} \mathrm{Var}(|A_n^{(k)} \cap X_n|) &= |X_n|^2 (\mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_k\} \subset A_n))^2 \\ &\quad + \sum_{i=1}^k |Y_{i,n}| (\mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathbf{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n)) \\ &\le \sum_{i=1}^k |Y_{i,n}| \mathbf{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n). \end{aligned} $$

By Lemma 3.10 (i) and $|Y_{i,n}| \le n^{2k\alpha+i(d-1)+2k \times 10\epsilon}$

$$ \begin{aligned} \mathrm{Var}(|A_n^{(k)} \cap X_n|) &\le \sum_{i=1}^k n^{2k\alpha+i(d-1)-2k \times 10\epsilon} n^{(2k-i)(d-1+\epsilon)} \\ &\le k n^{2k(\alpha+d-1-9\epsilon)}. \end{aligned} $$

*Proof of Theorem 3.7 for uniform density model.* We consider each item.

(i) Suppose that $\alpha + d < 1$. We shall prove that

$$ \mathbf{Pr}(A_n^{(k)} \cap X_n \ne \emptyset) \xrightarrow{n \to \infty} 0. $$

Let $\epsilon > 0$ such that

$$ \epsilon < \min \left\{ \frac{1-d-\alpha}{2}, \frac{\epsilon_0(d)}{10}, d \right\}. $$
(i) $n^{k(\alpha+d-1-2\epsilon)} \le \mathbb{E}(|A_n^{(k)} \cap X_n|) \le n^{k(\alpha+d-1+2\epsilon)}$.

(ii) If in addition $\alpha + d - 1 > 2\epsilon > 0$ and $X$ has $d$-small self-intersection, then

$$ \mathrm{Var}(|A_n^{(k)} \cap X_n|) \le k n^{2k(\alpha+d-1-9\epsilon)}. $$

*Proof.* We consider each item.

(i) By Lemma 3.9,

$$ \mathbb{E}(|A_n^{(k)} \cap X_n|) = |X_n| \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n). $$

So by Lemma 3.10 and $n^{k(\alpha-\epsilon)} \le |X_n| \le n^{k(\alpha+\epsilon)}$, we have

$$ n^{k(\alpha-\epsilon)} n^{k(d-1-\epsilon)} \le \mathbb{E}(|A_n^{(k)} \cap X_n|) \le n^{k(\alpha+\epsilon)} n^{k(d-1+\epsilon)}. $$

(ii) By Lemma 3.10 (ii)

$$ \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n)^2 \le 0. $$

Apply Lemma 3.9, eliminate negative parts:

$$ \begin{aligned} \mathrm{Var}(|A_n^{(k)} \cap X_n|) &= |X_n|^2 (\mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n) - \mathrm{Pr}(\{x_1, \dots, x_k\} \subset A_n))^2 \\ &\quad + \sum_{i=1}^k |Y_{i,n}| (\mathrm{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n) - \mathrm{Pr}(\{x_1, \dots, x_{2k}\} \subset A_n)) \\ &\le \sum_{i=1}^k |Y_{i,n}| \mathrm{Pr}(\{x_1, \dots, x_{2k-i}\} \subset A_n). \end{aligned} $$

By Lemma 3.10 (i) and $|Y_{i,n}| \le n^{2k\alpha+i(d-1)+2k \times 10\epsilon}$

$$ \begin{aligned} \mathrm{Var}(|A_n^{(k)} \cap X_n|) &\le \sum_{i=1}^k n^{2k\alpha+i(d-1)-2k \times 10\epsilon} n^{(2k-i)(d-1+\epsilon)} \\ &\le k n^{2k(\alpha+d-1-9\epsilon)}. \end{aligned} $$

*Proof of Theorem 3.7 for uniform density model.* We consider each item.

(i) Suppose that $\alpha + d < 1$. We shall prove that

$$ \mathrm{Pr}(A_n^{(k)} \cap X_n \ne \emptyset) \xrightarrow{n \to \infty} 0. $$

Let $\epsilon > 0$ such that

$$ \epsilon < \min \left\{ \frac{1-d-\alpha}{2}, \frac{\epsilon_0(d)}{10}, d \right\}. $$
By Markov's inequality and Lemma 3.11: If $n \ge \max\{n_\epsilon, (1+2k)^{1/\epsilon}\}$, then

$$
\begin{align*}
\mathbf{Pr}(A_n^{(k)} \cap X_n \neq \emptyset) &= \mathbf{Pr}(|A_n^{(k)} \cap X_n| \geq 1) \\
&\leq \mathbb{E}(|A_n^{(k)} \cap X_n|) \\
&\leq n^{k(\alpha+d-1+2\epsilon)} \xrightarrow{n \to \infty} 0.
\end{align*}
$$

(ii) Suppose that $\alpha + d > 1$. Denote $B_n = A_n^{(k)} \cap X_n$. Let $\epsilon > 0$ be an arbitrary small number, with

$$
\epsilon < \min\left\{\frac{\alpha + d - 1}{3}, \frac{\epsilon_0(d)}{10}, d\right\}.
$$

We shall prove that a.a.s.

$$
n^{k(\alpha+d-1-3\epsilon)} \le |B_n| \le n^{k(\alpha+d-1+3\epsilon)}.
$$

By Lemma 3.11, if $n \ge \max\{n_\epsilon, (1+2k)^{1/\epsilon}\}$, then

$$
n^{k(\alpha+d-1-2\epsilon)} \le \mathbb{E}(|B_n|) \le n^{k(\alpha+d-1+2\epsilon)}.
$$

In addition, if $n \ge 2^{1/k\epsilon}$, we have

$$
n^{k(\alpha+d-1-3\epsilon)} \le \frac{1}{2} n^{k(\alpha+d-1-2\epsilon)} \le \frac{1}{2} \mathbb{E}(|B_n|)
$$

and

$$
\frac{3}{2} \mathbb{E}(|B_n|) \le \frac{3}{2} n^{k(\alpha+d-1+2\epsilon)} \le n^{k(\alpha+d-1+3\epsilon)}.
$$

So, it is enough to prove that a.a.s.

$$
|B_n| - \mathbb{E}(|B_n|) \le \frac{1}{2} \mathbb{E}(|B_n|).
$$

By Chebyshev's inequality,

$$
\mathbf{Pr}(|B_n| - \mathbb{E}(|B_n|) > \frac{1}{2} \mathbb{E}(|B_n|)) \le \frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)}.
$$

Combined with Lemma 3.11, if $n \ge \max\{n_\epsilon, (1+2k)^{1/\epsilon}, 2^{1/k\epsilon}\}$, then

$$
\frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)} \le \frac{4k n^{2k(\alpha+d-1-9\epsilon)}}{n^{2k(\alpha+d-1-2\epsilon)}} \le \frac{4k}{n^{14k\epsilon}} \xrightarrow{n \to \infty} 0.
$$

■
By Markov's inequality and Lemma 3.11: If $n \ge \max\{n_\epsilon, (1+2k)^{1/\epsilon}\}$, then

$$
\begin{align*}
\mathbf{Pr}(A_n^{(k)} \cap X_n \neq \emptyset) &= \mathbf{Pr}(|A_n^{(k)} \cap X_n| \geq 1) \\
&\leq \mathbb{E}(|A_n^{(k)} \cap X_n|) \\
&\leq n^{k(\alpha+d-1+2\epsilon)} \xrightarrow{n \to \infty} 0.
\end{align*}
$$

(ii) Suppose that $\alpha + d > 1$. Denote $B_n = A_n^{(k)} \cap X_n$. Let $\epsilon > 0$ be an arbitrary small number, with

$$
\epsilon < \min\left\{\frac{\alpha + d - 1}{3}, \frac{\epsilon_0(d)}{10}, d\right\}.
$$

We shall prove that a.a.s.

$$
n^{k(\alpha+d-1-3\epsilon)} \le |B_n| \le n^{k(\alpha+d-1+3\epsilon)}.
$$

By Lemma 3.11, if $n \ge \max\{n_\epsilon, (1+2k)^{1/\epsilon}\}$, then

$$
n^{k(\alpha+d-1-2\epsilon)} \le \mathbb{E}(|B_n|) \le n^{k(\alpha+d-1+2\epsilon)}.
$$

In addition, if $n \ge 2^{1/k\epsilon}$, we have

$$
n^{k(\alpha+d-1-3\epsilon)} \le \frac{1}{2} n^{k(\alpha+d-1-2\epsilon)} \le \frac{1}{2} \mathbb{E}(|B_n|)
$$

and

$$
\frac{3}{2} \mathbb{E}(|B_n|) \le \frac{3}{2} n^{k(\alpha+d-1+2\epsilon)} \le n^{k(\alpha+d-1+3\epsilon)}.
$$

So, it is enough to prove that a.a.s.

$$
|B_n| - \mathbb{E}(|B_n|) \le \frac{1}{2} \mathbb{E}(|B_n|).
$$

By Chebyshev's inequality,

$$
\mathbf{Pr}(|B_n| - \mathbb{E}(|B_n|) > \frac{1}{2} \mathbb{E}(|B_n|)) \le \frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)}.
$$

Combined with Lemma 3.11, if $n \ge \max\{n_\epsilon, (1+2k)^{1/\epsilon}, 2^{1/k\epsilon}\}$, then

$$
\frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)} \le \frac{4k n^{2k(\alpha+d-1-9\epsilon)}}{n^{2k(\alpha+d-1-2\epsilon)}} \le \frac{4k}{n^{14k\epsilon}} \xrightarrow{n \to \infty} 0.
$$

■
**3.4. The general model (densable and permutation invariant)**

Let $\mathbf{X}$ be a sequence of subsets of $\mathbf{E}^{(k)}$ having the $d$-small intersection condition.
Recall that

$$
\varepsilon_0(d) = \min_{1 \le i \le k} \left\{ \alpha + (d-1) \frac{i}{2k} - \overline{\mathrm{dens}} \mathbf{Y}_i \right\} > 0.
$$

Note that if $d' < d$ then $\varepsilon(d') < \varepsilon(d)$.

In order to apply Lemma 3.11 in a small interval $[d - \varepsilon, d + \varepsilon]$, we choose

$$
0 < \varepsilon < \min\left\{\frac{\varepsilon_0(d)}{20}, \frac{d}{2}\right\},
$$

so that

$$
\varepsilon < \min \left\{ \frac{\varepsilon_0(d - \varepsilon)}{10}, d - \varepsilon \right\} \le \min \left\{ \frac{\varepsilon_0(d')}{10}, d' \right\}
$$

for every $d' \in [d - \varepsilon, d + \varepsilon]$.

By the definition of $\varepsilon_0$ and the densability of $\mathbf{X}$, we choose again $n_\varepsilon \in \mathbb{N}$ such
that for all $n \ge n_\varepsilon$,

$$
|Y_{n,i}| \le n^{2k\alpha+(d-1)i-2k \times 20\epsilon} \le n^{2k\alpha+(d'-1)i-2k \times 10\epsilon} \quad \forall 1 \le i \le k
$$

and

$$
n^{k(\alpha-\epsilon)} \le |X_n| \le n^{k(\alpha+\epsilon)}.
$$

**Lemma 3.12.** Let $0 < \varepsilon < \min\{\varepsilon_0(d)/20, d/2\}$ be a small real number. Let $\mathbf{A}$ be a sequence of uniform random subsets of $\mathbf{E}$ with density $d' \in [d-\varepsilon, d+\varepsilon]$. Let $\mathbf{X}$ be a sequence of subsets of $\mathbf{E}^{(k)}$ with density $\alpha$. If $n \ge \max\{n_\varepsilon, (1+2k)^{1/\varepsilon}\}$, then

$$
(i) \quad n^{k(\alpha+d-1-3\varepsilon)} \le \mathbb{E}(|A_n^{(k)} \cap X_n|) \le n^{k(\alpha+d-1+3\varepsilon)}.
$$

(ii) If in addition $\alpha + d - 1 > 3\epsilon > 0$ and $\mathbf{X}$ has $d$-small self-intersection, then

$$
\mathrm{Var}(|A_n^{(k)} \cap X_n|) \le k n^{2k(\alpha+d-1-8\epsilon)}.
$$

*Proof.* We consider each item.

(i) Recall from the above discussion that $\varepsilon < \min\{\varepsilon_0(d')/10, d'\}$. By Lemma 3.11,

$$
n^{k(\alpha+d'-1-2\epsilon)} \le \mathbb{E}(|A_n^{(k)} \cap X_n|) \le n^{k(\alpha+d'-1+2\epsilon)}.
$$

We then have the inequality by $d - \varepsilon \le d' \le d + \varepsilon$.

(ii) Because $\varepsilon_0(d') > 0$, $\mathbf{X}$ has $d'$-small self-intersection. By Lemma 3.11 and the fact that $d' \le d + \varepsilon$,

$$
\mathrm{Var}(|A_n^{(k)} \cap X_n|) \le k n^{2k(\alpha+d'-1-9\epsilon)} \le k n^{2k(\alpha+d-1-8\epsilon)}.
$$

■
### 3.4. The general model (densable and permutation invariant)

Let $\mathbf{X}$ be a sequence of subsets of $\mathbf{E}^{(k)}$ having the $d$-small intersection condition.
Recall that

$$ \varepsilon_0(d) = \min_{1 \le i \le k} \left\{ \alpha + (d-1) \frac{i}{2k} - \overline{\mathrm{dens}} \mathbf{Y}_i \right\} > 0. $$

Note that if $d' < d$ then $\varepsilon(d') < \varepsilon(d)$.

In order to apply Lemma 3.11 in a small interval $[d - \varepsilon, d + \varepsilon]$, we choose

$$ 0 < \varepsilon < \min \left\{ \frac{\varepsilon_0(d)}{20}, \frac{d}{2} \right\}, $$

so that

$$ \varepsilon < \min \left\{ \frac{\varepsilon_0(d - \varepsilon)}{10}, d - \varepsilon \right\} \le \min \left\{ \frac{\varepsilon_0(d')}{10}, d' \right\} $$

for every $d' \in [d - \varepsilon, d + \varepsilon]$.

By the definition of $\varepsilon_0$ and the densability of $\mathbf{X}$, we choose again $n_\varepsilon \in \mathbb{N}$ such that for all $n \ge n_\varepsilon$,

$$ |Y_{n,i}| \le n^{2k\alpha+(d-1)i-2k \times 20\varepsilon} \le n^{2k\alpha+(d'-1)i-2k \times 10\varepsilon} \quad \forall 1 \le i \le k $$

and

$$ n^{k(\alpha-\varepsilon)} \le |X_n| \le n^{k(\alpha+\varepsilon)}. $$

**Lemma 3.12.** Let $0 < \varepsilon < \min\{\varepsilon_0(d)/20, d/2\}$ be a small real number. Let $\mathbf{A}$ be a sequence of uniform random subsets of $\mathbf{E}$ with density $d' \in [d - \varepsilon, d + \varepsilon]$. Let $\mathbf{X}$ be a sequence of subsets of $\mathbf{E}^{(k)}$ with density $\alpha$. If $n \ge \max\{n_\varepsilon, (1+2k)^{1/\varepsilon}\}$, then

$$ (i) \quad n^{k(\alpha+d-1-3\varepsilon)} \le \mathbb{E}(|A_n^{(k)} \cap X_n|) \le n^{k(\alpha+d-1+3\varepsilon)}. $$

(ii) If in addition $\alpha + d - 1 > 3\varepsilon > 0$ and $\mathbf{X}$ has $d$-small self-intersection, then

$$ \mathrm{Var}(|A_n^{(k)} \cap X_n|) \le k n^{2k(\alpha+d-1-8\varepsilon)}. $$

*Proof.* We consider each item.

(i) Recall from the above discussion that $\varepsilon < \min\{\varepsilon_0(d')/10, d'\}$. By Lemma 3.11,

$$ n^{k(\alpha+d'-1-2\varepsilon)} \le \mathbb{E}(|A_n^{(k)} \cap X_n|) \le n^{k(\alpha+d'-1+2\varepsilon)}. $$

We then have the inequality by $d - \varepsilon \le d' \le d + \varepsilon$.

(ii) Because $\varepsilon_0(d') > 0$, $\mathbf{X}$ has $d'$-small self-intersection. By Lemma 3.11 and the fact that $d' \le d + \varepsilon$,

$$ \mathrm{Var}(|A_n^{(k)} \cap X_n|) \le k n^{2k(\alpha+d'-1-9\varepsilon)} \le k n^{2k(\alpha+d-1-8\varepsilon)}. \quad \blacksquare $$
**Lemma 3.13 (Concentration lemma).** Let $\varepsilon > 0$ be an arbitrary small real number. Let $A$ and $X$ given as the previous lemma, with $\alpha + d - 1 > 4\varepsilon > 0$ and $X$ having $d$-small self-intersection. If $\varepsilon < \min\{\varepsilon_0/10, d/2\}$ and $n \ge \max\{n_\varepsilon, (1+2k)^{1/\varepsilon}\}$, then

$$ \mathrm{Pr}(n^{k(\alpha+d-1-4\varepsilon)} \le |A_n^{(k)} \cap X_n| \le n^{k(\alpha+d-1+4\varepsilon)}) > 1 - kn^{-10k\varepsilon}. $$

*Proof.* Denote $B_n = A_n^{(k)} \cap X_n$. By Lemma 3.12 (i) and $n^{k\varepsilon} \ge 2$, we have

$$ n^{k(\alpha+d-1-4\varepsilon)} \le \frac{1}{2} n^{k(\alpha+d-1-3\varepsilon)} \le \frac{1}{2} \mathbb{E}(|B_n|) $$

and

$$ \frac{3}{2} \mathbb{E}(|B_n|) \le \frac{3}{2} n^{k(\alpha+d-1+3\varepsilon)} \le n^{k(\alpha+d-1+4\varepsilon)}. $$

By Chebyshev's inequality,

$$ \begin{aligned} \mathrm{Pr}(n^{k(\alpha+d-1-4\varepsilon)} \le |B_n| \le n^{k(\alpha+d-1+4\varepsilon)}) &\ge \mathrm{Pr}(|B_n| - \mathbb{E}(|B_n|) \le \frac{1}{2}\mathbb{E}(|B_n|)) \\ &\ge 1 - \frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)}. \end{aligned} $$

Again by Lemma 3.12,

$$ \frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)} \le \frac{k n^{2k(\alpha+d-1-8\varepsilon)}}{n^{2k(\alpha+d-1-3\varepsilon)}} \le k n^{-10k\varepsilon}. \quad \blacksquare $$

*Proof of the Theorem 3.7.* Let $\varepsilon > 0$ be an arbitrary small number with $\varepsilon < \min\{d/2, \varepsilon_0(d)/20\}$ as given in Lemma 3.12. Denote $Q_n = \{n^{d-\varepsilon} \le |A_n| \le n^{d+\varepsilon}\}$ and

$$ \mathbb{N}_{A, \varepsilon, n} := \{ \ell \in \mathbb{N} \mid n^{d-\varepsilon} \le \ell \le n^{d+\varepsilon} \text{ and } \mathrm{Pr}(|A_n| = \ell) > 0 \}. $$

By densability of $A$, we have $\mathrm{Pr}(Q_n) \xrightarrow{n \to \infty} 1$. Denote by $\mathrm{Pr}_{Q_n} := \mathrm{Pr}(\cdot | Q_n)$ the probability measure under the condition $\overline{Q}_n$. Define similarly $\mathbb{E}_{Q_n}$ and $\mathrm{Var}_{Q_n}$.

In order to prove that some sequence of properties ($R_n$) is a.a.s. true, by the inequality

$$ \mathrm{Pr}(\overline{R_n}) \le \mathrm{Pr}(Q_n) \mathrm{Pr}_{Q_n}(\overline{R_n}) + \mathrm{Pr}(\overline{Q_n}), $$

it is enough to prove that $\mathrm{Pr}_{Q_n}(\overline{R_n}) \xrightarrow{n \to \infty} 0$.

(i) Suppose that $\alpha + d < 1$. Assume in addition that $\varepsilon < (1-d-\alpha)/3$. We shall prove that

$$ \mathrm{Pr}_{Q_n}(A_n^{(k)} \cap X_n \ne \emptyset) = \mathrm{Pr}_{Q_n}(|A_n^{(k)} \cap X_n| \ge 1) \xrightarrow{n \to \infty} 0. $$
**Lemma 3.13 (Concentration lemma).** Let $\varepsilon > 0$ be an arbitrary small real number. Let $A$ and $X$ given as the previous lemma, with $\alpha + d - 1 > 4\varepsilon > 0$ and $X$ having $d$-small self-intersection. If $\varepsilon < \min\{\varepsilon_0/10, d/2\}$ and $n \ge \max\{n_\varepsilon, (1+2k)^{1/\varepsilon}\}$, then

$$ \mathrm{Pr}(n^{k(\alpha+d-1-4\varepsilon)} \le |A_n^{(k)} \cap X_n| \le n^{k(\alpha+d-1+4\varepsilon)}) > 1 - kn^{-10k\varepsilon}. $$

*Proof.* Denote $B_n = A_n^{(k)} \cap X_n$. By Lemma 3.12 (i) and $n^{k\varepsilon} \ge 2$, we have

$$ n^{k(\alpha+d-1-4\varepsilon)} \le \frac{1}{2} n^{k(\alpha+d-1-3\varepsilon)} \le \frac{1}{2} \mathbb{E}(|B_n|) $$

and

$$ \frac{3}{2} \mathbb{E}(|B_n|) \le \frac{3}{2} n^{k(\alpha+d-1+3\varepsilon)} \le n^{k(\alpha+d-1+4\varepsilon)}. $$

By Chebyshev's inequality,

$$ \begin{aligned} \mathrm{Pr}(n^{k(\alpha+d-1-4\varepsilon)} \le |B_n| \le n^{k(\alpha+d-1+4\varepsilon)}) &\ge \mathrm{Pr}(|B_n| - \mathbb{E}(|B_n|) \le \frac{1}{2}\mathbb{E}(|B_n|)) \\ &\ge 1 - \frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)}. \end{aligned} $$

Again by Lemma 3.12,

$$ \frac{4 \mathrm{Var}(|B_n|)}{\mathbb{E}(|B_n|^2)} \le \frac{k n^{2k(\alpha+d-1-8\varepsilon)}}{n^{2k(\alpha+d-1-3\varepsilon)}} \le k n^{-10k\varepsilon}. \quad \blacksquare $$

*Proof of the Theorem 3.7.* Let $\varepsilon > 0$ be an arbitrary small number with $\varepsilon < \min\{d/2, \varepsilon_0(d)/20\}$ as given in Lemma 3.12. Denote $Q_n = \{n^{d-\varepsilon} \le |A_n| \le n^{d+\varepsilon}\}$ and

$$ \mathbb{N}_{A, \varepsilon, n} := \{ \ell \in \mathbb{N} \mid n^{d-\varepsilon} \le \ell \le n^{d+\varepsilon} \text{ and } \mathrm{Pr}(|A_n| = \ell) > 0 \}. $$

By densability of $A$, we have $\mathrm{Pr}(Q_n) \xrightarrow{n \to \infty} 1$. Denote by $\mathrm{Pr}_{Q_n} := \mathrm{Pr}(\cdot | Q_n)$ the probability measure under the condition $\overline{Q}_n$. Define similarly $\mathbb{E}_{Q_n}$ and $\mathrm{Var}_{Q_n}$.

In order to prove that some sequence of properties ($R_n$) is a.a.s. true, by the inequality

$$ \mathrm{Pr}(\overline{R_n}) \le \mathrm{Pr}(Q_n) \mathrm{Pr}_{Q_n}(\overline{R_n}) + \mathrm{Pr}(\overline{Q_n}), $$

it is enough to prove that $\mathrm{Pr}_{Q_n}(\overline{R_n}) \xrightarrow{n \to \infty} 0$.

(i) Suppose that $\alpha + d < 1$. Assume in addition that $\varepsilon < (1-d-\alpha)/3$. We shall prove that

$$ \mathrm{Pr}_{Q_n}(A_n^{(k)} \cap X_n \ne \emptyset) = \mathrm{Pr}_{Q_n}(|A_n^{(k)} \cap X_n| \ge 1) \xrightarrow{n \to \infty} 0. $$
By the formula of total probability and Markov's inequality,

$$
\begin{align*}
\mathbf{Pr}_{Q_n}(|A_n^{(k)} \cap X_n| \ge 1) &\le \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l) \mathbf{Pr}(|A_n^{(k)} \cap X_n| \ge 1 \mid |A_n| = l) \\
&\le \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l) \mathbb{E}(|A_n^{(k)} \cap X_n| \mid |A_n| = l).
\end{align*}
$$

By a change of variable $l = n^{d'}$ with $d - \varepsilon \le d' \le d + \varepsilon$, apply Lemma 3.12:

$$
\begin{align*}
\mathbf{Pr}_{Q_n}(|A_n^{(k)} \cap X_n| \ge 1) &\le \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l = n^{d'}) n^{\alpha+d-1+3\varepsilon} \\
&\le n^{\alpha+d-1+3\varepsilon} \xrightarrow{n \to \infty} 0.
\end{align*}
$$

(ii) Suppose that $\alpha + d > 1$. Assume in addition that $\varepsilon < (\alpha + d - 1)/4$, so that we can apply Lemma 3.13. We shall prove that

$$
\mathbf{Pr}_{Q_n} (n^{k(\alpha+d-1-4\varepsilon)} \le |A_n^{(k)} \cap X_n| \le n^{k(\alpha+d-1+4\varepsilon)}) \xrightarrow{n \to \infty} 1.
$$

By the formula of total probability, Lemma 3.13 and a change of variables $l = n^{d'}$:

$$
\begin{align*}
& \mathbf{Pr}_{Q_n} (n^{k(\alpha+d-1-4\varepsilon)} \le |A_n^{(k)} \cap X_n| \le n^{k(\alpha+d-1+4\varepsilon)}) \\
&= \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l) \\
& \quad \cdot \mathbf{Pr}(n^{k(\alpha+d-1-4\varepsilon)} \le |A_n^{(k)} \cap X_n| \le n^{k(\alpha+d-1+4\varepsilon)} \mid |A_n| = l) \\
&\ge \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l = n^{d'})(1 - kn^{-10k\varepsilon}) \\
&\ge 1 - kn^{-10k\varepsilon} \xrightarrow{n \to \infty} 1. \quad \blacksquare
\end{align*}
$$

**4. Applications to group theory**

Fix an alphabet $X = \{x_1, \dots, x_m\}$ as generators of groups. Let $B_\ell$ be the set of cycli-
cally reduced words of length at most $\ell$ on $X^\pm$. Recall that $|B_\ell| = (2m-1)^{\ell+O(1)}$.

We are interested in asymptotic behaviors, when $\ell$ goes to infinity, of group pre-
sentations $\langle X | R_\ell \rangle$ where $R_\ell$ is a random subset of $B_\ell$.

**Definition 4.1** (Random groups with density). Let $d \in ]0, 1]$. Let $\mathbf{R} = (R_\ell)$ be a densable sequence of permutation invariant random subsets with density $d$ of the sequence $\mathbf{B} = (B_\ell)$.

Denote $G_\ell = G_\ell(m, d)$ the random presentation defined by $\langle X | R_\ell \rangle$. The sequence
$\mathbf{G} = \mathbf{G}(m, d) = (G_\ell(m, d))_{\ell \in \mathbb{N}}$ is called a sequence of random groups with den-
sity $d$.
By the formula of total probability and Markov's inequality,

$$
\begin{align*}
\mathbf{Pr}_{Q_n}(|A_n^{(k)} \cap X_n| \ge 1) &\le \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l) \mathbf{Pr}(|A_n^{(k)} \cap X_n| \ge 1 \mid |A_n| = l) \\
&\le \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l) \mathbb{E}(|A_n^{(k)} \cap X_n| \mid |A_n| = l).
\end{align*}
$$

By a change of variable $l = n^{d'}$ with $d - \varepsilon \le d' \le d + \varepsilon$, apply Lemma 3.12:

$$
\begin{align*}
\mathbf{Pr}_{Q_n}(|A_n^{(k)} \cap X_n| \ge 1) &\le \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l = n^{d'}) n^{\alpha+d-1+3\varepsilon} \\
&\le n^{\alpha+d-1+3\varepsilon} \xrightarrow{n \to \infty} 0.
\end{align*}
$$

(ii) Suppose that $\alpha + d > 1$. Assume in addition that $\varepsilon < (\alpha + d - 1)/4$, so that we can apply Lemma 3.13. We shall prove that

$$
\mathbf{Pr}_{Q_n} (n^{k(\alpha+d-1-4\varepsilon)} \le |A_n^{(k)} \cap X_n| \le n^{k(\alpha+d-1+4\varepsilon)}) \xrightarrow{n \to \infty} 1.
$$

By the formula of total probability, Lemma 3.13 and a change of variables $l = n^{d'}$:

$$
\begin{align*}
& \mathbf{Pr}_{Q_n} (n^{k(\alpha+d-1-4\varepsilon)} \le |A_n^{(k)} \cap X_n| \le n^{k(\alpha+d-1+4\varepsilon)}) \\
&= \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l) \\
&\qquad \cdot \mathbf{Pr} (n^{k(\alpha+d-1-4\varepsilon)} \le |A_n^{(k)} \cap X_n| \le n^{k(\alpha+d-1+4\varepsilon)} \mid |A_n| = l) \\
&\ge \sum_{l \in \mathbb{N}_{A, \varepsilon, n}} \mathbf{Pr}_{Q_n}(A_n = l = n^{d'})(1 - kn^{-10k\varepsilon}) \\
&\ge 1 - kn^{-10k\varepsilon} \xrightarrow{n \to \infty} 1. \quad \blacksquare
\end{align*}
$$

**4. Applications to group theory**

Fix an alphabet $X = \{x_1, \dots, x_m\}$ as generators of groups. Let $B_\ell$ be the set of cycli-
cally reduced words of length at most $\ell$ on $X^\pm$. Recall that $|B_\ell| = (2m-1)^{\ell+O(1)}$.

We are interested in asymptotic behaviors, when $\ell$ goes to infinity, of group pre-
sentations $\langle X | R_\ell \rangle$ where $R_\ell$ is a random subset of $B_\ell$.

**Definition 4.1** (Random groups with density). Let $d \in ]0, 1]$. Let $\mathbf{R} = (R_\ell)$ be a densable sequence of permutation invariant random subsets with density $d$ of the sequence $\mathbf{B} = (B_\ell)$.

Denote $G_\ell = G_\ell(m, d)$ the random presentation defined by $\langle X | R_\ell \rangle$. The sequence
$\mathbf{G} = \mathbf{G}(m, d) = (G_\ell(m, d))_{\ell \in \mathbb{N}}$ is called a sequence of random groups with den-
sity $d$.
For example, if $d = 1$, then $G_\ell(m, 1)$ is isomorphic to the trivial group.

A sequence of events $\mathcal{Q} = (Q_\ell)$ described by $\mathcal{G}(m, d)$ is asymptotically almost surely satisfied if $\Pr(Q_\ell) \xrightarrow{m \to \infty} 1$. We denote briefly a.a.s. $Q_\ell$.

**4.1. Phase transition at density 1/2**

**Theorem 4.2** (Gromov, phase transition at density 1/2). Let $(G_\ell(m, d))$ be a sequence of random groups with density $d$.

(i) If $d > 1/2$, then a.a.s. $G_\ell(m, d)$ is isomorphic to the trivial group.

(ii) If $d < 1/2$, then a.a.s. $G_\ell(m, d)$ is a hyperbolic group.

In [15, Section 2.1] (or [16, Section I.2.b]), Ollivier proved the first assertion by probabilistic pigeon-hole principle. We give a proof here by the intersection formula (Theorem 2.9 and Corollary 3.8).

*Proof of Theorem 4.2* (i). Let $x \in X$. Let $A_\ell$ be the set of cyclically reduced words that does not start or end by $x$, of lengths at most $\ell - 1$ (so that $xA_\ell \subset B_\ell$). It is easy to check that the sequences $(A_\ell)$ and $(xA_\ell)$ are sequences of fixed subsets of $\mathcal{B} = (B_\ell)$ of density 1. By the random-fixed intersection formula (Corollary 3.8), the sequences $(x(R_\ell \cap A_\ell))$ and $(R_\ell \cap xA_\ell)$ are sequences of permutation invariant random subsets of $(xA_\ell)$ of density $d$.

By the intersection formula (Theorem 2.9), their intersection $(xR_\ell \cap R_\ell \cap xA_\ell)$ is a sequence of permutation invariant random subsets of $(xA_\ell)$ of density $(2d - 1) > 0$, which is a.a.s. not empty. Thus, a.a.s. there exists a word $w \in A_\ell$ such that $w \in R_\ell$ and $xw \in R_\ell$, so a.a.s. $x = 1$ in $G_\ell$ by canceling $w$.

The argument above works for any generator $x \in X$. By intersecting a finite number of a.a.s. satisfied events, a.a.s. all generators $x \in X$ are trivial in $G_\ell$. Hence, a.a.s. $G_\ell$ is isomorphic to the trivial group. $\blacksquare$

The proof of Theorem 4.2 (ii) needs *van Kampen diagrams* and will not be treated here. See [9, Section 9.B] for the original idea by Gromov, and [15, Section 2.2] or [16, Section V] for a detailed proof by Ollivier.

**4.2. Phase transition at density $\lambda/2$**

**Theorem 4.3.** Let $G(m, d) = (G_\ell(m, d))$ be a sequence of random groups with density $d$. Let $\lambda \in ]0, 1[$.

(i) If $d < \lambda/2$, then a.a.s. $G_\ell(m, d)$ satisfies $C'(\lambda)$.

(ii) If $d > \lambda/2$, then a.a.s. $G_\ell(m, d)$ does not satisfy $C'(\lambda)$.
For example, if $d = 1$, then $G_\ell(m, 1)$ is isomorphic to the trivial group.

A sequence of events $\mathcal{Q} = (Q_\ell)$ described by $\mathcal{G}(m, d)$ is asymptotically almost surely satisfied if $\Pr(Q_\ell) \xrightarrow{m\to\infty} 1$. We denote briefly a.a.s. $Q_\ell$.

**4.1. Phase transition at density 1/2**

**Theorem 4.2** (Gromov, phase transition at density 1/2). Let $(G_\ell(m, d))$ be a sequence of random groups with density $d$.

(i) If $d > 1/2$, then a.a.s. $G_\ell(m, d)$ is isomorphic to the trivial group.

(ii) If $d < 1/2$, then a.a.s. $G_\ell(m, d)$ is a hyperbolic group.

In [15, Section 2.1] (or [16, Section I.2.b]), Ollivier proved the first assertion by probabilistic pigeon-hole principle. We give a proof here by the intersection formula (Theorem 2.9 and Corollary 3.8).

*Proof of Theorem 4.2* (i). Let $x \in X$. Let $A_\ell$ be the set of cyclically reduced words that does not start or end by $x$, of lengths at most $\ell - 1$ (so that $xA_\ell \subset B_\ell$). It is easy to check that the sequences $(A_\ell)$ and $(xA_\ell)$ are sequences of fixed subsets of $\mathcal{B} = (B_\ell)$ of density 1. By the random-fixed intersection formula (Corollary 3.8), the sequences $(x(R_\ell \cap A_\ell))$ and $(R_\ell \cap xA_\ell)$ are sequences of permutation invariant random subsets of $(xA_\ell)$ of density $d$.

By the intersection formula (Theorem 2.9), their intersection $(xR_\ell \cap R_\ell \cap xA_\ell)$ is a sequence of permutation invariant random subsets of $(xA_\ell)$ of density $(2d - 1) > 0$, which is a.a.s. not empty. Thus, a.a.s. there exists a word $w \in A_\ell$ such that $w \in R_\ell$ and $xw \in R_\ell$, so a.a.s. $x = 1$ in $G_\ell$ by canceling $w$.

The argument above works for any generator $x \in X$. By intersecting a finite number of a.a.s. satisfied events, a.a.s. all generators $x \in X$ are trivial in $G_\ell$. Hence, a.a.s. $G_\ell$ is isomorphic to the trivial group. $\blacksquare$

The proof of Theorem 4.2 (ii) needs *van Kampen diagrams* and will not be treated here. See [9, Section 9.B] for the original idea by Gromov, and [15, Section 2.2] or [16, Section V] for a detailed proof by Ollivier.

**4.2. Phase transition at density $\lambda/2$**

**Theorem 4.3.** Let $G(m, d) = (G_\ell(m, d))$ be a sequence of random groups with density $d$. Let $\lambda \in ]0, 1[$.

(i) If $d < \lambda/2$, then a.a.s. $G_\ell(m, d)$ satisfies $C'(\lambda)$.

(ii) If $d > \lambda/2$, then a.a.s. $G_\ell(m, d)$ does not satisfy $C'(\lambda)$.
<figure><img src="image_3.png" /><figcaption>**Figure 1.** A cyclically reduced word having a piece that appears twice.</figcaption></figure>

*Proof.* We consider each item.

(i) Recall that (Lyndon–Schupp [13, p. 240]) a piece with respect to a set of relators is a cyclic sub-word that appears at least twice. There are two cases to verify.

(a) Let $A_\ell$ be the set of cyclically reduced words of length at most $\ell$ having a piece appearing twice on itself (Figure 1) that is longer than $\lambda$ times itself. We shall prove that a.a.s. the intersection $A_\ell \cap R_\ell$ is empty. We estimate first the number of relators of length $t \le \ell$ with a piece of length $s \ge \lambda t$. There are $2t$ ways (including orientations) to choose the first position of the piece, and $2t-s$ ways the choose the second position (note that because $r$ is reduced, it can not overlay the first one if they are with opposite orientations). For each way of positioning we can determine freely $t-s$ letters, each with $(2m-1)$ choices, except for the first letter and the last letter having respectively $2m$ and $2m-2$ or $2m-1$ choices. So this number is $2t(2t-s)C(m)(2m-1)^{t-s}$, where $C(m)$ is a real number that depends only on $m$. Hence,

$$|A_{\ell}| = \sum_{t=1}^{\ell} \sum_{s=\lfloor \lambda t \rfloor}^{t} 2t(2t-s)C(m)(2m-1)^{t-s} = (2m-1)^{(1-\lambda)\ell+o(\ell)},$$

which means that $(A_\ell)$ is a sequence of fixed subsets of $(B_\ell)$ with density $1 - \lambda$. By the intersection formula (Corollary 3.8), because $1 - \lambda + d < 1$, we have a.a.s.

$$A_{\ell} \cap R_{\ell} = \emptyset.$$

(b) Let $X_\ell$ be the set of distinct pairs of relators $r_1, r_2$ in $B_\ell$ having a piece (Figure 2) longer than $\lambda \min\{|r_1|, |r_2|\}$. It is a fixed subset of $B_\ell^{(2)}$. We shall prove that a.a.s the intersection $X_\ell \cap R_\ell^{(2)}$ is empty. There are $4\ell^2$ possible positions for pieces, $(2m-1)^{\ell+o(\ell)}$ choices for $r_1$ and $(2m-1)^{\ell-\lambda\ell+o(\ell)}$ choices for $r_2$. So,

$$|X_{\ell}| = (2m-1)^{(2-\lambda)\ell+o(\ell)},$$

which means that $(X_\ell)$ is a sequence of fixed subsets of $(B_\ell^{(2)})$ with density $1 - \frac{\lambda}{2}$. By the multi-dimension intersection formula (Theorem 3.7 (i)), because $1 - \frac{\lambda}{2} + d < 1$, we have a.a.s.

$$X_{\ell} \cap R_{\ell}^{(2)} = \emptyset.$$
<figure><img src="image_2.png" /><figcaption>**Figure 1.** A cyclically reduced word having a piece that appears twice.</figcaption></figure>

*Proof.* We consider each item.

(i) Recall that (Lyndon–Schupp [13, p. 240]) a piece with respect to a set of relators is a cyclic sub-word that appears at least twice. There are two cases to verify.

(a) Let $A_\ell$ be the set of cyclically reduced words of length at most $\ell$ having a piece appearing twice on itself (Figure 1) that is longer than $\lambda$ times itself. We shall prove that a.a.s. the intersection $A_\ell \cap R_\ell$ is empty. We estimate first the number of relators of length $t \le \ell$ with a piece of length $s \ge \lambda t$. There are $2t$ ways (including orientations) to choose the first position of the piece, and $2t-s$ ways the choose the second position (note that because $r$ is reduced, it can not overlay the first one if they are with opposite orientations). For each way of positioning we can determine freely $t-s$ letters, each with $(2m-1)$ choices, except for the first letter and the last letter having respectively $2m$ and $2m-2$ or $2m-1$ choices. So this number is $2t(2t-s)C(m)(2m-1)^{t-s}$, where $C(m)$ is a real number that depends only on $m$. Hence,

$$|A_{\ell}| = \sum_{t=1}^{\ell} \sum_{s=\lfloor \lambda t \rfloor}^{t} 2t(2t-s)C(m)(2m-1)^{t-s} = (2m-1)^{(1-\lambda)\ell+o(\ell)},$$

which means that $(A_\ell)$ is a sequence of fixed subsets of $(B_\ell)$ with density $1 - \lambda$. By the intersection formula (Corollary 3.8), because $1 - \lambda + d < 1$, we have a.a.s.

$$A_{\ell} \cap R_{\ell} = \emptyset.$$

(b) Let $X_\ell$ be the set of distinct pairs of relators $r_1, r_2$ in $B_\ell$ having a piece (Figure 2) longer than $\lambda \min\{|r_1|, |r_2|\}$. It is a fixed subset of $B_\ell^{(2)}$. We shall prove that a.a.s the intersection $X_\ell \cap R_\ell^{(2)}$ is empty. There are $4\ell^2$ possible positions for pieces, $(2m-1)^{\ell+o(\ell)}$ choices for $r_1$ and $(2m-1)^{\ell-\lambda\ell+o(\ell)}$ choices for $r_2$. So,

$$|X_{\ell}| = (2m-1)^{(2-\lambda)\ell+o(\ell)},$$

which means that $(X_\ell)$ is a sequence of fixed subsets of $(B_\ell^{(2)})$ with density $1 - \frac{\lambda}{2}$. By the multi-dimension intersection formula (Theorem 3.7 (i)), because $1 - \frac{\lambda}{2} + d < 1$, we have a.a.s.

$$X_{\ell} \cap R_{\ell}^{(2)} = \emptyset.$$
<figure><img src="image_4.png" /><figcaption>**Figure 2.** A pair of relators sharing a common subword (a piece).</figcaption></figure>

(ii) Take the sequence of sets $X = (X_\ell)$ constructed in part 1 (b). We shall prove that a.a.s. the intersection $X_\ell \cap R_\ell^{(2)}$ is not empty. We have already

$$ \text{dens } X + \text{dens } R^{(2)} > 1. $$

To apply Theorem 3.7 (ii), we need to calculate the size of the self-intersection

$$ Y_{1,\ell} = \{(x_1, x_2) \in X_\ell^2 \mid |x_1 \cap x_2| = 1\}. $$

Take $x_1 = (r_1, r_2)$ and $x_2 = (r_1, r_3)$, where $r_1, r_2, r_3$ are three different relators in $B_\ell$. There are $(2m-1)^{\ell+o(\ell)}$ choices for $r_1$, $(2m-1)^{\ell-\lambda\ell+o(\ell)}$ choices for $r_2$ and $(2m-1)^{\ell-\lambda\ell+o(\ell)}$ choices for $r_3$. The other three cases ($x_2 = (r_2, r_3)$, $(r_3, r_1)$, or $(r_3, r_2)$) are symmetric. Multiply these numbers, we have

$$ |Y_{1,\ell}| = (2m-1)^{3\ell-2\lambda\ell+o(\ell)}. $$

The density of $Y_1 = (Y_{1,\ell})$ is $(3-2\lambda)/4$ in $(B_\ell^{(2)})^2$. As $d > 0$, we have $(3-2\lambda)/4 < 1 - \frac{\lambda}{2} + \frac{1}{4}(d-1)$, which implies

$$ \text{dens } Y_1 < \text{dens } X + (d-1) \frac{1}{2 \times 2}. $$

Thus, we have the $d$-small self intersection condition (Definition 3.6). By the multi-dimensional intersection formula, a.a.s.

$$ X_{\ell} \cap R_{\ell}^{(2)} \neq \emptyset. \qquad \blacksquare $$

### 4.3. Every $(m-1)$-generated subgroup is free

Fix the set of $m$ generators $X = \{x_1, \dots, x_m\}$. Recall that $B_\ell$ is the set of $(2m-1)^{\ell+o(\ell)}$ cyclically reduced words on $X^\pm = \{x_1^\pm, \dots, x_m^\pm\}$ of length at most $\ell$. The few relator model of random groups is constructed as follows: fix a number $k \in \mathbb{N}$ and let

$$ G_{\ell} = \langle x_1, \dots, x_m \mid r_1, \dots, r_k \rangle, $$
<figure><img src="image_3.png" /><figcaption>**Figure 2.** A pair of relators sharing a common subword (a piece).</figcaption></figure>

(ii) Take the sequence of sets $X = (X_\ell)$ constructed in part 1 (b). We shall prove that a.a.s. the intersection $X_\ell \cap R_\ell^{(2)}$ is not empty. We have already

$$ \text{dens } X + \text{dens } R^{(2)} > 1. $$

To apply Theorem 3.7 (ii), we need to calculate the size of the self-intersection

$$ Y_{1,\ell} = \{(x_1, x_2) \in X_\ell^2 \mid |x_1 \cap x_2| = 1\}. $$

Take $x_1 = (r_1, r_2)$ and $x_2 = (r_1, r_3)$, where $r_1, r_2, r_3$ are three different relators in $B_\ell$. There are $(2m-1)^{\ell+o(\ell)}$ choices for $r_1$, $(2m-1)^{\ell-\lambda\ell+o(\ell)}$ choices for $r_2$ and $(2m-1)^{\ell-\lambda\ell+o(\ell)}$ choices for $r_3$. The other three cases ($x_2 = (r_2, r_3)$, $(r_3, r_1)$, or $(r_3, r_2)$) are symmetric. Multiply these numbers, we have

$$ |Y_{1,\ell}| = (2m-1)^{3\ell-2\lambda\ell+o(\ell)}. $$

The density of $Y_1 = (Y_{1,\ell})$ is $(3-2\lambda)/4$ in $(B_\ell^{(2)})^2$. As $d > 0$, we have $(3-2\lambda)/4 < 1 - \frac{\lambda}{2} + \frac{1}{4}(d-1)$, which implies

$$ \text{dens } Y_1 < \text{dens } X + (d-1) \frac{1}{2 \times 2}. $$

Thus, we have the $d$-small self intersection condition (Definition 3.6). By the multi-dimensional intersection formula, a.a.s.

$$ X_\ell \cap R_\ell^{(2)} \neq \emptyset. \qquad \blacksquare $$

### 4.3. Every $(m-1)$-generated subgroup is free

Fix the set of $m$ generators $X = \{x_1, \dots, x_m\}$. Recall that $B_\ell$ is the set of $(2m-1)^{\ell+o(\ell)}$ cyclically reduced words on $X^\pm = \{x_1^\pm, \dots, x_m^\pm\}$ of length at most $\ell$. The few relator model of random groups is constructed as follows: fix a number $k \in \mathbb{N}$ and let

$$ G_\ell = \langle x_1, \dots, x_m \mid r_1, \dots, r_k \rangle, $$
where $R_\ell = \{r_1, \dots, r_k\}$ is a random subset of $B_\ell$ given by the uniform probability on all subsets of $B_\ell$ with cardinality $k$.

The sequence $(G_\ell)_{\ell \in \mathbb{N}}$ is called a *sequence of random groups with $k$ relators*. As $k$ is independent of $\ell$, the sequence $(G_\ell)$ is a sequence of random groups with density $d = 0$. By Proposition 4.3, a.a.s. $G_\ell$ satisfies $C'(\lambda)$ for arbitrary small $\lambda > 0$.

In [5], Arzhantseva and Ol'shanskii proved the following result:

**Theorem 4.4** (Arzhantseva–Ol'shanskii [5, Theorem 1]). Let $(G_\ell)$ be a sequence of random groups with $k$ relators. Then a.a.s. every $(m-1)$-generated subgroup of $G_\ell$ is free.

Combining the intersection formula and their arguments, we prove the following theorem.

**Theorem 4.5.** Let $(G_\ell(m, d))$ be a sequence of random groups with density $0 \le d < 1/(120m^2 \ln(2m))$. Then a.a.s. every $(m-1)$-generated subgroup of $G_\ell(m, d)$ is free.

Let us recall the definition of “$\mu$-readable words” in [5, Section 2].

**Definition 4.6** ([5, Section 2]). Let $0 < \mu \le 1$. A cyclically reduced word $w$ of length $\ell$ on $X^\pm$ is $\mu$-readable if there exists a graph $\Gamma$ marked by $X^\pm$ with the following properties:

(a) the number of edges of $\Gamma$ is less than $\mu\ell$;

(b) the rank of $\Gamma$ is at most $m-1$;

(c) the word $w$ can be read along some path of $\Gamma$.

Note that the condition (b) is essential, because every word on $X^\pm$ can be read along the wedge of $m$ circles of length 1 marked by $x_1, \dots, x_m$, respectively.

Let $M_\ell^\mu$ be the set of words $r \in B_\ell$ having a cyclic sub-word $w < r$ such that $|w| \ge \frac{1}{2}|r|$ and $w$ is $\mu$-readable. We admit the following two lemmas in [5].

**Lemma 4.7** ([5, Lemma 4]). If $\mu < \log_{2m}(1 + 1/(4m-4))$, then there exists a constant $C(\mu, m)$ such that

$$|M_{\ell}^{\mu}| \le C(\mu, m) \ell^2 \left(2m - \frac{5}{4}\right)^{\ell}.$$

Recall that $|B_\ell| = (2m-1)^{\ell+O(1)}$, so $(M_\ell^\mu)$ is a densable sequence of subsets of $(B_\ell)$ with density $\log_{2m-1}(2m-5/4)$.

**Lemma 4.8** ([5, Section 4]). Let $G = \langle X|R \rangle$ be a group presentation where $X = \{x_1, \dots, x_m\}$ and $R$ is a subset of $B_\ell$. Suppose that

$$\mu < \log_{2m} \left(1 + \frac{1}{4m - 4}\right) \quad \text{and} \quad \lambda \le \frac{\mu}{15m + 3\mu}.$$
where $R_\ell = \{r_1, \dots, r_k\}$ is a random subset of $B_\ell$ given by the uniform probability on all subsets of $B_\ell$ with cardinality $k$.

The sequence $(G_\ell)_{\ell \in \mathbb{N}}$ is called a *sequence of random groups with $k$ relators*. As $k$ is independent of $\ell$, the sequence $(G_\ell)$ is a sequence of random groups with density $d = 0$. By Proposition 4.3, a.a.s. $G_\ell$ satisfies $C'(\lambda)$ for arbitrary small $\lambda > 0$.

In [5], Arzhantseva and Ol'shanskii proved the following result:

**Theorem 4.4** (Arzhantseva–Ol'shanskii [5, Theorem 1]). Let $(G_\ell)$ be a sequence of random groups with $k$ relators. Then a.a.s. every $(m-1)$-generated subgroup of $G_\ell$ is free.

Combining the intersection formula and their arguments, we prove the following theorem.

**Theorem 4.5.** Let $(G_\ell(m, d))$ be a sequence of random groups with density $0 \le d < 1/(120m^2 \ln(2m))$. Then a.a.s. every $(m-1)$-generated subgroup of $G_\ell(m, d)$ is free.

Let us recall the definition of “$\mu$-readable words” in [5, Section 2].

**Definition 4.6** ([5, Section 2]). Let $0 < \mu \le 1$. A cyclically reduced word $w$ of length $\ell$ on $X^\pm$ is $\mu$-readable if there exists a graph $\Gamma$ marked by $X^\pm$ with the following properties:

(a) the number of edges of $\Gamma$ is less than $\mu\ell$;

(b) the rank of $\Gamma$ is at most $m-1$;

(c) the word $w$ can be read along some path of $\Gamma$.

Note that the condition (b) is essential, because every word on $X^\pm$ can be read along the wedge of $m$ circles of length 1 marked by $x_1, \dots, x_m$, respectively.

Let $M_\ell^\mu$ be the set of words $r \in B_\ell$ having a cyclic sub-word $w < r$ such that $|w| \ge \frac{1}{2}|r|$ and $w$ is $\mu$-readable. We admit the following two lemmas in [5].

**Lemma 4.7** ([5, Lemma 4]). If $\mu < \log_{2m}(1 + 1/(4m-4))$, then there exists a constant $C(\mu, m)$ such that

$$|M_{\ell}^{\mu}| \le C(\mu, m) \ell^2 \left(2m - \frac{5}{4}\right)^{\ell}.$$

Recall that $|B_\ell| = (2m-1)^{\ell+O(1)}$, so $(M_\ell^\mu)$ is a densable sequence of subsets of $(B_\ell)$ with density $\log_{2m-1}(2m-5/4)$.

**Lemma 4.8** ([5, Section 4]). Let $G = \langle X|R \rangle$ be a group presentation where $X = \{x_1, \dots, x_m\}$ and $R$ is a subset of $B_\ell$. Suppose that

$$\mu < \log_{2m} \left(1 + \frac{1}{4m - 4}\right) \quad \text{and} \quad \lambda \le \frac{\mu}{15m + 3\mu}.$$
If $R$ does not intersect $M_{\ell}^{\mu}$, has no true powers, and satisfies $C'(\lambda)$, then every
$(m-1)$-generated subgroup of $G$ is free.
$\blacksquare$

**Proof of Theorem 4.5.** We look for a density $d(m) \le 1/2$ such that for any $d < d(m)$ a.a.s. the random group $G_{\ell}(m, d) = \langle X | R_{\ell} \rangle$ satisfies the conditions of Lemma 4.8 with

$$
\mu = \log_{2m} \left( 1 + \frac{1}{4m-4} \right) - \varepsilon \quad \text{and} \quad \lambda = \frac{\mu}{15m + 3\mu}
$$

with an arbitrary small $\varepsilon > 0$.

The set of true powers in $B_\ell$ is with density $1/2$. By the intersection formula (Corollary 3.8), because $d < 1/2$, a.a.s. $R_\ell$ has no true powers. By Lemma 4.7 and the intersection formula, we need

$$
d(m) < 1 - \text{dens}(M_{\ell}^{\mu}) < 1 - \log_{2m-1} \left( 2m - \frac{5}{4} \right),
$$

so that a.a.s. $R_\ell$ does not intersect $M_\ell^\mu$ by the intersection formula.

At the end we need a.a.s. $R_\ell$ satisfies $C'(\lambda)$ with

$$
\lambda = \frac{\log_{2m}\left(1 + \frac{1}{4m-4}\right) - \varepsilon}{15m + 3\log_{2m}\left(1 + \frac{1}{4m-4}\right) - 3\varepsilon}.
$$

By Theorem 4.3, we need $d(m) < \lambda/2$. Note that this inequality implies the previous one. For $\varepsilon$ small enough, we have $\lambda > 1/(60m^2 \ln(2m))$. It is enough to take

$$
d(m) = \frac{1}{120m^2 \ln(2m)}. \qquad \blacksquare
$$

**Acknowledgments.** I would like to thank my supervisor, Thomas Delzant, for his guidance and interesting discussions on the subject, especially for his patience with me while completing this article. I would also like to thank the referee for his/her thorough review of the manuscript and highly appreciate the comments and suggestions, which significantly contributed to improving the quality of this work.

**References**

[1] S. Antoniuk, T. Łuczak, and J. Świątkowski, Random triangular groups at density 1/3.
*Compos. Math.* **151** (2015), no. 1, 167–178 Zbl **1334.20076** MR **3305311**

[2] G. N. Arzhantseva, On groups in which subgroups with a fixed number of generators are free. *Fundam. Prikl. Mat.* **3** (1997), no. 3, 675–683 Zbl **0929.20025** MR **1794135**

[3] G. N. Arzhantseva, Generic properties of finitely presented groups and Howson's theorem.
*Comm. Algebra* **26** (1998), no. 11, 3783–3792 Zbl **0911.20027** MR **1647075**
If $R$ does not intersect $M_{\ell}^{\mu}$, has no true powers, and satisfies $C'(\lambda)$, then every
$(m-1)$-generated subgroup of $G$ is free. ■

*Proof of Theorem 4.5.* We look for a density $d(m) \le 1/2$ such that for any $d < d(m)$ a.a.s. the random group $G_{\ell}(m, d) = \langle X | R_{\ell} \rangle$ satisfies the conditions of Lemma 4.8 with

$$
\mu = \log_{2m} \left( 1 + \frac{1}{4m-4} \right) - \varepsilon \quad \text{and} \quad \lambda = \frac{\mu}{15m + 3\mu}
$$

with an arbitrary small $\varepsilon > 0$.

The set of true powers in $B_\ell$ is with density $1/2$. By the intersection formula (Corollary 3.8), because $d < 1/2$, a.a.s. $R_\ell$ has no true powers. By Lemma 4.7 and the intersection formula, we need

$$
d(m) < 1 - \operatorname{dens}(M_{\ell}^{\mu}) < 1 - \log_{2m-1} \left( 2m - \frac{5}{4} \right),
$$

so that a.a.s. $R_\ell$ does not intersect $M_\ell^\mu$ by the intersection formula.

At the end we need a.a.s. $R_\ell$ satisfies $C'(\lambda)$ with

$$
\lambda = \frac{\log_{2m}\left(1 + \frac{1}{4m-4}\right) - \varepsilon}{15m + 3\log_{2m}\left(1 + \frac{1}{4m-4}\right) - 3\varepsilon}.
$$

By Theorem 4.3, we need $d(m) < \lambda/2$. Note that this inequality implies the previous one. For $\varepsilon$ small enough, we have $\lambda > 1/(60m^2 \ln(2m))$. It is enough to take

$$
d(m) = \frac{1}{120m^2 \ln(2m)}. \quad \blacksquare
$$

**Acknowledgments.** I would like to thank my supervisor, Thomas Delzant, for his guidance and interesting discussions on the subject, especially for his patience with me while completing this article. I would also like to thank the referee for his/her thorough review of the manuscript and highly appreciate the comments and suggestions, which significantly contributed to improving the quality of this work.

**References**

[1] S. Antoniuk, T. Łuczak, and J. Świątkowski, Random triangular groups at density 1/3.
*Compos. Math.* **151** (2015), no. 1, 167–178 Zbl **1334.20076** MR **3305311**

[2] G. N. Arzhantseva, On groups in which subgroups with a fixed number of generators are free. *Fundam. Prikl. Mat.* **3** (1997), no. 3, 675–683 Zbl **0929.20025** MR **1794135**

[3] G. N. Arzhantseva, Generic properties of finitely presented groups and Howson's theorem.
*Comm. Algebra* **26** (1998), no. 11, 3783–3792 Zbl **0911.20027** MR **1647075**
[4] G. N. Arzhantseva, A property of subgroups of infinite index in a free group. Proc. Amer. Math. Soc. 128 (2000), no. 11, 3205-3210 Zbl 0976.20014 MR 1694447

[5] G. N. Arzhantseva and A. Y. Ol'shanskiǐ, The class of groups all of whose subgroups with lesser number of generators are free is generic. Mat. Zametki 59 (1996), no. 4, 489-496, 638 Zbl 0877.20021 MR 1445193

[6] F. Bassino, C. Nicaud, and P. Weil, Random presentations and random subgroups: A survey. In *Complexity and Randomness in Group Theory*, pp. 45-76, GAGTA 1, de Gruyter, Berlin, 2020 Zbl 7205680

[7] É. Ghys, Groupes aléatoires (d'après Misha Gromov, . . . ). *Astérisque* (2004), no. 294, 173-204 Zbl 1134.20306 MR 2111644

[8] M. Gromov, Hyperbolic groups. In *Essays in group theory*, pp. 75-263, Math. Sci. Res. Inst. Publ. 8, Springer, New York, 1987 Zbl 0634.20015 MR 919829

[9] M. Gromov, Asymptotic invariants of infinite groups. In *Geometric group theory, Vol. 2* (Sussex, 1991), pp. 269-282, London Math. Soc. Lecture Note Ser. 182, Cambridge Univ. Press, Cambridge, 1993 MR 1253544

[10] V. S. Guba, Conditions under which 2-generated subgroups in small cancellation groups are free. *Izv. Vyssh. Uchebn. Zaved. Mat.* **87** (1986), no. 7, 12-19 Zbl 0614.20022
MR 867603

[11] I. Kapovich and P. Schupp, Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups. Math. Ann. 331 (2005), no. 1, 1-19
Zbl 1080.20029 MR 2107437

[12] I. Kapovich and P. Schupp, On group-theoretic models of randomness and genericity. Groups Geom. Dyn. 2 (2008), no. 3, 383-404 Zbl 1239.20047 MR 2415305

[13] R. C. Lyndon and P. E. Schupp, *Combinatorial group theory*. Ergeb. Math. Grenzgeb. (3) 89, Springer, Berlin-New York, 1977 Zbl 0368.20023 MR 0577064

[14] Y. Ollivier, Critical densities for random quotients of hyperbolic groups. C. R. Math. Acad. Sci. Paris 336 (2003), no. 5, 391-394 Zbl 1050.20048 MR 1979351

[15] Y. Ollivier, Sharp phase transition theorems for hyperbolicity of random groups. *Geom. Funct. Anal.* **14** (2004), no. 3, 595-679 Zbl 1064.20045 MR 2100673

[16] Y. Ollivier, *A January 2005 invitation to random groups*. Ensaios Mat. 10, Soc. Brasil. Mat., Rio de Janeiro, 2005 Zbl 1163.20311 MR 2205306

[17] Y. Ollivier, Some small cancellation properties of random groups. *Internat. J. Algebra Comput.* **17** (2007), no. 1, 37-51 Zbl 1173.20025 MR 2300404

[18] Y. Ollivier and D. T. Wise, Cubulating random groups at density less than 1/6. *Trans. Amer. Math. Soc.* **363** (2011), no. 9, 4701-4733 Zbl 1277.20048 MR 2806688

[19] A. Żuk, Property (T) and Kazhdan constants for discrete groups. *Geom. Funct. Anal.* **13** (2003), no. 3, 643-670 Zbl 1036.22004 MR 1995802

Received 22 April 2021; revised 13 December 2021.

Tsung-Hsuan Tsai

Institut de Recherche Mathématique Avancée, UFR de Mathématiques (Office 105),
7 rue René Descartes, 67000 Strasbourg, France; tsung-hsuan.tsai@math.unistra.fr
[4] G. N. Arzhantseva, A property of subgroups of infinite index in a free group. Proc. Amer. Math. Soc. 128 (2000), no. 11, 3205-3210 Zbl 0976.20014 MR 1694447

[5] G. N. Arzhantseva and A. Y. Ol'shanskiǐ, The class of groups all of whose subgroups with lesser number of generators are free is generic. Mat. Zametki 59 (1996), no. 4, 489-496, 638 Zbl 0877.20021 MR 1445193

[6] F. Bassino, C. Nicaud, and P. Weil, Random presentations and random subgroups: A survey. In *Complexity and Randomness in Group Theory*, pp. 45-76, GAGTA 1, de Gruyter, Berlin, 2020 Zbl 7205680

[7] É. Ghys, Groupes aléatoires (d'après Misha Gromov, . . . ). *Astérisque* (2004), no. 294, 173-204 Zbl 1134.20306 MR 2111644

[8] M. Gromov, Hyperbolic groups. In *Essays in group theory*, pp. 75-263, Math. Sci. Res. Inst. Publ. 8, Springer, New York, 1987 Zbl 0634.20015 MR 919829

[9] M. Gromov, Asymptotic invariants of infinite groups. In *Geometric group theory, Vol. 2* (Sussex, 1991), pp. 269-282, London Math. Soc. Lecture Note Ser. 182, Cambridge Univ. Press, Cambridge, 1993 MR 1253544

[10] V. S. Guba, Conditions under which 2-generated subgroups in small cancellation groups are free. *Izv. Vyssh. Uchebn. Zaved. Mat.* **87** (1986), no. 7, 12-19 Zbl 0614.20022
MR 867603

[11] I. Kapovich and P. Schupp, Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups. Math. Ann. 331 (2005), no. 1, 1-19
Zbl 1080.20029 MR 2107437

[12] I. Kapovich and P. Schupp, On group-theoretic models of randomness and genericity. Groups Geom. Dyn. 2 (2008), no. 3, 383-404 Zbl 1239.20047 MR 2415305

[13] R. C. Lyndon and P. E. Schupp, *Combinatorial group theory*. Ergeb. Math. Grenzgeb. (3) 89, Springer, Berlin-New York, 1977 Zbl 0368.20023 MR 0577064

[14] Y. Ollivier, Critical densities for random quotients of hyperbolic groups. C. R. Math. Acad. Sci. Paris 336 (2003), no. 5, 391-394 Zbl 1050.20048 MR 1979351

[15] Y. Ollivier, Sharp phase transition theorems for hyperbolicity of random groups. *Geom. Funct. Anal.* **14** (2004), no. 3, 595-679 Zbl 1064.20045 MR 2100673

[16] Y. Ollivier, *A January 2005 invitation to random groups*. Ensaios Mat. 10, Soc. Brasil. Mat., Rio de Janeiro, 2005 Zbl 1163.20311 MR 2205306

[17] Y. Ollivier, Some small cancellation properties of random groups. *Internat. J. Algebra Comput.* **17** (2007), no. 1, 37-51 Zbl 1173.20025 MR 2300404

[18] Y. Ollivier and D. T. Wise, Cubulating random groups at density less than 1/6. *Trans. Amer. Math. Soc.* **363** (2011), no. 9, 4701-4733 Zbl 1277.20048 MR 2806688

[19] A. Żuk, Property (T) and Kazhdan constants for discrete groups. *Geom. Funct. Anal.* **13** (2003), no. 3, 643-670 Zbl 1036.22004 MR 1995802

Received 22 April 2021; revised 13 December 2021.

Tsung-Hsuan Tsai

Institut de Recherche Mathématique Avancée, UFR de Mathématiques (Office 105),
7 rue René Descartes, 67000 Strasbourg, France; tsung-hsuan.tsai@math.unistra.fr