5 revised wording, made minor changes to the question

Is there an understanding of the emergence , and the subsequent disappearance , of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the edge-probability increases, as in the same way that there is for Erdős–Rényi graphs?

## Longer version.

The occurance and prevalence of isolated trees, isolated graphs containing a single cycle ("unicyclic components"), and isolated graphs containing multiple cycles are quite well understood for Erdős–Rényi graphs, where each possible edge occurs independently with some probability $p$ which is a function of the number $n$ of nodes. , and we let $n \to \infty$. Below is a summary of what results may be found just in Erdős and Rényi's original paper on the subject.

• For $p \in \Theta(n)$, cycles of all lengths occur with non-zero probability, but there only approach exists a cycle with certainty as $p \nearrow \frac{1}{n}$.

• For $p ~<~ =~ \frac{1}{\tau}\ln(n)/n ~~+~~ (1 - \frac{1}{\tau})\ln \ln(n)/n ~~+~~ (y + o(1))/n$, where we may take any $y \in \mathbb R$O(1/n)$, trees of size$\tau$remain probable, but almost never occur for larger$p$; • Because As random subgraphs of the lattice have much less connectivity than Erdős–Rényi graphs (random subgraphs of the$n$-clique), the critical behaviour is much different; . For instance, it is not difficult isn't hard to show that one may obtain a finite probability of having isolated componnents for constant$p$, the expected number of finite size containing multiple components with two cycles in it is infinite. But we may expect some analogues to the Erdős–Rényi case: there will be a threshold at which the existence presence of "multcyclic" components becomes probable; , and there will be another threshold at which they components with a finite number of cycles become improbable , again (somewhere below$p = 1 - \omega(n^{-1/2d})$, which it seems to me I think is the limit at which the graph$G_p^d$becomes almost surely connected for$d \in \{2,3\}$(so that there are no more finite size components).{2,3\}$.)

Is there any literature on this topic, or a straightforward analysis which indicates when finite-sized unicyclic and multicyclic components arise and disappear? (Below the critical threshold for $d \in \{2,3\}$, it seems easy to show the emergence of unicyclic components in either $G_\ell^2$ or $G_\ell^3$ at $p \in \Omega(n^{-1/4})$; the rest is not so obvious.) And do trees survive longer than components with more than one cycle? Any pointers would be much appreciated.

4 Reverted to re-establish an edit I had previously made; then retagged
3 Rollback to Revision 1

## Short version

Is there an understanding of the emergence, and the subsequent disappearance, of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the edge-probability increases, as there is for Erdős–Rényi graphs?

## Longer version.

### (i) Erdős–Rényi graphs

The occurance and prevalence of isolated trees, isolated graphs containing a single cycle ("unicyclic components"), and isolated graphs containing multiple cycles are quite well understood for Erdős–Rényi graphs, where each possible edge occurs independently with some probability $p$ which is a function of the number $n$ of nodes. Below is a summary of what results may be found just in Erdős and Rényi's original paper on the subject.

1. For $p < \tfrac{1}{n}$, there is a.a.s. no connected component having more than one cycle; and the expected number/distribution of trees and cycles of various sizes is fairly well-understood as a function of $n$ and $p$ as $n \to \infty$. As $p$ increases up to $\frac{1}{n}$, the following occur:

• For $p \in \Omega(n^{-3/2})$, trees of more than two vertices begin to proliferate, with trees of size $\tau$ becoming only probable for $p \in \Omega(n^{-1 ~-~ 1/(\tau-1)})$;
• For $p \in \Theta(n)$, cycles of all lengths occur with non-zero probability, but only approach certainty as $p \nearrow \frac{1}{n}$.

2. Once $p > \frac{1}{n}$, a giant component emerges which is expected to have a number of cycles diverging to infinity; but the other components are still expected a.a.s. to have at most one cycle. Where cycles and trees emerged for $p < \frac{1}{n}$, they now begin to be subsumed into the giant component as $p > \frac{1}{n}$:

• For $p > \frac{1}{n}$, the number of isolated unicyclic components begins to decrease asymptotically to zero, and is a.a.s. zero for $p \in \omega(1/n)$.

• For $p ~<~ \frac{1}{\tau}\ln(n)/n ~~+~~ (1 - \frac{1}{\tau})\ln \ln(n)/n ~~+~~ (y + o(1))/n$, where we may take any $y \in \mathbb R$, trees of size $\tau$ remain probable, but almost never occur for larger $p$;

• For $p ~=~ \ln(n)/n ~+~ \omega(1/n)$, there are a.a.s. no components except for the giant (that is, the graph is connected).

Thus, for Erdős–Rényi graphs, there is a fairly well-developed theory as to the rise and fall of the prevalence of components which have a finite number of cycles in them.

### (ii) Random subgraphs of rectangular lattices

Define the graphs $\def\L{\mathsf L}\L_\ell^2$ and $\L_\ell^3$ on the vertex-sets \begin{align*} V(\L_\ell^2) &= \Bigl\{ (x,y) \in \mathbb Z^2 : ~0 \leqslant x,y < \ell ~\Bigr\} ~,\\ V(\L_\ell^3) &= \Bigl\{ (x,y,z) \in \mathbb Z^3 : ~0 \leqslant x,y,z < \ell ~\Bigr\}~, \end{align*} containing $n = \ell^2$ and $n = \ell^3$ vertices respectively, where in each graph two vertices are adjacent if the line segment between them has length exactly 1. I'm considering problems involving random subgraphs $G_p^{2} < \L_\ell^2$ and $G_p^{3} < \L_\ell^3$ of these lattices in which each edge is present independently with some probability $p > 0$.

Because random subgraphs of the lattice have much less connectivity than Erdős–Rényi graphs (random subgraphs of the $n$-clique), the critical behaviour is much different; it is not difficult to show that one may obtain a finite probability of having isolated componnents of finite size containing multiple cycles. But we may expect some analogues: there will be a threshold at which the existence of "multcyclic" components becomes probable; and there will be another threshold at which they become improbable, somewhere below $p = 1 - \omega(n^{-1/2d})$, which it seems to me is the limit at which the graph $G_p^d$ becomes almost surely connected for $d \in \{2,3\}$ (so that there are no more finite size components).

Is there any literature on this topic, or a straightforward analysis which indicates when finite-sized unicyclic and multicyclic components arise and disappear? (Below the critical threshold of for $p = d \frac{1}{2}$, in \{2,3\}$, it seems easy to show the emergence of unicyclic components is fairly easy to show to be in either$G_\ell^2$or$G_\ell^3$at$p \in \omega(n^{-1/4})$; Omega(n^{-1/4})$; the rest is not so obvious.) Any pointers would be much appreciated.

2 different tags
1