Return to 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 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. 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 \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}$.
  
  

• 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).

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 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.) Any pointers would be much appreciated.

Is there an understanding of the emergence and 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, 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 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 \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 there only exists a cycle with certainty as $p \nearrow \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 ~~+~~ O(1/n)$, 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).

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 isn't hard to show that for constant $p$, the expected number of 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 presence of "multcyclic" components becomes probable, and there will be another threshold at which components with a finite number of cycles become improbable again (somewhere below $p = 1 - \omega(n^{-1/2d})$, which I think is the limit at which the graph $G_p^d$ becomes almost surely connected for $d \in \{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.

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 (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 $p = \frac{1}{2}$, the emergence of unicyclic components is fairly easy to show to be $p \in \omega(n^{-1/4})$; the rest is not so obvious.) Any pointers would be much appreciated.

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 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.) Any pointers would be much appreciated.