Square percolation and the threshold for quadratic divergence in random right-angled Coxeter groups

In Section 3 we provide additional background material on the geometry of random groups and derive Theorem 1.6 from Theorems 1.4–1.5. In Section 4, we recall some basic facts about branching processes and give an outline of the proof strategy we follow for our main results, and of the ways in which it departs from the framework used by Bolloás and Riordan in their study of clique percolation in random graphs. Theorem 1.4 is proved in Section 5, while Theorem 1.5 is derived in Section 6. We end the paper in Section 7 with some discussion of the results and of further work and related problems.

The authors thank Mark Hagen for discussions during the early stages of this work. Behrstock was supported by NSF grant DMS-1710890. Falgas-Ravry was supported by Swedish Research Council grant VR 2016-03488. The authors thank Ela Behrstock for her skillful rendering of Figures 2 and 2. Aspects of this work were motivated by output from software written by the authors (available upon request from the authors, some available online at http://comet.lehman.cuny.edu/behrstock/random.html). Accordingly, this research was supported, in part, by a grant of computer time from the City University of New York High Performance Computing Center under NSF Grants CNS-0855217, CNS-0958379, and ACI-1126113.

Recall that the graph joint $\Gamma_{1}\ast\Gamma_{2}$ of two graphs $\Gamma_{1}$ and $\Gamma_{2}$ is the graph obtained by taking disjoint unions of $\Gamma_{1}$ and $\Gamma_{2}$, and adding in all edges from $\Gamma_{1}$ to $\Gamma_{2}$.

Dani–Thomas were the first to introduce a special case of the $\mathcal{CFS}$ property for triangle-free graphs in [8]. The $\mathcal{CFS}$ property for arbitrary graphs was then studied by Hagen and the authors in [5], with an eye towards establishing when this property holds a.a.s. in random graphs, while in [15] Levcovitz studied the geometric properties of right-angled Coxeter groups whose presentation graphs do not possess the $\mathcal{CFS}$ property.

With Hagen, the authors determined in  [5] the threshold for the $\mathcal{CFS}$ property to hold a.a.s. in Erdős–Rényi random graphs up to a polylogarithmic factor.

The $\mathcal{CFS}$ property is closely linked to the large scale geometry of right-angled Coxeter groups, connected to divergence and (strong algebraic) thickness. Divergence is a quasi-isometry invariant of groups introduced by Gersten [12] and further developed by Druţu, Mozes and Sapir [10], while thickness was introduced by Behrstock–Druţu–Mosher in [4] and then further refined by Behrstock–Druţu in [3]. We define these notions and explain how they are related below.

Given two non-decreasing functions $f,g\colon\mathbb{N}\to\mathbb{R}^{+}$, we say that $f\lesssim g$ if there exists $C\geq 1$ so that:

and we say $f\sim g$ if $f\lesssim g$ and $g\lesssim f$. Importantly, two polynomials that are non decreasing $\mathbb{N}\to\mathbb{R}^{+}$ and have the same degree are equivalent under this relation, and further for $a,b\in\mathbb{N}$ we have $x^{a}\sim x^{b}$ if and only if $a=b$.

When $X$ is the Cayley graph of a right-angled Coxeter group, it is straightforward to see that $\delta_{\rho}(r)\sim\delta_{1}(r)$. Therefore when we are referring to the divergence function of $W_{\Gamma}$, we will mean $\delta_{1}(r)$. We say that a RACG $W_{\Gamma}$ has quadratic divergence if $\delta_{1}(r)\sim r^{2}$ and linear divergence if $\delta_{1}(r)\sim r$.

Behrstock and Druţu discovered that the order of thickness provides upper bounds on the divergence of a metric space. In particular they proved:

The group theoretic motivation for studying the $\mathcal{CFS}$ property is that it provides a graph theoretical proxy for certain geometric properties of right-angled Coxeter groups, such as their divergence. To see that $W_{\Gamma}$ has quadratic divergence when $\Gamma$ has the $\mathcal{CFS}$ property is straightforward, since interpreting the definition of $\mathcal{CFS}$ in the Cayley graph yields a chain of linearly many spaces with linear divergence with each intersecting the next in an infinite diameter set. Indeed, it is an immediate consequence of the definitions that if if $G$ is the direct product of two infinite groups then $G$ has linear divergence, just as a path avoiding a linear-sized ball in the plane has linear length. Hence every finitely generated abelian group of rank at least $2$ has linear divergence (and is thick of order $0$).

Now, if $\Gamma=K\star\Gamma^{\prime}$ where $K$ is a clique, then $W_{\Gamma}\cong\mathbb{Z}_{2}^{|K|}\times W_{\Gamma^{\prime}}$. In such a case $W_{\Gamma^{\prime}}$ is a finite-index subgroup of $W_{\Gamma^{\prime}}$ and thus, up to finite index, we can assume that $\Gamma$ does not contain a vertex sending an edge to all other vertices of $\Gamma$.

Now, $W_{\Gamma}$ contains a network of convex subgroups generated by the induced square in the full-support component of $\square(\Gamma)$. Each of these groups is virtually $\mathbb{Z}^{2}$, that is to say has a finite index subgroup which is a copy of $\mathbb{Z}^{2}$. Further, two induced squares in $\Gamma$ correspond to incident edges in $\square(\Gamma)$ if and only if the intersection of the associated virtual $\mathbb{Z}^{2}$ subgroups is virtually $\mathbb{Z}$, that is to say has a finite index subgroup which is a copy of $\mathbb{Z}$.

Thus, paths in the full-support component of $\square(\Gamma)$ give the connecting sequences needed in Definition 3.4. Hence if $\Gamma$ has the $\mathcal{CFS}$ property, $W_{\Gamma}$ is thick of order at most $1$ and has at most quadratic divergence.

As shown by Dani–Thomas in the triangle-free case [8, Theorem 1.1 and Remark 4,8], and by the present authors with Hagen in the general case (as above) [5, Proposition 3.1], if $\Gamma$ has the $\mathcal{CFS}$ property then the associated right-angled Coxeter group $W_{\Gamma}$ has thickness of order at most $1$, and hence has at most quadratic divergence. Further, in [6], Behrstock, Hagen and Sisto show that a right-angled Coxeter group $W_{\Gamma}$ has linear divergence (and is thick of order $0$) if and only if $\Gamma$ is the join of two non-complete graphs. Finally Levcovitz proved that any graph without $\mathcal{CFS}$ has at least cubic divergence [15], and so we see that $W_{\Gamma}$ has exactly quadratic divergence if and only if $\Gamma$ is not the join of two non-complete graphs and has the $\mathcal{CFS}$ property.

Assuming our main theorems about square percolation, Theorems 1.4 and 1.5, we are now in a position to provide a proof of Theorem 1.6 on the threshold for quadratic divergence in RACGs:

We recall here some basic facts and definitions from the theory of branching processes that we will use in our argument; for a more general treatment of such processes, see e.g. [2].

A Galton–Watson branching process can be viewed as a random rooted tree: in the zero-th generation there is a root or ancestor, who begets a random number $X_{1,1}\sim X$ of children that form the first generation. In every subsequent generation, each child independently begets a random number of children, with the $i$-th member of generation $t$ begetting $X_{i,t}\sim X$ children.

Galton–Watson branching processes are a widely studied family of random processes and are the subject of much probabilistic research; see e.g. [2] and the references therein. Here we introduce only some fairly standard elements of the theory that are needed for our argument. A Galton–Watson process $\mathbf{W}$ is said to become extinct if $W_{t}=0$ for some $t\in\mathbb{N}$. The total progeny of $\mathbf{W}$ is the total number of vertices in the associated tree, which we denote by $W=\sum_{t=0}^{\infty}W_{t}$; this quantity is finite if and only if $\mathbf{W}$ becomes extinct.

A key tool in the study of $\mathbf{W}$ is the generating function of its offspring distribution, $f_{X}(t)=\mathbb{E}t^{X}$. The following standard results from the theory of branching processes relate the probability of extinction for $\mathbf{W}$ to the mean and generating function of its offspring distribution $X$.

Bollobás and Riordan in [7] developed a powerful branching process framework for the study of clique percolation. Much of that framework can be adapted to the study of the non-induced square percolation we are concerned with in this paper. However there remains a number of significant hurdles which need to be overcome in order to extend their techniques to the present setting.

In the subcritical regime, the structure of squares makes the analysis of exceptional edges and offspring distributions (which are the crux of the argument) differ significantly from the Bollobás–Riordan paper; care is needed to handle the resulting complications correctly. Indeed, Bollobás and Riordan are able to model clique percolation using a Galton–Watson branching process whose offspring distribution is roughly Poisson; however, for square percolation, the offspring distribution is more heavy-tailed, forcing us to resort to somewhat delicate technical arguments.

Further, in the supercritical regime, because of our motivation from geometric group theory, we are interested in the study of induced square percolation. In particular, adding new edges to a graph could destroy some induced squares and hence split apart square-components even as we are trying to build a giant square-component. This situation is quite unlike that in clique percolation, and we have to use a completely different sprinkling argument to obtain our results (inter alia sprinkling vertices rather than edges). Thus here again there are significant complications and major departures from Bollobás and Riordan’s framework in [7].

Our results rely on the analysis of a branching process exploration of the square-components of a graph $\Gamma\in{\mathcal{G}}(n,p)$ for some fixed $p=\lambda n^{-1/2}$ where $\lambda>0$.

We begin with an arbitrary induced square $S_{1}=abcd$ in $\Gamma$. Its diagonals $ac$ and $bd$ give us two pairs of non-edges which can be used to discover further non-edges of $\Gamma$ belonging to the same square-component. The size of the set $\left(\Gamma_{a}\cap\Gamma_{c}\right)\setminus\{b,d\}$ of common neighbors of $a$ and $c$ in $V(\Gamma)\setminus\{b,d\}$ is a binomially distributed random variable $Z\sim\mathrm{Binom}(n-4,p^{2})$. Assuming that $\Gamma_{a}\cap\Gamma_{c}$ is an independent set (i.e., contains no edge of $\Gamma$) these common neighbors together with $b,d$ give rise to $\binom{Z+2}{2}$ non-edges that lie in the same square-component as $ac$; however, since we already knew about the pair $bd$, only $X=\binom{Z+2}{2}-1$ of these are new. We then pursue our exploration of the square-component of $ac$ by iterating this procedure: for each as-yet untested non-edge $xy$ in our square-component, we can first find the common neighbors of $xy$, and add as “children” of $xy$ all the new non-edges discovered in this way.

This can be viewed as a Galton–Watson branching process $\mathbf{W}$ with offspring distribution $X$ in a natural way. Assuming the past exploration does not greatly interfere with the distribution of the number of children in our process, the expected number of children at each step is roughly equal to

The expected value of $X$ is readily computed from the first and second moments of the binomial distribution of $Z$, yielding

The Galton–Watson process $\mathbf{W}$ becomes critical when the expectation of its offspring distribution is $1$. Solving

and selecting the non-negative root $\lambda_{c}=\sqrt{\sqrt{6}-2}=0.6704\ldots$, we thus see that for for any fixed $\lambda<\lambda_{c}$, our branching process $\mathbf{W}$ is subcritical. We thus expect it to terminate a.a.s. after a fairly small number of steps, from which one can hope to, in turn, deduce that a.a.s. all square-components are small. On the other hand, for any fixed $\lambda>\lambda_{c}$, $\mathbf{W}$ is supercritical, and with probability strictly bounded away from zero it does not terminate before we have discovered a reasonably large number of non-edges. A second-moment argument can then be used to show that a strictly positive proportion of non-edges must lie in reasonably large square-components. With a little glueing work, we can then hope to show that in fact a strictly positive proportion of non-edges lie in a giant square-component that covers all the vertices of $\Gamma$.

The above is however a simplification of what is actually required to make the arguments go through, and the situation turns out to be considerably more nuanced than what we described above. A first issue is our assumption that the vertices in $Z$ form an independent set: in the subcritical regime, we need to consider what happens if the set $Z$ of common neighbors of some non-edge $xy$ which we are testing interacts with some other previously discovered vertices, or with vertices in $Z$. In particular, any “exceptional” edge from $Z$ to previously discovered vertices other than $x$, $y$ could potentially create many additional squares, and hence add many new pairs to our square-component which are not accounted for by our branching process. Bollobás and Riordan faced a similar problem in their work on clique percolation. However, as stated in the previous subsection, the way they dealt with “exceptional edges” does not quite work for us in the square percolation setting. One issue is that in a copy of $C_{4}$, vertices on opposite sides of a diagonal are not adjacent, so that the number of $4$-cycles created by an exceptional edge cannot always be bounded by the degree of a newly discovered vertex. In addition, we note that if it is not dealt with properly, the presence of exceptional edges could significantly affect the future distribution of the number of children in our branching process: if in the example above $a,c$ had three common neighbors among the already discovered vertices rather than two, then the correct number of children for $ac$ in the exploration process would be $\binom{Z+3}{2}-3=\binom{Z+2}{2}-1+Z$, which has expectation equal to $1+\lambda_{c}^{2}>1$ when $\lambda=\lambda_{c}$. Finally, for the argument to work, we need not only for a Galton–Watson branching process with offspring distribution $X$ to become a.a.s. extinct within a few generations (which is an easy first moment argument): we also need its total progeny to be a.a.s. small. Here the fact that $X$ is a quadratic function of the binomial random variable $Z$ (and thus rather heavy-tailed) causes complicated issues, which were not faced in [7] (where the offspring distribution was essentially Poisson with mean $<1$). Overcoming these problems is the main work done in Section 5.

Secondly, in the supercritical argument, after establishing the a.a.s. existence of many non-edges in reasonably large square-components, we must prove the a.a.s. existence of a giant square-component covering all vertices and a strictly positive proportion of non-edges of $\Gamma$. Here the crucial point is that, because of the applications in geometric group theory motivating our work, we are considering induced square percolation. The size of a largest square-component in $\Gamma$ is not monotone with respect to the addition of edges to the graph — adding an edge could very well destroy an induced square, thus potentially breaking a large square-component in to several smaller pieces. So we have to use a completely new sprinkling argument to be able to agglomerate all “reasonably large” square-components into a single giant square-component. To do this we reserve some vertices for sprinkling, rather than edges. We use these vertices to build bridges between reasonably large square-components in a sequence of rounds until all such components are joined into one. Finally once we have established the a.a.s. existence of a giant square-component, some care is needed to ensure this square-component covers every vertex of $\Gamma$. Assembling a giant square-component and ensuring it has full support in this way involves overcoming a number of interesting obstacles, and is the main work done in Section 6.

Our exploration process will proceed by considering the following for each time $t\geq 0$:

• •

  (Discovered vertices.) An ordered set of vertices: $D_{t}=\{v_{1},v_{2},\ldots,v_{d_{t}}\}$.

• •

  (Active pairs.) A set of pairs of vertices (ordered lexicographically with respect to the ordering on $D_{t}$): $A_{t}=\{x_{1}y_{1},x_{2}y_{2},\ldots,x_{a_{t}}y_{a_{t}}\}\subseteq D_{t}^{(2)}$.

• •

  (Discovered pairs.) A set of pairs of vertices: $S_{t}\subseteq D_{t}^{(2)}$.

• •

  (Explored edge set.) A set of edges: $E_{t}\subseteq D_{t}^{(2)}\cap E(\Gamma)$.

• •

  (Epoch.) An integer: $e_{t}\in\{0,1,2,3,4,5\}$.

These sets will satisfy:

• ($\star$)

  for all $t\geq 0$ and for every active pair $x_{i}y_{i}\in A_{t}$, the vertices $x_{i}$ and $y_{i}$ have either $0$ or $2$ common neighbors in the graph $(D_{t},E_{t})$.

The initial state of the exploration consists of the following data, which is seeded by a choice of $v_{1}v_{2}$, an arbitrary pair of vertices from $V(\Gamma)$ (note that this pair can, alternatively, be thought of as a vertex of $\boxtimes(\Gamma)$). We set $D_{0}=\{v_{1},v_{2}\}$, $A_{0}=S_{0}=\{v_{1}v_{2}\}$, $E_{0}=\emptyset$ and $e_{0}=0$.

At each time step $t$ our exploration proceeds as follows, with $\varepsilon$ as given in equation (5.1):

1. 1.

   If $|D_{t}|<2^{2^{10}}\varepsilon^{-2^{10}}(\log n)^{2^{31}}$ and $A_{t}\neq\emptyset$, let $a={x}{y}$ be the first pair in $A_{t}$. For each $z\in V(\Gamma)\setminus D_{t}$ we test whether or not $z$ sends an edge in $\Gamma$ to both vertices of $a$. Set $Z_{t}:=\{z\in V(\Gamma)\setminus D_{t}:\ {z}{x},{z}{y}\in E(\Gamma)\}$ and $F_{t}$ to be the collection of joint neighbors of $x$ and $y$ in $(D_{t},E_{t})$. (Note, by property $(\star)$, the set $F_{t}$ is either empty or consists of a pair of discovered vertices.)

   We arbitrarily order the vertices in $Z_{t}$ as $\{v_{d_{t}+1},v_{d_{t}+2},\ldots,v_{d_{t+1}}\}$, and add them to $D_{t}$ to form $D_{t+1}$. We then set

   $$A_{t+1}=\left(A_{t}\cup\left(F_{t}\cup Z_{t}\right)^{(2)}\right)\setminus\left(a\cup F_{t}^{(2)}\right)$$

   to be the new collection of active pairs (which again is ordered lexicographically with respect to the ordering on $D_{t}$), set $E_{t+1}=E_{t}\cup\{zx,zy:\ z\in Z_{t}\}$, set $e_{t+1}=e_{t}$, $S_{t+1}=S_{t}\cup A_{t+1}$ and then proceed to the next time step $t+1$ of the process. Note that since the only new edges being added are ones connecting a new vertex to $x$ and $y$ and since $xy\notin A_{t+1}$ each pair in $A_{t+1}$ has either $0$ or $2$ common neighbors in $(D_{t+1},E_{t+1})$, i.e., property ($\star$) is still satisfied in the next time-step.

2. 2.

   If $|D_{t}|\geq 2^{2^{10}}\varepsilon^{-2^{10}}(\log n)^{2^{31}}$, then we terminate the process and declare large stop.

3. 3.

   If $|D_{t}|<2^{2^{10}}\varepsilon^{-2^{10}}(\log n)^{2^{31}}$ and $A_{t}=\emptyset$, then we consider $i=|E(\Gamma[D_{t}])\setminus E_{t}|$.

   If $i=0$ or $e_{t}+i\geq 5$, then we terminate our exploration process and declare extinction stop or exceptional stop, respectively.
   Otherwise we set $e_{t+1}=e_{t}+i$, update $E_{t}$ by setting $E_{t}=E(\Gamma[D_{t}])$, and set $i_{1}=i$ (which by assumption is $>0$). We then run the following subroutines:

   1. 3A.

      Set

      $$Z^{1}_{t}:=\{z\in V(\Gamma)\setminus D_{t}:\ z\textrm{ sends at least three edges into }D_{t}\}.$$

      We then update our value of $i_{1}$, setting $i_{1}=|Z^{1}_{t}|$.

      • •

        If $i_{1}>0$ and $e_{t+1}+i_{1}>5$, then we terminate the whole exploration process and declare exceptional stop.

      • •

        Else if $i_{1}>0$ and $e_{t+1}+i_{1}\leq 5$, we add $Z^{1}_{t}$ to $D_{t}$, update $E_{t}$ by setting $E_{t}=E(\Gamma[D_{t}])$, update $S_{t}$ by setting $S_{t}=D_{t}^{(2)}$. We then update $e_{t+1}$ to $e_{t+1}+i_{1}$ and run through subroutine 3.3A. again.

      • •

        Otherwise $i_{1}=0$ and we proceed to subroutine 3.3B.

   2. 3B.

      Let

      $$Z^{2}_{t}:=\{z\in V(\Gamma)\setminus D_{t}:\ z\textrm{ sends at least two edges into }D_{t}\},$$

      Since subroutine 3A. terminated with $i_{1}=0$ each vertex in $Z^{2}_{t}$ sends exactly two edges into $D_{t}$. We set $D_{t+1}=D_{t}\cup Z^{2}_{t}$, and let $A_{t+1}$ consist of all pairs of vertices in $D_{t+1}$ containing at least one vertex of $Z^{2}_{t}$. Further, we set $S_{t+1}=S_{t}\cup A_{t+1}$.

      Once this is done, we proceed to the next time-step $t+1$ in the overall exploration process, observing that property $(\star)$ has been preserved (since by construction every vertex in $Z^{2}_{t}$ has degree exactly two in $(D_{t+1},E_{t+1})$).

The exploration process defined in the previous subsection can terminate for one of three reasons:

1. (1)

   $|D_{t}|\geq 2^{2^{10}}\varepsilon^{-2^{10}}(\log n)^{2^{31}}$ (large stop);

2. (2)

   $e_{t}\geq 5$ (exceptional stop);

3. (3)

   $A_{t}=\emptyset$ and $E_{t}=\Gamma[D_{t}]$ (extinction stop).

It follows from the above that the process must in fact terminate within $O\left((\log n)^{2^{32}}\right)$ time-steps. We begin our analysis by noting that, given our aim of proving Theorem 1.4, extinction stops are good for us: