1. Introduction
In this paper we study a model for random groups constructed using Erdős–Rényi random graphs. Using combinatorial and probabilistic techniques, we are able to analyze the geometric properties of a typical outcome of our random group model, establishing thresholds for the presence of Morse subgroups and showing that there are many examples of non-relatively hyperbolic groups which exhibit coarse cubical rigidity. The first examples of non-relatively hyperbolic groups with coarse cubical rigidity were recently constructed in [Reference Fioravanti, Levcovitz and Sageev21]; in Corollary 1 we show that this phenomenon is in fact typical rather than exotic. This exemplifies the way in which studying random groups is a powerful tool for generating interesting examples in geometric group theory. We expect this approach will be fruitful in the study of further properties, and we hope this paper will inspire more probabilists and geometric group theorists to investigate models for random groups.
The right-angled Coxeter group (RACG)
$W_{\Gamma}$
with presentation graph
$\Gamma=(V,E)$
is the group with generators V and relations
$a^2=\mathrm{id}$
and
$ab=ba$
for all
$a\in V$
and
$ab\in E$
. Coxeter groups are an abstract generalization of the notion of reflection groups in Euclidean space that was introduced by the geometer Coxeter in the 1930s. Like reflections, generators in a Coxeter group have order 2. If the angle between two hyperplanes is
$\alpha$
, then the product of their associated reflections yields a rotation through an angle of
$2\alpha$
; if
$\alpha=\pi/k$
then this has finite order k, otherwise the order is infinite. Thus, RACGs are an abstract generalization of reflection groups generated by hyperplanes whose pairwise angles are either
$\pi/2$
(hence the name ‘right-angled’) or cannot be expressed as a rational multiple of
$\pi$
.
We study a RACG
$W_{\Gamma}$
whose presentation graph
$\Gamma$
is an Erdős–Rényi random graph
$\mathcal{G}_{n,p}$
. We recall here that for a sequence of edge probabilities
$p=p(n)\in[0,1]$
, the graph
$\mathcal{G}_{n,p}$
is obtained by taking as a vertex set
$[n]\;:\!=\;\{1,2, \ldots n\}$
and including each of the
$\binom{n}{2}$
possible edges with probability p, independently at random. We write
$\Gamma\sim\mathcal{G}_{n,p}$
to denote the fact that
$\Gamma$
is a random graph with the same distribution as
$\mathcal{G}_{n,p}$
.
Given such a random graph
$\Gamma\sim \mathcal{G}_{n,p}$
we can then define a random RACG
$W_{\Gamma}$
, thereby obtaining an interesting model for a random right-angled Coxeter group. Random group models have been extensively studied since [Reference Gromov23] in the 1990s, while the geometry of random right-angled Coxeter groups was first considered in [Reference Charney and Farber12] in 2012, and has since received significant attention; see, e.g., [Reference Behrstock, Çiçeksiz and Falgas-Ravry3, Reference Behrstock, Falgas-Ravry, Hagen and Susse6, Reference Behrstock, Hagen and Sisto8].
One approach to studying the geometry of a RACG is to investigate the structure of its flats (isometrically embedded copies of
$\mathbb R^{n}$
). In general, a finitely generated group does not have a canonical generating set, so we typically consider quasi-isometric invariant features of the group, as the word metric is canonical up to quasi-isometry. On the other hand, RACGs have a natural metric given by the generators in the defining presentation. This metric is especially nice because it is the one-skeleton of a CAT(0) cube complex associated with the RACG known as the Davis complex. (The Davis complex is a CAT(0) cube complex associated with W on which W acts isometrically as a reflection group; see [Reference Davis16] for a thorough treatment.) Using the fact that induced 4-cycles in
$\Gamma$
give rise to two-dimensional flats in the Davis complex, [Reference Behrstock, Hagen and Sisto8, Reference Dani and Thomas15] showed that important geometric properties of the group
$W_{\Gamma}$
can be understood by studying an auxiliary graph encoding the induced 4-cycles of
$\Gamma$
. The square graph of
$\Gamma$
is the graph
$S(\Gamma)$
whose vertices correspond to the induced 4-cycles (a.k.a. squares) of
$\Gamma$
, and with edges corresponding to pairs of induced 4-cycles having a non-edge in common (we refer to these non-edges as diagonals of the square).
In probabilistic and combinatorial arguments, it is often convenient to work with a slightly different but closely related auxiliary graph (which, confusingly, is also referred to as ‘the square graph’ in the literature), denoted by
$T_{1}(\Gamma)$
. These two graphs encode essentially the same information – indeed,
$S(\Gamma)$
is the line graph of
$T_{1}(\Gamma)$
; both
$S(\Gamma)$
and
$T_{1}(\Gamma)$
are formally defined in Section 2. Note that if
$\Gamma\sim \mathcal{G}_{n,p}$
, then the associated square graph (whether
$S(\Gamma)$
or
$T_1(\Gamma)$
) is also a random graph, but with a starkly different and more complex distribution featuring in particular some significant dependencies between the edges. The study of the properties of
$S(\Gamma)$
and
$T_1(\Gamma)$
when
$\Gamma$
is a random graph is known as square percolation, by analogy with the clique percolation model [Reference Derényi, Palla and Vicsek18] introduced in 2005, which has received extensive attention from researchers in network science.
Studying the square graphs associated with a random graph
$\Gamma \sim \mathcal{G}_{n,p}$
is interesting from both probabilistic and geometric group theory perspectives. From a probabilistic perspective, these square graphs arising from random graphs present novel challenges (see the extensive discussion in Section 2.3 on the difficulties arising from their study, in particular with regards to non-monotonicity), while from a group-theoretic perspective they are a source of interesting examples. The specific question of the connectivity threshold of
$S(\Gamma)$
when
$\Gamma \sim \mathcal{G}_{n,p}$
was raised in [Reference Susse28] on the existence of Morse subgroups in a random RACG. To state those results and conjecture, we must have recourse to a standard probabilistic notion: we say that an event holds asymptotically almost surely (henceforth abbreviated to a.a.s.) if, informally, it holds with probability
$1-o(1)$
; this notion as well as our notation for relative asymptotic growth (
$o, \omega, O, \Omega, \ll, \theta $
) are formally defined in Section 2.2.
Susse proved that for edge probabilities
$p=p(n)$
satisfying
$n^{-1}\ll p \leq (1-\varepsilon)\sqrt{(\!\log n)/n}$
, the square graph
$S(\Gamma)$
is a.a.s. not connected [Reference Susse28, Corollary 3.8]; note that the
$n^{-1}\ll p$
hypothesis is needed to ensure a.a.s. that
$\Gamma$
has at least two induced squares, and thus that
$S(\Gamma)$
has at least two vertices. [Reference Susse28, Conjecture 3.9] suggested that for p above this range
$S(\Gamma)$
is a.a.s. connected. Our main result fully resolves Susse’s conjecture and determines the threshold for connectivity of the graphs
$T_1(\Gamma)$
and
$S(\Gamma)$
.
Theorem 1. For every
$\varepsilon, \delta>0$
fixed, there exist constants
$C, n_0>0$
such that, for every
$n\geq n_0$
, setting
$\Gamma\sim\mathcal{G}_{n,p}$
, we have:
-
(i) if
$Cn^{-1} \leq p \leq (1-\varepsilon)\sqrt{({\log n})/{n}}$
, then
$\mathbb{P}(S(\Gamma) \textit{ is connected})<\delta $
; -
(ii) if
$(1+\varepsilon)\sqrt{({\log n})/{n}}\leq p$
, then
$\mathbb{P}(S(\Gamma) \textit{ is connected})>1-\delta $
; -
(iii) if
$p \leq \sqrt{2-\varepsilon}\sqrt{({\log n})/{n}}$
, then
$\mathbb{P}(T_1(\Gamma) \textit{ is connected})<\delta $
; -
(iv) if
$\sqrt{2+\varepsilon}\sqrt{({\log n})/{n}}\leq p$
, then
$\mathbb{P}(T_1(\Gamma) \textit{ is connected})>1-\delta$
.
Remark 1. The thresholds for connectivity of the graphs
$S(\Gamma)$
and
$T_1(\Gamma)$
differ. Indeed, Theorem 1 implies that for p in the range
$[\sqrt{1+\varepsilon}\sqrt{(\!\log n)/n},\sqrt{2-\varepsilon}\sqrt{(\!\log n)/n}]$
,
$T_1(\Gamma)$
consists a.a.s. of a unique non-trivial component together with a number of isolated vertices, corresponding to non-edges of
$\Gamma$
that do not lie in any induced square of
$\Gamma$
. So for p in this range, a.a.s.
$T_1(\Gamma)$
is not connected while its line graph
$S(\Gamma)$
is connected. Further, the lower bound on part (i) is necessary and the best possible, just as in the earlier results in [Reference Susse28], since
$S(\Gamma)$
is connected whenever
$\Gamma$
contains at most one square.
Remark 2. At first blush, the obstruction to connectivity in the random graphs
$S(\Gamma)$
and
$T_1(\Gamma)$
are ‘the obvious ones’ from a random graph-theoretic perspective as they correspond to the presence of structures corresponding to isolated vertices. In this case,
$p\approx \sqrt{2 (\!\log n)/n}$
is the threshold at which you expect every pair of vertices (in particular any non-edge) in
$\Gamma$
to have at least two common neighbors in
$\Gamma$
(and in particular a decent chance of being contained in a 4-cycle).
However, in stark contrast with the situation for the Erdős–Rényi random graph model, the main challenge in proving Theorem 1 is not proving that there are no small components, but rather in showing the uniqueness of the large component. Indeed, in Proposition 3 we provide surprising examples showing it is possible for two distinct components of
$S(\Gamma)$
or
$T_1(\Gamma)$
to be supported on exactly the same set of vertices in
$V(\Gamma)$
. This presents a non-trivial obstacle in establishing Theorem 1, and most of the work in the present paper goes to showing that while it is possible for two (or more) large components of our random graphs to coexist inside the same space, it is extremely rare. Indeed, we show in Theorem 3 that some time before the connectivity threshold for
$S(\Gamma)$
, any two square components that are reasonably spreadly out (in the sense of containing squares that together cover at least about
$\log(n)^{2}$
vertices) must connect up. Intuitively, square components that are too spread out have too many opportunities to merge to fail to do so, even if that would be theoretically possible.
Theorem 1 has some interesting implications for the geometric properties of a random RACG, which we now discuss. For further background on the topics discussed below, we refer the reader to [Reference Davis16], a treatise on RACGs, and [Reference Dani13], a recent survey on active areas of research on these groups.
If we drop from the presentation of a RACG the requirement that each generator is of order two, we obtain the presentation for a right-angled Artin group (RAAG). These groups interpolate between free groups (RAAGs associated with edgeless graphs) and free abelian groups (RAAGs associated with complete graphs). It was proved in [Reference Davis and Januszkiewicz17] that every right-angled Artin group is a finite-index subgroup of some RACG, but it turns out that not every RACG is a finite-index subgroup of some right-angled Artin group. Two groups are said to be virtually isomorphic when a finite-index subgroup of one is isomorphic to a finite-index subgroup of the other. Several interesting papers on determining which RACGs are virtually RAAGs have been written recently, including [Reference Cashen and Edletzberger11, Reference Dani and Levcovitz14].
Divergence functions are a key geometric object for the study of geodesic spaces and play an important role in the study of RACGs. Roughly speaking, a divergence function measures the length of a shortest path between pairs of points at distance r apart in a space when forced to avoid a ball of radius
$\alpha r$
around a third point, for some fixed
$\alpha\in (0,1)$
, as a function of r. Its growth rate (linear, quadratic, …) has important implications for the geometry of the space. See [Reference Behrstock and Drutu4, Reference Drutu, Mozes and Sapir19] for a formal definition of divergence and its applications.
It is known from [Reference Behrstock and Charney2] that any RAAG has exactly one of the following three distinct properties: it has quadratic divergence, or it is free abelian (and thus has linear divergence), or it splits as a free product (and thus has at least exponential divergence). By [Reference Behrstock, Hagen and Sisto8, Theorem 3.2] and [Reference Behrstock, Hagen and Sisto8, Theorem V], a RACG is a.a.s. either an abelian group or quasi-isometric to a group that splits as a free product if and only if
$p=p(n)$
goes very quickly to 0 or 1 (see [Reference Behrstock, Hagen and Sisto8] for the precise bounds). Hence, for
$p=p(n)$
bounded away from 0 and 1, a random RACG is a.a.s. quasi-isometric (or, a fortiori, virtually) a RAAG only if it a.a.s. has quadratic divergence, which by [Reference Behrstock, Falgas-Ravry and Susse7, Theorem 1.6] occurs for p in the range
$(\sqrt{\sqrt{6}-2}+\varepsilon) / \sqrt{n} \leq p(n) \leq 1-(1+\varepsilon)(\!\log{n}) / n$
. Since both RAAGs and RACGs act geometrically on CAT(0) cube complexes with factor systems, they are hierarchically hyperbolic spaces (see [Reference Behrstock, Hagen and Sisto9, Proposition B and Theorem G]); it then follows from [Reference Behrstock, Hagen and Sisto10, Corollary E] that the structure of their quasiflats can be described in terms of certain standard flats in their CAT(0) structure. In the case of RAAGs, we can deduce that they have quadratic divergence by verifying the connectivity associated with the coarse intersection pattern of the cosets of their standard
$\mathbb Z \times \mathbb Z$
subgroups [Reference Behrstock, Drutu and Mosher5, Theorem 10.5]. By pulling back the subgroups associated with squares in
$\Gamma$
to the RAAG, it follows that any RACG which is quasi-isometric to a RAAG with quadratic divergence would inherit this connectivity structure and thus have
$S(\Gamma)$
connected.
[Reference Susse28, Corollary 3.7] proved (see Theorem 1(i)) that for edge probabilities
$p=p(n)$
satisfying
$ 1/n\ll p<(1-\varepsilon)\sqrt{(\!\log n)/n}$
the random RACG cannot be a.a.s. quasi-isometric to a RAAG because of the presence of certain Morse cycles; one way to think about why this presents an obstacle to being virtually a RAAG is that in that range
$S(\Gamma)$
is a.a.s. not connected. By contrast, it is an immediate consequence of our Theorem 1(ii) that the same obstruction does not hold when
$(1+\varepsilon)\sqrt{(\!\log n)/n}\leq p$
. Accordingly, the following remains a very interesting open question.
Question 1.
Given
$p=p(n)$
satisfying
$(1+\varepsilon)\sqrt{(\!\log n)/n} \leq p \leq 1-(1+\varepsilon)(\!\log n)/n$
and
$\Gamma\sim\mathcal{G}_{n,p}$
, is the random right-angled Coxeter group
$W_{\Gamma}$
a.a.s. virtually a RAAG? If not, is it at least a.a.s. quasi-isometric to one?
A powerful method in geometric group theory involves the study of actions of groups on non-positively curved spaces. Such actions allow us to deduce important topological, algebraic, and dynamical results about the group. A right-angled Coxeter group acts on its Davis complex, which is a cube complex satisfying the CAT(0) condition for non-positive curvature; see [Reference Davis16, Reference Gromov23]. Since the action on the Davis complex is cocompact, it can be used to associate a cocompact cubulation to any given right-angled Coxeter group.
[Reference Fioravanti, Levcovitz and Sageev21] recently established a useful framework for determining the possible cubulations of a given group, phrased in terms of medians, whose definition we now give. Given a triple of vertices
$x_1,x_2,x_3$
in the 1-skeleton of a CAT(0) cube complex, there exists a unique point
$m=m(x_1, x_2,x_3)$
in the 1-skeleton that lies on the intersection of the geodesics between
$x_i$
and
$x_j$
,
$1\le i < j \le 3$
. we can thus equip every CAT(0) cube complex with a median operator
$(x_1,x_2,x_3)\mapsto m(x_1, x_2, x_3)$
sending a triple of elements in the 1-skeleton to their median.
Given a group acting cocompactly on a cube complex, [Reference Fioravanti, Levcovitz and Sageev21] defines the cubical coarse median to be the pull-back of the median operator via any equivariant quasi-isometry. Two cubulations induce the same coarse median structure if their cubical coarse medians are a uniformly bounded distance apart. This provides a definition of when two cocompact cubulations should be considered equivalent. A group has coarse cubical rigidity if all its cubulations induce the same coarse median structure. In [Reference Fioravanti, Levcovitz and Sageev21] it is proved that for each
$n\geq 2$
the group
$\mathbb{Z}^{n}$
has countably many distinct cubical coarse medians, and thus in particular it does not have coarse cubical rigidity.
Using the methods from the proof of Theorem 1(ii) together with these recent results, we obtain the following result on the cubical coarse median structure of the random RACG.
Theorem 2 (Coarse cubical rigidity.) Let
$\varepsilon>0$
be fixed and
$p=p(n)$
satisfy
\begin{equation*} (1+\varepsilon)\sqrt{\frac{\log n}{n}}\leq p\leq 1-(1+\varepsilon)\frac{\log n}{n}. \end{equation*}
Then a.a.s. the right-angled Coxeter group
$W_{\Gamma}$
with
$\Gamma\sim \mathcal{G}_{n,p}$
has a unique cubical coarse median structure.
We note that some upper bound on
$p=p(n)$
in Theorem 2 is necessary. Indeed, for
$1-p$
of order
$n^{-2}$
the right-angled Coxeter group
$W_{\Gamma}$
with
$\Gamma\sim \mathcal{G}_{n,p}$
is a.a.s. virtually abelian, as shown in [Reference Behrstock, Hagen and Sisto8, Theorem V]. For these values of p, it thus follows that
$W_{\Gamma}$
is either a finite group or virtually infinite cyclic (both of which have unique coarse median structures), or it has more than one distinct cubical coarse median structures by [Reference Fioravanti, Levcovitz and Sageev21, Proposition 3.11], and all three alternatives occur with probability bounded away from 0 by [Reference Behrstock, Hagen and Sisto8, Theorem V].
As for the lower bound on
$p=p(n)$
, [Reference Susse28, Corollary 3.8] implies that in the case
$n^{-1}\ll p\leq (1-\varepsilon)\sqrt{({\log n})/{n}}$
the square graph associated with
$\Gamma\sim\mathcal{G}_{n,p}$
will a.a.s. contain non-bonded induced squares (see Section 3.4 for a definition), which it was suggested should imply the existence of several distinct cubical coarse median structures (see the discussion after [Reference Fioravanti, Levcovitz and Sageev21, Corollary C]). If this speculation is correct, then this would indicate that both the lower bound and the upper bound on p(n) in Theorem 2 are optimal. For the lower bound, this would follow from [Reference Susse28], while for the upper bound we note that in any graph a pair of non-edges that together induce a square and that do not share a vertex with any other non-edge of the graph form a non-bonded square. For
$\varepsilon>0$
fixed and
$1-p\leq (1-\varepsilon)(\!\log n)/n$
, standard results in random graph theory imply the a.a.s. existence of such pairs of non-edges (and hence of non-bonded squares) in
$\Gamma\sim \mathcal{G}_{n,p}$
.
[Reference Fioravanti, Levcovitz and Sageev21] gave the first examples of non-hyperbolic groups with coarse cubical rigidity. Theorem 2, combined with [Reference Behrstock, Çiçeksiz and Falgas-Ravry3, Theorem 1.1], implies that coarse cubical rigidity is in fact very common among non-hyperbolic (indeed non-relatively hyperbolic) RACGs, as is seen in the following corollary which covers a wide range of edge probabilities p, including in particular
$p=\frac12$
.
Corollary 1. Let
$\varepsilon<0$
be fixed and
$p=p(n)$
satisfy
\begin{align*}\frac{\sqrt{\sqrt{6}-2}}{\sqrt{n}}\leq p \leq 1-(1+\varepsilon)\frac{\log n}{n}.\end{align*}
Then, a.a.s. the right-angled Coxeter group
$W_{\Gamma}$
with
$\Gamma\sim \mathcal{G}_{n,p}$
has a unique cubical coarse median structure and is neither hyperbolic nor relatively hyperbolic.
A number of questions concerning component evolution and diameter in the square graphs of random graphs were raised in [Reference Behrstock, Falgas-Ravry and Susse7, Section 7]. In Theorem 3 and Proposition 8, we shed light on several of those questions. For instance, as a key step in the proof of Theorem 1, we establish an a.a.s. upper bound on the size of the second-largest component in the auxiliary graph
$T_1(\Gamma)$
for p just above the threshold for the emergence of the giant square component. This is given by the following result, which resolves a question about component evolution for p in the corresponding range, and constitutes the main probabilistic result in the present paper.
Theorem 3. Let
$\Gamma\sim\mathcal{G}_{n,p}$
. Then there exists a constant
$C>0$
such that if
\[C\sqrt{\frac{\log \log n}{n}}\leq p(n) \leq 1-\omega(n^{-2}),\]
then a.a.s. there exists a unique giant component in
$T_1(\Gamma)$
of size
$\Omega((1-p)n^2)$
, with all other components having size
$O((({\log n})/({\log \log n}))^2)$
.
(The upper bound on p in Theorem 3 is needed to guarantee that a.a.s.
$T_1(\Gamma)$
has
$\Omega((1-p)n^2)$
vertices; for
$1-p$
of order
$n^{-2}$
, we can guarantee
$T_1(\Gamma)$
is a.a.s. connected but its order is a
$\mathrm{Binom}\big(\binom{n}{2}, 1-p\big)$
random variable which is zero with probability bounded away from 0.) We conjecture that already at the time of the emergence of a giant square component (which occurs at
$p\approx\sqrt{\sqrt{6}-2}/\sqrt{n}$
, as proved in [Reference Behrstock, Falgas-Ravry and Susse7]), the second-largest square component should have support of only polylogarithmic order.
Conjecture 1. Let
$\Gamma\sim \mathcal{G}_{n,p}$
, and let
$\varepsilon>0$
be fixed. Suppose
$p = p(n) \geq ({\sqrt{\sqrt{6}-2} +\varepsilon})/{\sqrt{n}}$
. Then there exists a constant
$C=C(\varepsilon)>0$
such that a.a.s. all connected components of
$T_1(\Gamma)$
except the largest one have size
$(\!\log n)^{C}$
.
We expect a new approach will be needed to resolve this conjecture, as it does not seem attainable using our current methods. More precisely, when p is of order
$1/\sqrt{n}$
our partition and vertex-sprinkling arguments are not strong enough to rule out the existence of connected components of
$T_1(\Gamma)$
having order polynomial in n but
$o(n^2)$
. To deal with these components, it is likely that we will need to argue instead that it is unlikely that two polynomially large square components can have significantly overlapping support – and thus to find quantitative arguments to bound the probability of seeing examples such as the ones constructed in Proposition 3 in a random graph. This, however, will require a more detailed combinatorial understanding of square components than is currently available.
1.1. Organization of the paper
In Section 2 we recall some background on graph theory, algebraic thickness, and a number of probabilistic tools we shall require for our arguments. In Section 3 we begin with an outline of the proof of Theorem 1. We then proceed to the existence of a unique giant component in square percolation (Section 3.2), the connectivity threshold for the random square graph (Section 3.3), and finally the application of our work to the geometry of the random RACG (Section 3.4). We end the paper in Section 4 with some concluding remarks and open questions related to our work that would be of interest for further exploration.
2. Preliminaries and definitions
2.1. Graph-theoretic notions and notation
We recall here some standard graph-theoretic notions and notation that we will use throughout the paper. We write
$[n]\;:\!=\;\{1,2, \ldots, n\}$
, and
$[m,n]\;:\!=\;\{m,m+1,\ldots,n\}$
for
$n,m\in \mathbb{Z}$
, and
$x_1x_2\ldots x_r$
to denote the r-set
$\{x_1, x_2, \ldots, x_r\}$
. Given a set S, we let
$S^{(r)}$
denote the collection of all subsets of S of size r. A graph is a pair
$\Gamma=(V,E)$
, where
$V=V(\Gamma)$
is a set of vertices and
$E=E(\Gamma)$
is a subset of
$V^{(2)}$
. All graphs considered in this paper are simple graphs, with no loops or multiple edges.
A subgraph of
$\Gamma$
is a graph
$\Gamma'$
with
$V(\Gamma')\subseteq V(\Gamma)$
and
$E(\Gamma')\subseteq E(\Gamma)$
. We say
$\Gamma'$
is the subgraph of
$\Gamma$
induced by a set of vertices S if
$\Gamma' =(S, S^{(2)}\cap E(\Gamma))$
, and denote this fact by writing
$\Gamma'=\Gamma[S]$
. The complement of
$\Gamma$
is the graph
$\overline{\Gamma}\;:\!=\;(V, V^{(2)}\setminus E)$
. The neighbourhood of a vertex x in
$\Gamma$
is the set
$N_{\Gamma}(x)\;:\!=\;\{y\in V(\Gamma)\colon xy \in E(\Gamma)\}$
.
A path of length
$\ell\geq 0$
in
$\Gamma$
is a sequence of distinct vertices
$v_0, v_1, \ldots, v_{\ell}$
with
$v_iv_{i+1}\in E(\Gamma)$
for all
$i\in [\ell-1]\cup\{0\}$
. The vertices
$v_0$
and
$v_{\ell}$
are called the endpoints of the path. Two vertices are said to be connected in
$\Gamma$
if they are the endpoints of some path of finite length. Being connected in
$\Gamma$
is an equivalence relation on the vertices of
$\Gamma$
; its equivalence classes form the connected components of
$\Gamma$
. If there is a unique connected component, then the graph
$\Gamma$
is said to be connected. In such a case, the diameter of
$\Gamma$
is the least
$\ell$
such that any pair of vertices in
$\Gamma$
are connected by a path of length at most
$\ell$
.
A minimally connected subgraph of a connected graph is called a spanning tree. A cycle of length
$\ell$
in
$\Gamma$
is a sequence of distinct vertices
$v_1, v_2, \ldots ,v_{\ell}$
with
$v_iv_{i+1}\in E(\Gamma)$
for all
$i \in [\ell]$
, where
$v_{\ell+1}$
is identified with
$v_1$
. A forest is an acyclic graph, i.e. a graph containing no cycle. An independent set in a graph
$\Gamma$
is a set of vertices
$I\subseteq V(\Gamma)$
such that the subgraph of
$\Gamma$
induced by I is the empty graph, that is to say
$E(\Gamma)\cap I^{(2)}=\emptyset$
. Conversely, a clique in
$\Gamma$
is a set of vertices
$K\subseteq V(\Gamma)$
such that the induced subgraph is complete, that is to say
$ K^{(2)}\subseteq E(\Gamma)$
; we refer to
$m\;:\!=\;\vert K\vert$
as the order of the clique K, and call K an m-clique.
2.2. Probabilistic notation and tools
We write
$\mathbb{P}$
,
$\mathbb{E}$
, and Var for probability, expectation, and variance respectively. We say that a sequence of events
$\mathcal{E}=\mathcal{E}(n)$
,
$n\in \mathbb{N}$
, holds a.a.s. (asymptotically almost surely) if
$\lim_{n\rightarrow \infty} \mathbb{P}(\mathcal{E}(n))=1$
. Throughout the paper we use standard Landau notation: for functions
$f,g\colon \mathbb{N}\rightarrow \mathbb{R}$
we write
$f=o(g)$
if
$\lim_{n\rightarrow \infty} f(n)/g(n)=0$
,
$f=O(g)$
if there exists a real constant
$C>0$
such that
$\limsup_{n\rightarrow \infty} \vert f(n)/g(n)\vert \leq C$
. We occasionally use
$f\ll g$
as a shorthand for
$f=o(g)$
. We further write
$f=\omega(g)$
if
$g=o(f)$
, and
$f=\Omega(g)$
if
$g=O(f)$
. Finally, we write
$f=\theta(g)$
if
$f=O(g)$
and
$f=\Omega(g)$
both hold.
We shall make repeated use of Markov’s inequality: given a non-negative integer-valued random variable X,
$\mathbb{P}(X>a)\leq ({1}/({a+1}))\mathbb{E}X$
for any integer
$a \geq 0$
. We shall also use the following standard Chernoff bound (see, e.g., [Reference Alon and Spencer1, Theorems A.1.11 and A.1.13]).
Proposition 1 (Chernoff bound). Let
$X_1, X_2, \ldots, X_n$
be independent and identically distributed Bernoulli random variables. Set
$X=\sum_i X_i$
and
$\mu\;:\!=\;\mathbb{E}X$
. Then, for any
$\delta\in \big(0, \frac23\big)$
,
\[\mathbb{P}(\vert X-\mu\vert\geq \delta \mu)\leq 2\exp\!\bigg({-}\frac{\delta^2 \mu}{3}\bigg).\]
Finally, we shall need Janson’s inequality [Reference Janson, Łuczak and Ruciński25] as well as a large-deviation extension of it due to Janson [Reference Janson24], which can be found in the form given below in, e.g., [Reference Alon and Spencer1, Theorems 8.1.1 and 8.7.2]. Given a set X and
$q\in [0,1]$
, a q-random subset X
′ of X is obtained by including each element of X in X
′ with probability q, independently of all other elements.
Proposition 2 (Janson inequalities.) Let U be a finite set and
$U_q$
a q-random subset of U for some
$q\in [0,1]$
. Let
$\mathcal{F}$
be a family of subsets of U, and for every
$F\in \mathcal{F}$
let
$\mathbf{1}_F$
be the indicator function of the event
$\{F\subseteq U_q\}$
. Set
$\mathbf{1}_{\mathcal{F}}=\sum_{F\in \mathcal{F}} \mathbf{1}_F$
, and let
$\mu=\mathbb{E} \mathbf{1}_{\mathcal{F}}$
and
$\Delta=\sum_{F,F'\in\mathcal{F}:F\cap F'\neq\emptyset,\,F\neq F'}\mathbb{E}(\mathbf{1}_F\mathbf{1}_{F'})$
. Then
$\mathbb{P}(\mathbf{1}_{\mathcal{F}}=0) \leq \exp\!(\!-{\mu^2}/{2\Delta})$
and
$\mathbb{P}(\mathbf{1}_{\mathcal{F}}=0) \leq \exp\!(\!-\mu+{\Delta}/{2})$
. Further, for any
$\gamma>0$
,
\begin{equation*} \mathbb{P}(\mathbf{1}_{\mathcal{F}} \leq (1-\gamma)\mu) \leq \exp\!\bigg({-}\frac{\gamma^2\mu}{2 + 2(\Delta/\mu)}\bigg). \end{equation*}
We shall use the Janson inequalities to show that the probability there exist ‘bridges’ connecting up large square components living on disjoint vertex sets A and B is high, with the set U then corresponding to the collection of edges from A to B, and the sets F corresponding to potential squares having a non-edge in A and a non-edge in B.
2.3. The square graph
The square graph
$S(\Gamma)$
was introduced in [Reference Behrstock, Falgas-Ravry, Hagen and Susse6] as a way of capturing the algebraic notion of thickness of order 1 and the geometric notion of quadratic divergence in graph-theoretic terms, and was denoted
$\square(\Gamma)$
in that paper. A related notion for triangle-free graphs was first investigated in [Reference Dani and Thomas15], and
$S(\Gamma)$
has subsequently been investigated in a number of papers, including [Reference Susse28] in connection with the existence of Morse subgroups in random right-angled Coxeter groups.
Combinatorially, it turns out to be more convenient to analyse the closely related graph
$T_1(\Gamma)$
, which admits
$S(\Gamma)$
as its line graph (
$S(\Gamma)$
being, for its part, better suited to some of the applications to geometric group theory). This latter graph was introduced in [Reference Behrstock, Falgas-Ravry and Susse7], where confusingly it was also referred to as ‘the square graph’ and denoted by
$\square(\Gamma)$
; we hope to resolve this unfortunate ambiguity in this paper by using the notation
$S(\Gamma)$
and
$T_1(\Gamma)$
. Generalizations
$T_k(\Gamma)$
,
$k\in\mathbb{Z}_{\geq 0}$
, of
$T_1(\Gamma)$
were in [Reference Behrstock, Çiçeksiz and Falgas-Ravry3] to study higher orders of algebraic thickness and divergence, with an inductive definition (which is not relevant to the present paper). For our purposes, however, we provide an equivalent definition of
$T_1(\Gamma)$
in terms of the induced squares in
$\Gamma$
and their pairwise interactions.
Definition 1. (
$T_1(\Gamma)$
: the square graph.) Given a graph
$\Gamma$
, the square graph of
$\Gamma$
, denoted by
$T_1(\Gamma)$
, is defined as follows. The vertex set of
$T_1(\Gamma)$
is the collection
$E(\overline{\Gamma})$
of non-edges of
$\Gamma$
. The edges of
$T_1(\Gamma)$
consist of those pairs of non-edges
$f, f'\in E(\overline{\Gamma})$
, such that the 4-set of vertices
$f\cup f'$
induces a square (i.e. a 4-cycle) in
$\Gamma$
.
We refer to connected components of
$T_1(\Gamma)$
as square components of
$\Gamma$
. Given such a component C, we define its support to be
$\mathrm{supp}(C)\;:\!=\;\bigcup_{f\in C}f$
, the collection of vertices in
$V(\Gamma)$
belonging to some
$f\in C$
. When
$\mathrm{supp}(C)=V(\Gamma)$
we say the component has full support.
Remark 3. (The other square graph:
$S(\Gamma)$
.) As mentioned above, for certain applications in geometric group theory it is natural to work with another auxiliary graph closely related to (but distinct from) the square graph
$T_1(\Gamma)$
, namely the line graph of
$T_1(\Gamma)$
, denoted by
$S(\Gamma)$
. This latter graph has the induced squares of
$\Gamma$
as its vertices, and as its edges those pairs of induced squares having a diagonal in common. As noted in [Reference Behrstock, Falgas-Ravry and Susse7, Remark 1.2], both versions of a square graph carry essentially the same information, so working with one rather than the other is primarily a question of what is convenient for the intended application.
Remark 4. (Challenges when studying the connectivity of the square graph.) Connectivity in the square graph is a delicate matter. In the next two subsections we highlight two features of the square graph that our arguments will have to contend with. The first is that we may have two distinct square components with exactly the same support (something which makes the study of connectivity considerably more challenging); the second is that connectivity in the square graph of
$\Gamma$
is not monotonic with respect to the addition or removal of edges in
$\Gamma$
. Indeed, adding or removing an edge in a graph can cause the associated square graph to change from being connected to being disconnected or, on the contrary, from disconnected to connected.
2.3.1. Coexistence of distinct square components with the same support.
One of the results which makes the square graph a powerful tool for studying the geometry of RACGs is that having a component of full support (together with the original graph not being a join) is equivalent to the associated RACG having quadratic divergence [Reference Behrstock, Falgas-Ravry, Hagen and Susse6, Reference Behrstock, Hagen and Sisto8, Reference Levcovitz26]. Several papers have been written studying square graphs which contain components of full support, so that this property could be applied. Here we observe that there exist graphs whose associated square graphs have the following property, which we found surprising: the existence of more than one component with full support. We illustrate this with a concrete example (from which many similar ones can be built by varying the relevant parameters, including ones with other numbers of components of full support).
Proposition 3. There exist graphs
$\Gamma$
such that
$T_1(\Gamma)$
contains two distinct components each having full support in
$\Gamma$
.
Proof. The idea in building such an example is to begin with a graph with a square component of full support that has many non-edges which are not the ‘diagonal’ of any induced square. Then, we can add some additional edges which do not make any of the original squares non-induced, but create new induced squares that can be woven together to form a new component of the square graph which is also of full support. Moreover, with sufficient care, we can do this in a way that ensures that each ‘diagonal’ of a new square is not in the link of the ‘diagonal’ of an old square (or vice versa), so that the resulting two square components are distinct, despite both being supported on the entire vertex set.
We begin with a graph G ′ (see Figure 1) that is the concatenation of a sequence of squares along their diagonals together with some extra edges to make some of the squares in the concatenation non-induced. By producing a graph with fewer induced squares, these extra edges will make it easier later on in the construction to ensure that the second square component with full support we shall build does not merge with the square component in G ′. We name the vertices and the edges of the graph G ′ as follows:
\begin{align*} V(G') & = \{v_i\colon i \in [0,21]\}; \\[5pt] E(G') & = \{v_iv_{i+10},v_iv_{i+12}\colon i \in [9]\} \cup \{v_0v_{12},v_0v_{21},v_{10}v_{11},v_{10}v_{20}\} \\[5pt] & \quad \bigcup \{v_iv_{i+1}\colon i \in [0,9]\} \cup \{v_0v_{10}\} \cup \{v_iv_{i+1}\colon i\in [11,20]\} \cup \{v_{11}v_{21}\} \\[5pt] & \quad \bigcup \{v_iv_{i+2}\colon i \in [0,8]\} \cup \{v_0v_{9},v_1v_{10}\} \cup \{v_iv_{i+2}\colon i\in [11,19]\} \cup \{v_{11}v_{20},v_{12}v_{21}\}. \end{align*}
The set on the first line in the definition of E(G
′) consists of the edges that connect the top and bottom of the ladder, while the sets on the second and third lines connect pairs of indices that differ by one and two inside the top layer of the ladder and similarly in the bottom layer (the third set being used to decrease the number of induced squares). Figure 1 shows the graph G
′; the vertices
$v_0,v_{11}$
at the beginning and the end of the figure are the same vertices drawn twice to make it easier to see the cyclic symmetry of the graph thus constructed.
The graph G ′.
To make the distinction with the graph we will add on top of this, we note that the diagonals of induced squares in this graph (including the blue squares in Figure 3) are vertices of the non-edges whose indices satisfy the following condition:
-
• one index is
$i \in [0,10]$
and the other is one of the three indices
$i+11$
or
$(i \pm 2)1\,(\textrm{mod}\;1) +11$
.
Now, we add some additional edges to construct another square component on these underlying vertices that will use a completely distinct set of diagonals and which will not close off any of the diagonals of the above square component. The idea is to shift the indices on one side of the above circular strip enough that when we add edges in a similar way to those above there will be no overlaps of the diagonals. We shift the bottom row by six indices to define G ′′ as follows.
Let G
′′ be the graph with the same set of vertices as G
′ and whose edges, E(G
′′), consist of all the pairs of indices where the first index is
$i \in [0,10]$
and the second is one of the two indices
$(i+6\pm 1)1\,(\textrm{mod}\;1) +11$
(see Figure 2).
The graph G ′′. Note that the bottom indices are shifted to emphasize the similarity with G ′.
Two perspectives on the graph G. Both highlight all the squares that contain the vertices 5 and 16 (in blue) and the vertices 7 and 14 (in red). Both emphasize the bipartite division of the vertices. The figure on the left highlights the distinction (as seen by the different ‘slopes’) between the blue squares (which are in the first component of full support) and the red squares (which are in the second component of full support). The figure on the right emphasizes the symmetry and avoids the multiple collinear vertices which hide some of the edges in the graph on the left (for instance, those connecting the vertices at the bottom to the ones at the top).
With these two graphs now constructed, we consider the graph
$G=G'\cup G''$
, with
$V(G)=V(G')=V(G'')$
and
$E(G)=E(G')\cup E(G'')$
, illustrated (in two ways) in Figure 3. In the graph G, the new diagonals of induced squares (i.e. those squares which use at least one edge from G
′′) consist of all the pairs of indices where
-
• one index is
$i \in [0,10]$
and the other is one of the three indices
$(i+6)1\,(\textrm{mod}\;1) +11$
or
$(i+6\pm 2)1$
$(\textrm{mod}\;1) +11$
.
The diagonals of the first square component with full support are the diagonals coming from G
′, and the diagonals of the second square component with full support are the diagonals coming from squares which use some edges from G
′′. Note that both sets of diagonals have full support by construction. Also note that every diagonal of a square in G is of one of the two forms previously noted in the two bullet points. Since the ones in G
′ and those including an edge of G
′′ are distinct, no diagonal in one can be connected in
$T_1(G)$
to a diagonal from the other. Thus
$T_1(G)$
has two distinct components, both having full support in G.
This construction was independently verified by computer, and a number of related examples were also generated and checked (the source code and data is available from the authors). We note in particular that a slight variant of the above ideas yields an example in which there are three distinct square components with full support (using 22 vertices on each side instead of 11 and then shifting by 12 instead of 6), and further variations also allow us to build examples with an even larger number of distinct square components of full support.
2.3.2. Non-monotonicity of connectivity in square percolation.
The connectivity properties of the graph
$T_1(\Gamma)$
are not monotone under the addition of edges to
$\Gamma$
. Indeed, adding an edge to
$\Gamma$
could have a number of different potential effects. It could create new induced squares in
$\Gamma$
(and thus new edges in
$T_1(\Gamma)$
), but it also removes a non-edge (so that
$T_1(\Gamma)$
loses a vertex and all edges incident with it), which can destroy some induced squares that were in
$\Gamma$
.
As an example, consider the complete bipartite graph
$\Gamma=K_{2,n-2}$
with one part of size 2 and another of size
$n-2$
. Clearly,
$T_1(\Gamma)$
is connected. However, if we delete any edge from
$\Gamma$
, or if we add an edge inside the part of size 2, then
$T_1(\Gamma)$
becomes disconnected (and in the latter case becomes an edgeless graph on
$\binom{n-2}{2}$
vertices). This illustrates the sensitivity and non-monotonicity of the connectivity properties we are considering in this paper.
2.3.3. The extremal bound for thick graphs.
We also state here the following useful property of graphs that have a square component with full support, which was first proved in [Reference Behrstock, Falgas-Ravry, Hagen and Susse6, Lemma 5.5] and later greatly generalized in [Reference Behrstock, Çiçeksiz and Falgas-Ravry3, Theorem 1.4] to encompass all thick graphs.
Proposition 4 (Extremal bound for thick graphs [Reference Behrstock, Çiçeksiz and Falgas-Ravry3, Reference Behrstock, Falgas-Ravry, Hagen and Susse6].) Let
$\Gamma$
be a graph on n vertices such that
$T_1(\Gamma)$
contains a component C with
$\mathrm{supp}(C)= V(\Gamma)$
. Then
$\vert E(\Gamma)\vert \geq 2n-4$
.
2.4. Building and connecting giants in square percolation
We shall need two results from [Reference Behrstock, Falgas-Ravry and Susse7]. The first establishes that for p slightly above the threshold for the emergence of a giant square component, the number of non-edges in somewhat-large square components is concentrated around its mean (which is of order
$\Omega(n^2)$
).
Proposition 5 (Many edges in large components [Reference Behrstock, Falgas-Ravry and Susse7, Corollary 6.3].) Let
$\lambda>\sqrt{\sqrt{6}-2}$
be fixed, and let
$C>0$
be an arbitrary constant. Let
$\Gamma\sim \mathcal{G}_{n,p}$
and suppose
$p=p(n)$
satisfying
\begin{equation*} \frac{\lambda}{\sqrt{n}\,} \leq p(n) \leq C\sqrt{\frac{\log n}{n}}. \end{equation*}
Then, with probability
$1-O(n^{-1})$
, the number
$N_v$
of non-edges
$f\in E(\overline{\Gamma})$
that belong to square components of size at least
$(\!\log n)^4$
satisfies
$N_v=(1-o(1))\mathbb{E}N_v =\Omega(n^{2})$
.
In [Reference Behrstock, Falgas-Ravry and Susse7, Corollary 6.3] this was stated with
$C=5$
, but the proof works for any choice of the constant
$C>0$
in the upper bound on p(n).
The second result concerns vertex sprinkling; it allows a number of somewhat-large square components to connect up into a giant square component.
Proposition 6 (Sprinkling lemma [Reference Behrstock, Falgas-Ravry and Susse7, Lemma 6.6].) Let
$p=p(n)$
satisfy
$\Omega(1/\sqrt{n}) \leq p(n) \leq O(((\!\log n)/n)^{{1}/{3}})$
, and let
$\Gamma\sim \mathcal{G}_{n,p}$
. Let
$V_1\sqcup V_2$
be a bipartition of
$V(\Gamma)$
such that
$\vert V_2\vert =\Omega(n)$
. Then, conditional on the event that there are
$\Omega(n^2)$
pairs from
$E(\overline{\Gamma[V_1]})$
that lie in components of
$T_1(\Gamma[V_1])$
of size at least
$(\!\log n)^4$
, the probability that there exists a square component C in
$T_1(\Gamma)$
containing all the pairs from
$E(\overline{\Gamma[V_1]})$
that lie in components of
$T_1(\Gamma[V_1])$
of size at least
$(\!\log n)^4$
is at least
$1- \exp\!(\!-\Omega((\!\log n)^2))$
.
In [Reference Behrstock, Falgas-Ravry and Susse7, Lemma 6.6] this was stated with an upper bound of
$p(n)=O(\sqrt{(\!\log n)/n})$
, but the proof of the connecting lemma [Reference Behrstock, Falgas-Ravry and Susse7, Lemma 6.4], which is the main tool in the proof of [Reference Behrstock, Falgas-Ravry and Susse7, Lemma 6.6], carries over when we have the weaker upper bound
$p(n) \leq O(\sqrt[3]{(\!\log n)/n})$
without any change, as does the remainder of the proof of [Reference Behrstock, Falgas-Ravry and Susse7, Lemma 6.6].
We shall need an additional result that is somewhat reminiscent of the connecting lemma [Reference Behrstock, Falgas-Ravry and Susse7, Lemma 6.4], and is proved in an analogous manner via Janson’s inequality.
Proposition 7. (Giant-connecting lemma.) Let
$\Gamma\sim\mathcal{G}_{n,p}$
, with
$p=p(n)$
satisfying
\[\frac{1}{\sqrt{n}\,} \ll p(n) \leq 100\bigg(\frac{\log n}{n}\bigg)^{{1}/{3}}.\]
Let
$M=M(n)$
be such that
$1\ll M\ll p^{-1}$
. Suppose
$W_1\sqcup W_2$
is a partition of
$V(\Gamma)$
such that
$\vert W_1\vert = n/M$
, and there are
$\Omega(n^2)$
non-edges of
$W_2$
that lie in the same (giant) component
$C_2$
of
$T_1(\Gamma[W_2])$
. Then the probability that there exists some component
$C_1$
of
$T_1(\Gamma[W_1])$
of size at least M such that
$C_1$
and
$C_2$
are not a subset of the same component in
$T_1(\Gamma)$
is at most
\begin{equation*} \frac{n^2}{M^3}\exp\!(\!-\Omega(Mnp^2)). \end{equation*}
Further, if there exist two distinct components
$C_2$
and
$C_2'$
of
$T_1(\Gamma[W_2])$
of size
$\Omega(n^2)$
, then with probability
$1-\exp\!(\!-\Omega(n^2p^2))$
they are a subset of the same component in
$T_1(\Gamma)$
.
(The upper bound on p here is taken to match the range in which we will be applying the proposition in the proof of Theorem 3 – the proof for any
$p=o(1)$
.)
Proof. Let U denote the complete bipartite graph with bipartition
$W_1\sqcup W_2$
. Clearly, the collection of edges of
$\Gamma$
from
$W_1$
to
$W_2$
is distributed as a p-random subset of U.
Given a component
$C_1$
of
$T_1(\Gamma[W_1])$
of size at least M, there are
$\Omega(n^2M)$
pairs
$\{x_1x_2, y_1y_2\}$
with
$x_1x_2\in C_1$
,
$y_1y_2\in C_2$
. For each such pair, we define
$F_{x_1x_2, y_1y_2}$
to be the event that
$x_iy_j\in E(\Gamma)$
for every
$i,j\in [2]$
, i.e. that
$x_1x_2y_1y_2$
induces a square of
$\Gamma$
joining
$C_1$
to
$C_2$
in
$T_1(\Gamma)$
. The probability of this event is
$p^4$
, and we are thus in a position to apply Janson’s inequality.
We have
$\mu =\Omega(n^2Mp^4)$
. To compute the parameter
$\Delta$
, note that
$F\;:\!=\;F_{x_1x_2, y_1y_2}$
and
$F'\;:\!=\;F_{x'_1x'_2, y'_1y'_2}$
are independent unless
$X\;:\!=\;\vert \{x_1,x_2\}\cap \{x'_1, x'_2\}\vert $
and
$Y\;:\!=\;\vert \{y_1,y_2\}\cap \{y'_1, y'_2\}\vert $
are both strictly positive. If
$(X,Y)=(2,2)$
then
$F=F'$
. Further, note that
$\mathbb{E}\mathbf{1}_F\mathbf{1}_{F'}$
is equal to
$p^7$
if
$(X,Y)=(1,1)$
and to
$p^6$
if
$(X,Y)=(2,1)$
or (1, 2).
Now, for
$\{x_1x_2, y_1y_2\}$
fixed we have O(n) ways of picking
$y'_1y'_2 \in C_2$
such that
$Y=1$
and at most M ways of picking
$x'_1x'_2\in C_1$
such that
$X =1$
. Going over all possibilities
$(X, Y)\in \{(1,1), (2,1), (1,2)\}$
, calculating
$\mathbf{1}_F\mathbf{1}_{F'}$
in each case and using our assumption that
$M\ll p^{-1}$
, we see that
$\Delta = O(\mu p^2n)$
. It then follows from Proposition 2 and Janson’s inequality, together with the linearity of expectation and Markov’s inequality, that the probability that one of the at most
$n^2/(2M^3)$
choices of a square component
$C_1$
in
$T_1(\Gamma[W_1])$
with size at least M that does not join up to
$C_2$
in
$T_1(\Gamma)$
is at most
\[ \frac{n^2}{2M^3}\exp\!\bigg({-}\Omega\bigg(\frac{\mu}{p^2n}\bigg)\bigg) = \frac{n^2}{M^3}\exp\!(\!-\Omega(Mp^2n)). \]
It remains to show the ‘Further…’ part of the proposition. Let
$\mathcal{B}$
be the event that there are fewer than
${n^2}/{4M^2}$
non-edges in
$\Gamma[W_1]$
. Applying the Chernoff bound (Proposition 1) and using our assumption that
$p=o(1)$
, we have
$\mathbb{P}(\mathcal{B}) = \exp\!(\!-\Omega(n^2/M^2))$
, which by our bounds on p and M is at most
$\exp\!(\!-\Omega(n^2p^2))$
.
Suppose the event
$\mathcal{B}$
does not occur. Now, note that there are at most O(1) distinct giant square components in
$T_1(\Gamma[W_2])$
. For any such pair of giants
$C_2,C_2'$
and any
$x_1x_2\in C_2$
,
$y_1y_2\in C_2'$
with
$\{x_1,x_2\}\cap \{y_1,y_2\}=\emptyset$
, and any non-edge
$z_1z_2\in E(\overline{\Gamma[W_1]})$
, let
$F_{x_1x_2, y_1y_2,z_1z_2}$
be the event that
$x_iz_j$
and
$y_iz_j$
are edges of
$\Gamma$
for every
$i,j\in [2]$
(and in particular that
$C_2$
and
$C_2'$
join up in
$T_1(\Gamma)$
through two induced squares both having
$z_1z_2$
as a diagonal). Clearly, the probability of this event is
$p^8$
. Conditional on
$\mathcal{B}$
not occurring, there are
$\Omega(n^6/M^2)$
such triples
$x_1x_2, y_1y_2, z_1z_2$
. Here again we can apply Janson’s inequality with parameters
$\mu= \Omega(p^8n^6/M^2)$
and
$\Delta=O(\mu n^3p^6/M)$
to deduce that the probability that
$C_2'$
and
$C_2$
fail to connect in
$T_1(\Gamma)$
through an
$F_{x_1x_2, y_1y_2,z_1z_2}$
-event when we reveal the edges from
$W_1$
to
$W_2$
is at most
$\exp\!(\!-\mu^2/2\Delta)=\exp\!(\!-\Omega(n^3p^3))$
, where in the last inequality we have used our assumption that
$M\ll p^{-1}$
. Since as noted above that there can be only O(1) pairs of distinct giants
$C_2, C_2'$
in
$T_1(\Gamma[W_2])$
, it follows from Markov’s inequality that the probability that any two of them fail to join up in
$T_1(\Gamma[W])$
is at most
$\mathbb{P}(\mathcal{B}) + O(1)\cdot \exp\!(\!-\Omega(n^3p^3)) = \exp\!(\!-\Omega(n^2p^2))$
, as claimed.
3. Connectivity in square percolation
3.1. Proof outline
Our proof of Susse’s conjecture on the location of the connectivity threshold for
$S(\Gamma)$
(and
$T_1(\Gamma)$
),
$\Gamma\sim\mathcal{G}_{n,p}$
, is structured as follows.
We first show that for ‘large’ p (which for us means
$p=\Omega((\!\log (n)/n)^{{1}/{3}})$
,
$T_1(\Gamma)$
is connected (Proposition 9). We then concentrate on values of
$p=p(n)$
which are not ‘large’, but which are a little above the threshold for the emergence of a giant component in
$T_1(\Gamma)$
(which occurs at
$p\approx\sqrt{\sqrt{6}-2}/\sqrt{n}$
). For p in this range we prove Theorem 3, showing that a.a.s. the giant square component is unique and that all other square components are small, with size
$O((\!\log n)^2)$
. For this part of the argument, we rely on a partial converse to Proposition 4 (Lemma 1), the tools from [Reference Behrstock, Falgas-Ravry and Susse7] we discussed in Section 2, and somewhat intricate partitioning arguments.
Finally, we use Lemma 1, Proposition 4, and Janson’s inequality to rule out the existence of small square components of size
$O((\!\log n)^2)$
for p just above Susse’s conjectured connectivity threshold, thereby completing the proof of Theorem 1.
3.2. One square component to rule them all: Proof of Theorem 3
We begin with a series of propositions showing that for large p it is straightforward to establish the a.a.s. existence of a unique giant square component.
Proposition 8. Let
$\Gamma\sim\mathcal{G}_{n,p}$
. If
$p=p(n)$
satisfies
$100(({\log n})/{n})^{{1}/{4}} \leq p(n)$
, then a.a.s.
$T_1(\Gamma)$
has diameter at most two and in particular is connected.
Proof.
Case 1:
$1-p\geq 100/n$
. Let
$x_1x_2$
and
$y_1y_2$
be distinct (but not necessarily disjoint) pairs of vertices from
$V(\Gamma)$
; the size of the common neighbourhood of
$\{x_1,x_2,y_1,y_2\}$
in
$\Gamma$
stochastically dominates a
$\mathrm{Binomial}(n-4, p^4)$
random variable. Applying a Chernoff bound (Proposition 1) to bound the probability of the pairs having fewer than
$p^4n/2$
neighbours in common and taking the union bound over all such pairs, we see that, for
$p \geq 100(({\log n})/{n})^{{1}/{4}}$
, a.a.s. all distinct pairs
$x_1x_2, y_1y_2$
from
$V(\Gamma)^{(2)}$
have at least
${p^4n}/{2}$
neighbours in common.
Further, using the bound
$\binom{n}{m} \leq ({{\mathrm{e}} n}/{m})^m$
, we have that the expected number of m-cliques in
$\Gamma$
is
\begin{align*}\binom{n}{m}p^{\binom{m}{2}}\leq\bigg(\frac{en}{m}p^{({m-1})/{2}}\bigg)^m.\end{align*}
For
$m=\lceil{p^4n}/{4}\rceil$
and
$100((\!\log n)/n)^{1/4} \leq p \leq 1-100/n$
, the value of this expectation is
\begin{equation*} \bigg(\frac{en}{m}p^{({m-1})/{2}}\bigg)^m \leq \exp\!\bigg(m\bigg(3+5\log\bigg(\frac{1}{p}\bigg) - \frac{np^4}{8}\log\bigg(\frac{1}{p}\bigg)\bigg)\bigg). \end{equation*}
Now, on the other hand, for
$p\leq 1/{\mathrm{e}}$
we have that
$4m\geq np^4\geq 10^8 (\!\log n)$
and
$\log (1/p)\geq 1$
, whence the above is o(1). On the other hand, if
$1/{\mathrm{e}}\leq p \leq 1-100/n$
, then since the function
$x\mapsto x^4\log(1/x)$
is decreasing in the interval
$x\in [1/{\mathrm{e}}, 1]$
, it follows that
\[ \frac{np^4}{8}\log\bigg(\frac{1}{p}\bigg) \geq \frac{n(1-100/n)^4}{8}\log\bigg(\frac{1}{1-100/n}\bigg) = \frac{100}{8}-o(1)>10, \]
whence the above is at most
$\exp\!(\!-m(3+5-10))=\exp\!(\!-\Omega(n))=o(1)$
. It thus follows by Markov’s inequality a.a.s. that
$\Gamma$
contains no such clique. In particular, a.a.s. any
$p^4n/2$
-set in
$\Gamma$
contains at least one non-edge.
It follows from the two previous paragraphs that a.a.s. for any pair of distinct non-edges
$x_1x_2, y_1y_2$
from
$V(\Gamma)^{(2)}\setminus E(\Gamma)$
there exists a non-edge
$z_1z_2\in E(\overline{\Gamma})$
with
$z_1,z_2$
lying in the common neighbourhood of
$\{x_1,x_2,y_1,y_2\}$
, whence
$x_1x_2$
and
$y_1y_2$
are connected by a path of length at most two in
$T_1(\Gamma)$
. This establishes the proposition in this case.
Case 2:
$1-p\leq 100/n$
. By classical results on the connectivity threshold for the Erdős–Rényi random graph model
$\mathcal{G}_{n, 1-p}$
[Reference Erdős and Rényi20], the complement graph
$\overline{\Gamma}\sim\mathcal{G}_{n,1-p}$
of
$\Gamma$
is a.a.s. not connected. What is more, it is easily shown (by, e.g., a first-moment argument) that either
$\overline{\Gamma}$
contains at most one edge (in which case
$T_1(\Gamma)$
is a complete graph on at most one vertex) or it contains at least two distinct non-trivial components. Now, clearly any pair of non-edges of
$\Gamma$
taken from distinct non-trivial components of
$\overline{\Gamma}$
are joined by a square in
$\Gamma$
. It follows that for p in this range,
$T_1(\Gamma)$
again has a.a.s. diameter at most two.
Proposition 9. Let
$\Gamma\sim\mathcal{G}_{n,p}$
, and let
$\varepsilon>0$
be fixed. If
$p=p(n)$
satisfies
\[100\bigg(\frac{\log n}{n}\bigg)^{{1}/{3}} \leq p(n) \leq 100\bigg(\frac{\log n}{n}\bigg)^{{1}/{4}},\]
then a.a.s.
$T_1(\Gamma)$
is connected.
Proof. We argue similarly to Case 1 in Proposition 8. Since the distribution of the number of neighbours of a triple of vertices is
$\mathrm{Binomial}(n-3, p^3)$
, applying a Chernoff bound (Proposition 1) and taking the union over all such triples, we see that for
$p\geq 100(\!\log (n)/n)^{{1}/{3}}$
the following holds:
-
(i) a.a.s. every triple of vertices in
$\Gamma$
has at least
$p^3n/2$
common neighbours.
Further, the expected number of cliques of size
$m= \lceil p^3n /2\rceil$
is at most
\begin{align*}\bigg(\frac{n\mathrm{e}}{m}p^{({m-1})/{2}}\bigg)^m=o(1)\end{align*}
for
$p \leq 100(\!\log(n)/n)^{{1}/{4}}$
. Thus, we have that
-
(ii) a.a.s. every set of
$p^3n/2$
vertices in
$\Gamma$
must contain at least one non-edge of
$\Gamma$
.
It follows from the two facts (i) and (ii) that
-
(iii) a.a.s. for any pair of intersecting non-edges
$xy, yz\in E(\overline{\Gamma})$
, xy, yz belong to the same square component.
Now, for p in the range we are considering, classical results of Erdős and Rényi [Reference Erdős and Rényi20] imply that
-
(iv) a.a.s.
$\overline{\Gamma}\sim \mathcal{G}_{n,1-p}$
is connected.
It follows from (iii) and (iv) that
$T_1(\Gamma)$
is a.a.s. connected.
By a Chernoff bound, for
$p(n)\leq 1-\omega (n^{-2})$
we have that with probability
$1-\exp\!(\!-\Omega $
$(n^2(1-p)))=1-o(1)$
there are
$\Omega(n^2(1-p))=\omega(1)$
non-edges in
$\Gamma$
, each of which is a vertex of
$T_1(\Gamma)$
. It thus follows from Propositions 8 and 9 that for p(n) between
$100 (\!\log(n)/n)^{{1}/{3}}$
and
$1-\omega(n^{-2})$
, a.a.s. there exists a unique component in
$T_1(\Gamma)$
of order
$\Omega(n^2 (1-p))$
, proving Theorem 3 in that range.
In the remainder of this subsection, we therefore turn our attention to the range
\[p(n)\in R=R(n) \;:\!=\; [C\sqrt{({\log \log n})/{n}}, 100(\!\log(n)/n)^{{1}/{3}}],\]
where
$C>0$
is a large constant to be specified later. We first establish a simple proposition showing that for
$p\geq 50\sqrt{\log (n)/n}$
, with probability
$1-O(n^{-1})$
all non-edges of
$\Gamma$
belong to a ‘somewhat large’ square component (this can be contrasted with Proposition 5 which, for p above
$\sqrt{\sqrt{6}-2}/\sqrt{n}$
, gives us a.a.s.
$\Omega(n^{2})$
non-edges in ‘somewhat large’ square components).
Proposition 10. Suppose p(n) satisfies
$50\sqrt{\log (n)/n} \leq p \leq 100(\!\log(n)/n)^{{1}/{3}}$
. Then with probability
$1-O(n^{-1})$
, every non-edge of
$\Gamma$
belongs to a square component of size at least
$(\!\log n)^4$
.
Proof. The expected number of complete subgraphs on eight vertices contained in
$\Gamma$
is
$\binom{n}{8}p^{\binom{8}{2}}=O(n^8p^{28})$
, which for
$p\leq n^{-{1}/{3}+o(1)}$
is
$o(n^{-1})$
. Thus, by Markov’s inequality, the event
$\mathcal{B}$
that
$\Gamma$
contains a complete subgraph on eight vertices has probability at most
$o(n^{-1})$
.
Consider a pair of vertices v, v
′ from
$V(\Gamma)$
with
$vv'\notin E(\Gamma)$
. By a Chernoff bound (Proposition 1), with probability at least
$1-2\exp\!(\!-({1}/{12}+o(1))p^2n) = 1-O(n^{-3})$
, the set X of common neighbours of v and v
′ has size at least
$\frac{1}{2}p^2n$
and at most
$\frac{3}{2}p^2n$
. If
$\mathcal{B}$
does not occur, then
$\Gamma[X]$
does not contain any complete graph on eight vertices, whence, by Turán’s theorem [Reference Turán29], it contains at most
$\big(1-\frac{1}{7}+o(1)\big)\binom{\vert X\vert}{2}$
edges. In particular, there is a set
$C=X^{(2)}\cap E(\overline{\Gamma})$
of at least
$\big(\frac{1}{7}-o(1)\big)\binom{p^2n/2}{2}>\frac{1}{64}p^4n^2$
non-edges in
$\Gamma[X]$
, all of which lie inside the same square component as vv
′.
Case 1:
${p\geq 4 \log n/\sqrt{n}}$
. Taking a union bound over the
$\binom{n}{2}$
pairs vv
′ from
$V(\Gamma)^{(2)}$
, the argument above shows that, with probability
$1-\mathbb{P}(\mathcal{B})-\binom{n}{2}\cdot O(n^{-3})= 1-O(n^{-1})$
, every pair
$vv'\in E(\overline{\Gamma})$
is in a component of
$T_1(\Gamma)$
of size at least
$(\!\log n)^4$
.
Case 2:
${p\leq 4 \log n/\sqrt{n}}$
. Suppose
$\mathcal{B}$
does not occur. With X and C as above, and C in particular of size at least
$\frac{1}{64} p^4n^2>10\,000 (\!\log n)^2$
, there must exist a perfect matching
$e_1, e_2, \ldots, e_m$
of
$m\;:\!=\;\lceil 100 \log n\rceil$
non-edges of
$\Gamma$
inside X (i.e. m pairwise disjoint non-edges). We use these non-edges to explore the square component containing vv
′. For
$1\leq t\leq m$
, do the following: set
$X_t$
to be the set of vertices in
$V(\Gamma)\setminus(X\cup\{v,v'\})$
sending edges to both vertices in
$e_t=v_tv'_t$
, and let
$C_t\;:\!=\;X_t^{(2)}\cap E(\overline{\Gamma})$
. If
$X_t$
has size less than
$\frac{1}{2}p^2n$
or more than
$\frac{3}{2}p^2n$
, terminate the process; otherwise, it follows from Turán’s theorem, just as in the analysis of Case 1, that
$C_t$
has size at least
$10\,000(\!\log n)^2$
and contains a collection
$e_{(t-1)m+1}, \ldots, e_{tm}$
of m non-edges in
$X_t$
forming a perfect matching. Add
$C_t$
to C and
$X_t$
to X. Then, if
$t\geq (\!\log n)^2$
terminate the process, otherwise move to step
$t+1$
of our iterative exploration.
We claim that either
$\mathcal{B}$
occurs or, with probability
$1-O(n^{-3})$
, the process ends with
$t=\lceil (\!\log n)^2\rceil $
and we have
$\frac{1}{2}p^2n \leq \vert X_t\vert \leq \frac{3}{2}p^2n$
at each time step t,
$1\leq t\leq (\!\log n)^2$
. Note that if this is the case then C at the end of the process has size at least
$(\!\log n)^4$
, and is part of the same component as vv
′ in
$T_1(\Gamma)$
. Taking a union bound over all pairs vv
′, our claim would thus imply that with probability
$1- \mathbb{P}(\mathcal{B})-\binom{n}{2}\cdot O(n^{-3})= 1-O(n^{-1})$
, every pair
$vv'\in E(\overline{\Gamma})$
is in a component of
$T_1(\Gamma)$
of size at least
$(\!\log n)^4$
, as desired.
Let us therefore prove our claim. Note first of all that at each time step
$t<(\!\log n)^2$
before the process terminates we have
$V(\Gamma)\setminus (X\cup\{v,v'\}) > n - 2t(\!\log n)^2 p^2n=(1-o(1))n$
. By a Chernoff bound, with probability
$1-2\exp\!(\!-({1}/{12}+o(1))p^2n)= 1-O(n^{-4})$
, we have that
$X_t\in [{p^2n}/{2}, {3p^2n}/{2}]$
. Thus, as claimed, either
$\mathcal{B}$
occurs or, with probability
$1- (\!\log n)^2 O(n^{-4})=1-O(n^{-4})$
, the process ends with
$t=\lceil (\!\log n)^2$
and
$\frac{1}{2}p^2n \leq \vert X_t\vert \leq \frac{3}{2}p^2n$
holding at each time step t,
$1\leq t\leq (\!\log n)^2$
.
Corollary 2. Fix a subset
$V' \subseteq V(\Gamma)$
with
$\vert V'\vert =(1-o(1))n$
, and let
$p=p(n) \in R$
. Then, with probability
$1-O(n^{-1})$
, there exists a giant square component in
$T_1(\Gamma[V']) $
of size
$\Omega(n^2)$
.
Proof. Fix
$\delta>0$
, and partition the set V
′ as
$V'=V_1\sqcup V_2$
, where
$\vert V_2\vert=(\delta+o(1))n$
and
$\vert V_1\vert = (1-\delta-o(1))n$
. By Propositions 5 and 10, we have that with probability
$1-O(n^{-1})$
there are
$\Omega(n^{2})$
non-edges of
$\Gamma[V_1]$
that lie in square components of
$T_1(\Gamma[V_1])$
of size at least
$(\!\log n)^4$
. The corollary is then immediate from the sprinkling lemma, Proposition 6.
The last tool we need is the following partial converse to Proposition 4, giving a lower bound on the number of non-edges in a graph
$\Gamma$
that has a square component of full support.
Lemma 1. Suppose
$\Gamma$
is a graph on
$m\geq 4$
vertices, and that C is a square component of
$\Gamma$
with full support,
$\mathrm{supp}(C)=V(\Gamma)$
. Then
$\vert C\vert \geq m/2$
.
Proof. By definition, every vertex
$u\in V(\Gamma)=\mathrm{supp}(C)$
belongs to a non-edge
$uv\in E(\overline{\Gamma})$
with
$uv\in C$
. By double-counting, C must have size at least
$m/2$
.
With these results in hand, we are now ready to prove Theorem 3 for the remaining range of p,
$p\in R$
.
Proof of Theorem
3. Let
$C>0$
be a sufficiently large constant, and let
$p=p(n)$
satisfy
\[\frac{C\sqrt{\log\log n}}{\sqrt{n}} \leq p \leq 100\bigg(\frac{\log n}{n}\bigg)^{{1}/{3}}.\]
Let
$\Gamma\sim \mathcal{G}_{n,p}$
and write V for
$V(\Gamma)$
. Let
$M=\lfloor{\log n}/({8\log \log n})\rfloor$
. Take a balanced partition
$V=\sqcup_{i=1}^{2M^2}V_i$
of the vertex set of
$\Gamma$
into
$2M^2$
parts. Given a subset S of
$[2M^2]$
, we denote by
$V_S\;:\!=\;\bigcup_{i\in S}V_i$
the union of all parts
$V_i$
with
$i\in S$
.
Given any subset
$S\in [2M^2]^{(2M)}$
, let
$E_S$
be the event that there is a giant square component C inside
$T_1(\Gamma[V\setminus V_S])$
containing
$\Omega(n^2)$
non-edges of
$\Gamma$
, and further that every square component C
′ of
$T_1(\Gamma[V_S])$
of size at least M joins up to (every such giant) C in
$T_1(\Gamma)$
. We claim that
$E_S$
occurs with very high probability.
Claim 1. For every
$S\in[2M^2]^{(2M)}$
,
$\mathbb{P}(\overline{E_S})=o\Big({\binom{2M^2}{2M}}^{-1}\Big)$
.
Proof. Since
$\vert V\setminus V_S\vert=(1-({1}/{M})+o(1))n =(1+o(1))n$
, it follows from Corollary 2 that with probability
$1-O(n^{-1})$
there exists a giant square component C inside
$T_1(\Gamma[V\setminus V_S])$
. If such a giant exists, Proposition 7 tells us there is a probability of at most
$n^2M^{-3}\exp\!(\!-\Omega $
$(Mnp^2))$
that some component of size M in
$T_1(\Gamma[V_S])$
fails to connect up to it in
$T_1(\Gamma)$
. Picking our constant C sufficiently large, we have that for
$p\geq C\sqrt{\log\log (n) /n}$
this probability is
$O(n^{-1})$
. Putting it all together, the probability of
$E_S$
is
$1-O(n^{-1})=1- o\Big({\binom{2M^2}{2M}}^{-1}\Big)$
, proving the lemma. It is here that our choice of M comes in, as it ensures that
${2{\mathrm{e}} M}^{4M} = \exp\!\big(\big(\frac{1}{2}+o(1)\big)\log n\big)$
so that
\begin{equation*} \binom{2M^2}{M}^2\leq \bigg(\frac{2{\mathrm{e}} M^2}{M}\bigg)^{2M}=o(n). \end{equation*}
Further, given subsets
$S,S'\in [2M^2]^{(2M)}$
with
$\vert S\cap S'\vert=2M-1$
, let
$E_{S,S'}$
be the event that for every pair of components C in
$T_1(\Gamma[V\setminus V_S])$
and C
′ in
$T_1(\Gamma[V\setminus V_{S'}])$
such that C, C
′ both have size
$\Omega(n^2)$
, C and C
′ join up in
$T_1(\Gamma)$
. Again, we claim that this event
$E_{S, S'}$
occurs with very high probability.
Claim 2. For every
$S,S'\in [2M^2]^{(2M)}$
with
$\vert S\cap S'\vert=2M-1$
,
$\mathbb{P}(\overline{E_{S,S'}})=o\Big({\binom{2M^2}{2M}}^{-2}\Big)$
.
Proof. Our condition on M ensures that
\begin{align*} \vert V_S \cap V_{S'}\vert = (1+o(1))\frac{n}{2M^2}(2M-1) = (1+o(1))\frac{n}{M} = (1+o(1))\frac{8n\log \log n}{\log n} \end{align*}
satisfies
$1\ll M\ll p^{-1}$
. By Corollary 2, with probability
$1-O(n^{-1})$
there exists a square component in
$\Gamma[V \setminus V_S\cap V_{S'} ]$
of size
$\Omega(n^{2})$
. We can thus apply the ‘Further…’ part of Proposition 7 to deduce that with probability
$1-O(n^{-1})-\exp\!(\!-\Omega(n^2p^2))=1-o\Big({\binom{2M^2}{2M}}^{-2}\Big)$
every pair of square components of size
$\Omega(n^2)$
from
$\Gamma[V\setminus (V_S\cap V_{S'})]$
join up in
$T_1(\Gamma)$
.
We are now ready to complete the proof of Theorem 3. Applying Claim 1 and Markov’s inequality, we see that a.a.s. the event
$E_S$
occurs for every subset
$S\in [2M^2]^{(2M)}$
. Further, by Claim 2 and Markov’s inequality, a.a.s the event
$E_{S,S'}$
occurs for every pair of subsets
$S,S'\in [2M^2]^{(2M)}$
with
$\vert S\cap S'\vert = 2M-1$
. We may therefore in the remainder of the proof condition on the a.a.s. event
$\mathcal{E}\;:\!=\;\big(\bigcap_{S\in[2M^2]^{(2M)}}E_S\big) \cap \big(\bigcap_{S,S'\in[2M^2]^{(2M)}:\vert S\cap S'\vert=2M-1}E_{S,S'}\big)$
.
Observe that if C is a component in
$T_1(\Gamma)$
of size at least
$\binom{2M}{2}$
, then the support of C has size at least 2M, and by [Reference Behrstock, Falgas-Ravry, Hagen and Susse6, Lemma 5.5], there must be a 2M-set
$X\subseteq V$
and a subset
$C_X\subseteq C\cap X^{(2)}$
such that
$C_X$
is a square component in
$T_1(\Gamma[X])$
with full support. By Lemma 1, we must have that
$\vert C_X\vert \geq M$
.
Now, X meets at most 2M of the parts
$V_i$
, so there exists a set
$S\in[2M^2]^{(2M)}$
such that
$X\subseteq V_S$
. Since
$E_S$
holds, we have that
$C_X$
joins up in
$T_1(\Gamma)$
to every giant (
$\Omega(n^2)$
-sized) component C of
$T_1(\Gamma[V\setminus V_S])$
. Further, since
$\bigcap_{S,S'}E_{S,S'}$
holds, we have that for every
$S,S'\in [2M^2]^{(2M)}$
and every pair of giant components C in
$T_1(\Gamma[V\setminus V_S])$
and C
′ in
$T_1(\Gamma[V\setminus V_{S'}])$
, C and C
′ join up to the same square component in
$T_1(\Gamma)$
(since there exists a finite sequence
$S_0=S, S_1, S_2, \ldots , S_{\ell}=S'$
with
$S_i\in [2M^2]^{(2M)}$
,
$\vert S_i\cap S_{i+1}\vert=2M-1$
, and
$E_{S_i, S_{i+1}}$
occurring for every
$i\geq 0$
, and since by
$E_{S_i}$
each of the
$T_1(\Gamma[V\setminus V_{S_i}])$
contains a giant component).
It follows that there exists a unique component in
$T_1(\Gamma)$
of size greater than
\begin{align*}\binom{2M}{2}\geq \frac{1}{33}\bigg(\frac{\log n}{\log \log n}\bigg)^2,\end{align*}
and this component has size
$\Omega(n^2)$
(since
$E_S$
holds), proving the theorem.
3.3. The connectivity threshold in square percolation
We are now in a position to prove Theorem 1, whose content we restate here for the convenience of the reader – given
$\varepsilon>0$
fixed and
$\Gamma\sim \mathcal{G}_{n,p}$
for some sequence of probabilities
$p=p(n)$
, we must show the following:
-
(i) If
$n^{-1}\ll p\leq (1-\varepsilon)\sqrt{(\!\log n)/ n}$
, then
$S(\Gamma)$
is a.a.s. not connected. -
(ii) If
$(1+\varepsilon)\sqrt{(\!\log n)/n}\leq p$
, then
$S(\Gamma)$
is a.a.s. connected. -
(iii) If
$p\leq \sqrt{2-\varepsilon}\sqrt{(\!\log n)/n}$
, then
$T_1(\Gamma)$
is a.a.s. not connected. -
(iv) If
$\sqrt{2+\varepsilon}\sqrt{(\!\log n)/n}\leq p$
, then
$T_1(\Gamma)$
is a.a.s. connected.
Proof of Theorem
1. Part (i) follows from [Reference Susse28, Corollary 3.8], which proved that, for
$n^{-1}\ll p\leq (1-\varepsilon)\sqrt{(\!\log n) /n}$
, a.a.s.
$T_1(\Gamma)$
contains isolated squares: induced copies of the 4-cycle
$C_4$
not sharing a diagonal with any other induced copy of
$C_4$
. Each of these isolated squares corresponds to an isolated edge in
$T_1(\Gamma)$
, and thus an isolated vertex in
$S(\Gamma)$
. The a.a.s. existence of these isolated vertices implies that
$S(\Gamma)$
is a.a.s. not connected for p in this range.
Part (iii) is proved using a similar second-moment argument to [Reference Susse28, Corollary 3.8]. Suppose
$p\leq \sqrt{2-\varepsilon}\sqrt{(\!\log n)/n}$
. Then we claim that a.a.s. there are non-edges of
$\Gamma$
that are not contained in any induced square. Such non-edges correspond to isolated vertices of
$T_1(\Gamma)$
, and ensure the latter graph is not connected. It is therefore enough to prove our claim, which we now do.
Given a pair
$e\in V(\Gamma)^{(2)}$
, let
$X_e$
be the indicator function of the event that e is a non-edge of
$\Gamma$
whose endpoints have no neighbour in common. Observe that if
$X_e=1$
, then certainly e is not contained in any induced square of
$\Gamma$
. Set
$X=\sum_{e}X_e$
. Straightforward calculations then give
\begin{align*} \mathbb{E}X = \binom{n}{2}(1-p)(1-p^2)^{n-2} = \bigg(\frac{1}{2}+o(1)\bigg)n^2{\mathrm{e}}^{-p^2n} \geq \bigg(\frac{1}{2}+o(1)\bigg)n^{\varepsilon}, \end{align*}
while
\begin{align*} \mathbb{E}(X^2) & = \binom{n}{2}(1-p)^2\bigg((1-p^2)^{n-2} + 2(n-2)(1-2p^2+p^3)^{n-3} \\[3pt] & \quad + \binom{n-2}{2}(1-p^2)^{2(n-4)}(1-p^4)\bigg) \\[3pt] & = (\mathbb{E}X)^2(1+o(1)). \end{align*}
Thus,
$\mathrm{Var}(X)=o((\mathbb{E}X)^2)$
, and it follows immediately from Chebyshev’s inequality that, a.a.s.,
$X=(1+o(1))\mathbb{E}X\gg 1$
. Thus, a.a.s. for
$p \leq \sqrt{2-\varepsilon}\sqrt{(\!\log n)/n}$
,
$T_1(\Gamma)$
contains isolated vertices and is not connected.
For Part (ii), consider
$p=p(n)\geq (1+\varepsilon)\sqrt{\log n}/\sqrt{n}$
. By Propositions 9 and 8, we may assume that
$p=p(n)\leq 100(\!\log (n)/n)^{{1}/{3}}$
. Further, by Theorem 3, for p in this range we know that a.a.s. there exists a unique square component of size at least
$(\!\log n)^2$
. Thus, all that remains to be shown is that a.a.s.
$T_1(\Gamma)$
contains no smaller non-trivial component, i.e. that
$T_1(\Gamma)$
consists of a giant component together with a collection of isolated vertices (corresponding to non-edges of
$\Gamma$
not belonging to any induced square of
$\Gamma$
).
For
$k\geq 4$
and a k-set
$S\subseteq V(\Gamma)$
, let
$X_S$
be the indicator function of the event that there exists a connected component C of
$T_1(\Gamma)$
with support
$\mathrm{supp}(C)= S$
. Note that every non-trivial connected component of
$T_1(\Gamma)$
must have support of size at least 4, by definition. Clearly for
$X_S$
to be non-zero, we must have that
$\Gamma[S]$
contains at least
$2k-4$
edges (by Proposition 4).
Further, suppose C is a square component with support exactly S. Then for every non-edge
$f=\{x_1,x_2\}\in \overline{\Gamma}[S]$
belonging to C, every neighbour
$f'=\{y_1,y_2\}$
of f in
$T_1(\Gamma)$
and every vertex
$v\in V(\Gamma)\setminus S$
sending edges to both of the endpoints of f, v must also send edges to both of the endpoints of f
′. Indeed, suppose
$vx_1, vx_2$
are edges in
$\Gamma$
but
$vy_i$
is not. Then the 4-set
$\{vx_1x_2y_i\}$
induces a square in
$\Gamma$
connecting f to
$vy_i$
in
$T_1(\Gamma)$
, contradicting the fact that
$v\notin S=\mathrm{supp}(C)$
. Since X has full support on S, this implies that any vertex
$v\in V(\Gamma)\setminus S$
sending edges to both endpoints of f must in fact send edges to every vertex of S (indeed, for any
$z\in S$
, there is a sequence of non-edges
$f_0=f, f_1, f_2, \ldots , f_t$
such that, for each i,
$f_i\cup f_{i+1}$
induces a square in
$\Gamma[S]$
and
$z\in f_t$
).
By Lemma 1, any square component C with
$\mathrm{supp}(C)=S$
must contain a set
$L=\{f_1, f_2$
,
$\ldots, f_{\lceil k/2\rceil}\}$
of at least
$k/2$
non-edges in
$\Gamma[S]$
. Thus, the discussion from the previous two paragraphs tells us that if
$X_S>0$
then all of the following must hold:
-
•
$\vert S\vert =k\geq 4$
. -
•
$\Gamma[S]$
contains at least
$2k-4$
edges. -
• There is a set
$L\subseteq S^{(2)}$
of
$\lceil k/2\rceil$
distinct pairs of vertices from S such that, for every vertex
$v\in V(\Gamma)\setminus S$
, either v sends edges to all of S or, for every
$f\in L$
, at least one of the endpoints of f does not receive an edge from v.
We shall use this information to bound the probability that
$X_S>0$
. Fix a k-set S, and an arbitrary
$\lceil k/2\rceil$
-set
$L\subseteq S^{(2)}$
. Observe that, for any
$v\in V(\Gamma)\setminus S$
, the events
$(E_{v,f})_{f\in L}$
that v sends edges to both endpoints of
$f\in L$
are positively correlated
$\mathrm{Bernoulli}(p^2)$
random variables. Further, for
$f_1\neq f_2$
, the probability of
$E_{v,f_1}\cap E_{v, f_2}$
is
$p^3$
if
$f_1\cap f_2\neq \emptyset$
and
$p^4$
otherwise. We may thus apply Janson’s inequality with
$\mu= \vert L\vert p^4$
and
$\Delta \leq 2\binom{\vert L\vert}{2}p^3$
to deduce that
\begin{equation} \mathbb{P}\Bigg(\bigcap_{f\in L} \overline{E_{v,f}}\Bigg) \leq \exp\!\bigg\{{-}\frac{k}{2}p^2 + \frac{k^2}{8}p^3\bigg\}. \end{equation}
Now write
$\mathcal{A}_{v,L}$
for the event that either
$\big(\bigcap_{f\in L} \overline{E_{v,f}}\big)$
occurs or v sends an edge to every vertex in S. Note that for any choice of L, the events
$(\mathcal{A}_{v,L})_{v\in V(\Gamma)\setminus S}$
are mutually independent, and are independent of the state of edges inside
$\Gamma[S]$
. Noting that for p in our range and
$k\geq 4$
, we have
$p^k{\mathrm{e}}^{{k}p^2/2} \leq p^4{\mathrm{e}}^{2p^2}=o(n^{-1})$
, it follows from this independence, inequality (1), the bullet points above, our bounds on p, and standard bounds for binomial coefficients that, for any k with
$4\leq k\leq (\!\log n)^2$
and any k-set S,
\begin{align*} \mathbb{P}(X_S=1) & \leq \mathbb{P}\big(\vert E(\Gamma[S])\vert \geq 2k-4\big)\Bigg( \sum_{L\subseteq S^{(2)}:\vert L\vert = \lceil k/2\rceil}\prod_{v\in V(\Gamma)\setminus S}\mathbb{P}(\mathcal{A}_{v,L})\Bigg) \\[5pt] & \leq \binom{\binom{k}{2}}{2k-4}p^{2k-4}\binom{\binom{k}{2}}{\lceil k/2\rceil} \big(p^k + {\mathrm{e}}^{-{k}p^2/2+{k^2}p^3/8}\big)^{n-k} \\[5pt] & \leq (1+o(1))({\mathrm{e}} k)^{{5k}/{2}}p^{2k-4}{\mathrm{e}}^{-{k}np^2(1-o(1))/2}. \end{align*}
Setting
$X_k\;:\!=\;\sum_{S\in V(\Gamma)^{(k)}} X_S$
and using linearity of expectation, we can exploit the inequality above to bound the expected number of square components of
$T_1(\Gamma)$
with support of size k. Given k with
$4\leq k\leq (\!\log n)^2$
and a fixed k-set S, we have
\begin{equation*} \mathbb{E}(X_k) \leq \binom{n}{k}\mathbb{E}(X_S) < \bigg(\frac{{\mathrm{e}} n}{k}({\mathrm{e}} k)^{{5}/{2}}p^2{\mathrm{e}}^{-{p^2 n(1+o(1))}/{2}}\bigg)^kp^{-4} \leq o\bigg(\frac{(\!\log n)^{5k-2}}{n^{{(k-4)+k\varepsilon}/{2}}}\bigg), \end{equation*}
with the first inequality coming from elementary bound
$\binom{n}{k} \leq ({{\mathrm{e}} n}/{k})^k$
on the binomial coefficient
$\binom{n}{k}$
, and the second one from the monotonicity of
$x\mapsto x{\mathrm{e}}^{-x}$
in
$[1,+\infty)$
, our upper bound on k (namely
$k\leq (\!\log n)^2$
), and our lower bound on p (namely
$p\geq (1+\varepsilon)\sqrt{\log n}/\sqrt{n}$
). Applying Markov’s inequality and linearity of expectation, this implies that
\begin{equation*} \mathbb{P}\Bigg(\sum_{k=4}^{(\!\log n)^2} X_k>0\Bigg) \leq \sum_{k=4}^{(\!\log n)^2}\mathbb{E}X_k = O\bigg(\frac{(\!\log n)^{20}}{n^{4\varepsilon}}\bigg)=o(1), \end{equation*}
and thus a.a.s. there is no square component with support of size between 4 (the smallest possible size) and
$(\!\log n)^2$
. By Theorem 3 we know that a.a.s.
$X_n=1$
and
$X_k=0$
for
$k\in [(\!\log n)^2, n-1]$
. Thus, there is an a.a.s. unique non-trivial square component, and
$S(\Gamma)$
is a.a.s. connected as required.
Part (iv) follows directly from Part (iii) and Markov’s inequality: for
$p=p(n)$
satisfying
$100(\!\log(n)/n)^{{1}/{3}} \leq p\leq 1-\omega(n^{-2})$
, we showed in Propositions 9 and 8 that
$T_1(\Gamma)$
is a.a.s. connected. Further, by Part (iii) as established above, we know that for
$\sqrt{2+\varepsilon}\sqrt{\log (n)/n}\leq p(n)\leq 100(\!\log(n)/n)^{{1}/{3}}$
, there is an a.a.s. unique non-trivial component in
$T_1(\Gamma)$
. Thus, all we need to rule out is the presence of isolated vertices for p in that range, i.e. the existence of ‘bad’ non-edges of
$\Gamma$
that are not contained in any induced square of
$\Gamma$
. Given
$e\in V(\Gamma)^{(2)}$
, let
$X_e$
denote the indicator function of the event that e is a non-edge and that the joint neighbourhood of the endpoints of e forms a clique. Set
$X=\sum_e X_e$
, so that X is precisely the number of ‘bad’ non-edges of
$\Gamma$
. Then, by Markov’s inequality and linearity of expectation, our bounds on p, and the facts that
$x\mapsto (1+x+x^2+x^3){\mathrm{e}}^{-x}$
is monotonous decreasing when
$x\geq 3$
and that
$np^{{9}/{2}} = o((\!\log n)^2n^{-{1}/{2}})$
, we have
\begin{align*} \mathbb{P}(X>0) \leq \mathbb{E}X & \leq \binom{n}{2}(1-p)\sum_{i=0}^{n-2}\binom{n-2}{i}p^{2i}(1-p^2)^{n-2-i}p^{\binom{i}{2}} \\[5pt] & < n^2\Bigg((1+np^2+n^2p^5+n^3p^9+n^4p^{14}+n^5p^{20}){\mathrm{e}}^{-p^2(n-7)} + \sum_{i\geq 6}\big(np^{({i+3})/{2}}\big)^i\Bigg) \\[5pt] & = O(n^{-\varepsilon}\log n)=o(1). \end{align*}
Thus, a.a.s.,
$X=0$
and
$T_1(\Gamma)$
is connected.
3.4. Implications for the geometry of the random RACG
Let
$\Gamma$
be any graph. The following notion of a bonded square was introduced in [Reference Fioravanti, Levcovitz and Sageev21]: an induced square X in
$\Gamma$
is bonded if there exists an induced square X
′ in
$\Gamma$
such that X and X
′ have exactly three vertices in common. In other words, an induced square with diagonals f and f
′ is bonded if and only if there exists some vertex
$v\notin f\cup f'$
sending edges to both endpoints of exactly one of f and f
′ (and thus sending at least one non-edge to the other diagonal).
One of the main results in [Reference Fioravanti, Levcovitz and Sageev21, Corollary C] established that if every square in a graph
$\Gamma$
is bonded, then the associated RACG
$W_{\Gamma}$
satisfies coarse cubical rigidity, and every cocompact cubulation of
$W_{\Gamma}$
induces the same coarse median structure on
$W_{\Gamma}$
as the one given by its Davis complex. They further suggested that this should be an if and only if, i.e. that the existence of non-bonded squares implies non-uniqueness of the coarse cubical median structure on
$W_{\Gamma}$
, though they were unable to prove this.
We now show how a slight modification of our proof of Theorem 1(ii) allows us to obtain a threshold for the disappearance of non-bonded squares in
$\Gamma\sim \mathcal{G}_{n,p}$
and thereby for coarse cubical rigidity.
Proof of Theorem
2. Let
$\Gamma\sim \mathcal{G}(n,p)$
. Given a 4-set S in
$V(\Gamma)$
, let
$X_S$
be the indicator function of the event that S induces a non-bonded square in
$\Gamma$
. For this event to hold, first,
$\Gamma[S]$
must induce a square, which occurs with probability
$3p^4(1-p)^2$
. Second, for every vertex
$v\notin S$
, if v sends edges to both ends of a diagonal of
$\Gamma[S]$
then it must in fact send edges to all four vertices in S; this occurs with probability
$1-2p^2(1-p^2)$
, independently at random for each
$v\in V(\Gamma)\setminus S$
. In particular, we have
\begin{align*} \mathbb{E}X_S & = 3p^4(1-p)^2(1-2p^2(1-p^2))^{n-4} \\[5pt] & \leq 3n^{-2}(np^2(1-p))^2\exp\!(\!-2(1+p)(np^2(1-p)) + O(1)). \end{align*}
Fix
$\varepsilon>0$
. For
$p=p(n)$
satisfying the bounds
\begin{align*}(1+\varepsilon)\frac{\sqrt{\log n}}{\sqrt{n}}\leq p \leq 1-(1+\varepsilon)\frac{\log n}{n},\end{align*}
we have that
$np^2(1-p) \geq (1+\varepsilon +o(1))\log n$
. It then follows from the monotonicity of
$x\mapsto x^2 \exp\!(\!-x)$
for
$x\in \mathbb{R}_{\geq 2}$
and the inequality above that
$\mathbb{E}X_S \leq O(n^{-4-2\varepsilon +o(1)})=o(n^{-4})$
.
Taking a union bound over all 4-sets S in
$V(\Gamma)$
and applying Markov’s inequality, we deduce that, for
$p(n)\in[(1+\varepsilon){\sqrt{\log n}}/{\sqrt{n}}, 1-(1+\varepsilon)({\log n})/{n}]$
we have that a.a.s.
$\sum_S X_S=0$
holds, i.e. that a.a.s. every square in
$\Gamma$
is bonded. Together with [Reference Fioravanti, Levcovitz and Sageev21, Corollary C], this implies the desired conclusion regarding the coarse cubical rigidity of
$W_{\Gamma}$
.
4. Concluding remarks
From the point of view of geometric group theory, this paper raises a number of questions, some probabilistic in nature and others not.
The graphs constructed in Section 2.3.1 came as somewhat of a surprise to the authors. These are very concrete examples, but the phenomenon of having multiple distinct square components each of full support is new, and we suspect that the RACG associated with these graphs may have other interesting geometric properties. We believe these examples warrant further investigation in the future.
As a juxtaposition to Theorem 2, we note that it has recently been shown that there are many right-angled Coxeter groups which admit uncountably many coarse median structures [Reference Mangioni27]. The examples there are beasts of a different form from the coarse cubical medians at play in our theorem, since they need not be cubical in nature and so in general can behave in a much wilder fashion. Moreover, while the RACGs this is shown for do not overlap with our examples, there is no a priori reason that a group with a unique cubical coarse median structure could not have uncountably many coarse median structures. Accordingly, it would be interesting to know whether those techniques (or others) could be adapted to answer the following question, for which we do not even know whether the answer is finite, countably infinite, or uncountable!
Question 2. The random RACG for p in the range given in Theorem 2 a.a.s. has a unique cubical coarse median structure. How many coarse median structures can it possess? Is this cardinality concentrated, and how does its distribution change as p varies?
There is a related question left open by our work.
Question 3. For what p does the random RAAG a.a.s. have a unique cubical coarse median structure? For p outside that range, how many cubical coarse median structures can it possess? Is this cardinality concentrated, and how does its distribution change as p varies?
As we were putting the finishing touches to this paper, [Reference Fioravanti and Sisto22] showed that some groups, with a mix of hyperbolic/Euclidean geometry different than that considered here, also have a unique coarse median (e.g. products of higher-rank free groups), further highlighting the potential interest of the two questions above.
From a probabilistic perspective, there are also a number of natural problems regarding the connectivity properties of
$T_1(\Gamma)$
,
$\Gamma\sim\mathcal{G}_{n,p}$
. Foremost among them is the question of whether a.a.s. as soon as a giant square component emerges, all other components have logarithmic size. We stated this more formally as Conjecture 1. Extending the investigation into the connectivity properties of
$T_1(\Gamma)$
, it is natural to ask how the diameter of that random graph behaves. The most basic question in this direction is as follows.
Question 4. What is the typical behaviour of the diameter of
$T_1(\Gamma)$
when
$\sqrt{2\log(n)/n}\leq p\leq 1-\omega(n^{-2})$
?
Heuristically, for
$p=o(1)$
in this range we expect the number of vertices of
$T_1(\Gamma)$
at distance d from a given vertex to grow like
$(n^2p^4/2)^d$
. This suggests the following behaviour may be likely:
-
(i) For
$p=\sqrt{f(n)/n}$
with
$(2+\varepsilon)\log n< f(n)$
and
$\log (f(n))=o(\!\log n)$
, the diameter of
$T_1(\Gamma)$
has a.a.s. size
$O((\!\log n) / \log f)$
. -
(ii) For every integer
$k \geq 2$
and
$n^{-{1}/{2}+{1}/{2k}}\ll p \ll n^{-{1}/{2}+{1}/({2(k-1)})}$
, the diameter of
$T_1(\Gamma)$
is a.a.s. exactly equal to k. -
(iii) For every integer
$k \geq 3$
and
$p=\theta(n^{-{1}/{2}+{1}/{2k}})$
, the diameter of
$T_1(\Gamma)$
is a.a.s. equal to k or
$k-1$
.
(Note that Proposition 8 establishes the behaviour in part (ii) above in the case
$k= 2$
.)
Finally, as a referee pointed out, it is very natural to ask whether we could hope for a hitting time version of Theorem 1. Suppose we add in edges one by one to an empty graph
$\Gamma_0$
on n vertices in a random order to obtain a nested sequence of graphs
$(\Gamma_k)_{k=0}^{\binom{n}{2}}$
. Is it the case that
$T_1(\Gamma_{k+1})$
becomes connected exactly as the last non-edge of
$\Gamma_{k}$
not contained in a 4-cycle disappears? This appears likely, but some care is needed: each edge we add to
$\Gamma_{k}$
destroys a vertex of
$T_1(\Gamma_k)$
in addition to creating new 4-cycles, so a proof may be delicate.
Acknowledgements
The initial discussions that led to this paper were carried out when the first author visited the second and third authors in Umeå in January 2023 at the occasion of the third Midwinter Meeting in Discrete Probability. The authors would like to express their gratitude to the editor and to the anonymous referees for their careful reading of the paper and their many helpful suggestions which helped improve its presentation.
Funding information
The hospitality of the Umeå mathematics department and the financial support of the Simons Foundation are gratefully acknowledged. In addition, the research of the second and third authors is supported by Swedish Research Council grant VR 2021-03687.
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.
Open access
