MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
+1 for writing style. – Theo Johnson-Freyd Sep 28 '12 at 3:05

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.