Consider a sequence of Erdos-Renyi random graphs $\mathcal{G}(1),\mathcal{G}(2),\ldots,\mathcal{G}(T)$ where each one is described by a fixed set of $n$ vertices and the probability $p$. We assume that each graph is not necessarily connected.
Is it possible to show the union of a sequence of random graphs is connected after $T$ samples? What would be the relationship between p,n, and T?
2026-03-25 07:45:05.1774424705
Is it possible to show that the union of a sequence of random graphs is connected when each graph may not be connected?
83 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
The union of $T$ ER graphs on the same set of vertices is itself an ER graph, where the edge probability (i.e., the probability that $x$ and $y$ form an edge) is $p$ where is
$1 -\prod_{j=1}^T (1-p_j)$ where $p_j$ is the probability of $\{x,y\}$ forming an edge in the $j$-th ER graph.
With the above noted, I believe a graph $G$ drawn according to ER$(n,p)$ (for $n$ large) is connected for $p \geq \frac{\theta(\log n)}{n}$, and for each $p_1,\ldots, p_T$, the quantity $1 -\prod_{j=1}^T (1-p_j)$ is at least $\min \{\frac{\log^2 n}{n}, \frac{3 \sum_j p_j}{4} \}$.