|
5
|
|
|
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
|
|
|
|
|
|
|
|
|
3
|
|
|
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.
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}$.
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
|
|
|
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.
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}$.
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 for of $d \in p = \{2,3\}$, it seems easy to show frac{1}{2}$, the emergence of unicyclic components in either $G_\ell^2$ or $G_\ell^3$ at is fairly easy to show to be $p \in \Omega(n^{-1/4})$; omega(n^{-1/4})$; the rest is not so obvious.) Any pointers would be much appreciated.
|
|
|
|
|
1
|
|
|
Expected number of components with multiple cycles in a subgraph of a square lattice
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.
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}$.
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 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.
|
|
|
