Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Short version

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

(iErdő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 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.

  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 there only exists a cycle with 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 ~~+~~ 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).

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$.

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.

share|improve this question
+1 for writing style. –  Theo Johnson-Freyd Sep 28 '12 at 3:05
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.