[proofplan]
The lower regime follows directly from the [Isolated Vertex Threshold](/theorems/2059): an isolated vertex disconnects the graph, so if isolated vertices appear with probability tending to $1$, connectivity fails. For the upper regime, we bound the probability of a disconnection by a union bound over all "witness" cuts: if $G$ is disconnected, some set $A$ with $1 \leq |A| \leq n/2$ has no edges to its complement. We split the union bound at $k = \varepsilon n/4$: for small $k$, we use $\binom{n}{k} \leq n^k$ and $1 - p \leq e^{-p}$ to bound each summand by $n^{-3k\varepsilon/4}$; for large $k$, we use $\binom{n}{k} \leq 2^n$ and $k(n-k) \geq \varepsilon n^2/8$ to show the whole tail decays exponentially.
[/proofplan]
[step:Deduce the lower regime from the isolated vertex threshold]
Assume $p \leq (1-\varepsilon)\frac{\log n}{n}$. By the [Isolated Vertex Threshold](/theorems/2059), in this regime
\begin{align*}
\mathbb{P}(G \text{ has an isolated vertex}) \to 1 \quad \text{as } n \to \infty.
\end{align*}
A graph containing an isolated vertex $v$ has $\{v\}$ as a component disjoint from every other vertex, hence is disconnected whenever $n \geq 2$. Therefore
\begin{align*}
\{G \text{ has an isolated vertex}\} \subseteq \{G \text{ is disconnected}\},
\end{align*}
so $\mathbb{P}(G \text{ is connected}) \leq \mathbb{P}(G \text{ has no isolated vertex}) \to 0$.
[/step]
[step:Reduce disconnection to the existence of a small empty cut]
Assume $p \geq (1+\varepsilon) \frac{\log n}{n}$. Suppose $G$ is disconnected. Then $V(G)$ partitions into components; let $C$ be any component. Set $A := C$ if $|C| \leq n/2$, otherwise $A := V(G) \setminus C$. In either case $A$ is a proper non-empty subset of $V(G)$ with $1 \leq |A| \leq \lfloor n/2 \rfloor$, and there are no edges between $A$ and $V(G) \setminus A$ (any such edge would merge $C$ with another component, contradicting $C$ being a component).
Writing $e(A, V(G) \setminus A)$ for the number of edges of $G$ across the cut,
\begin{align*}
\{G \text{ is disconnected}\} \subseteq \bigcup_{\substack{A \subset V(G) \\ 1 \leq |A| \leq n/2}} \{e(A, V(G) \setminus A) = 0\}.
\end{align*}
For a fixed $A$ with $|A| = k$, the number of potential edges between $A$ and $V(G) \setminus A$ is $k(n - k)$; each is present independently with probability $p$, so
\begin{align*}
\mathbb{P}(e(A, V(G) \setminus A) = 0) = (1-p)^{k(n-k)}.
\end{align*}
By the union bound, summing over all $\binom{n}{k}$ subsets of size $k$ and all $k \in \{1, \ldots, \lfloor n/2 \rfloor\}$,
\begin{align*}
\mathbb{P}(G \text{ is disconnected}) \leq \sum_{k=1}^{\lfloor n/2 \rfloor} \binom{n}{k} (1-p)^{k(n-k)}.
\end{align*}
[guided]
A disconnected graph has at least two components. Pick any component $C$. Either $|C| \leq n/2$ or $|V(G) \setminus C| \leq n/2$ — in either case, taking $A$ to be the smaller of $C$ or its complement gives a set with $1 \leq |A| \leq n/2$.
Why no edges between $A$ and $V(G) \setminus A$? If $A = C$, then by definition of component, no edges leave $C$. If $A = V(G) \setminus C$, then no edges cross from $V(G) \setminus C$ to $C$, which is the same condition. Either way, $e(A, V(G) \setminus A) = 0$.
So the event $\{G \text{ is disconnected}\}$ is contained in the union, over all $A$ with $1 \leq |A| \leq n/2$, of $\{e(A, V(G) \setminus A) = 0\}$. By the union bound:
\begin{align*}
\mathbb{P}(G \text{ is disconnected}) \leq \sum_A \mathbb{P}(e(A, V(G) \setminus A) = 0).
\end{align*}
The probability of the event $\{e(A, V(G) \setminus A) = 0\}$ depends only on $k = |A|$: it's $(1-p)^{k(n-k)}$, since there are $k(n-k)$ possible cross edges and each must be absent (independently). Grouping by size gives the binomial sum above.
A subtlety: we use *unordered* subsets (the cut defined by $A$ is the same as the cut defined by $V(G) \setminus A$). The restriction $|A| \leq n/2$ avoids double-counting the same cut when $|A| \neq n/2$; for $|A| = n/2$ (only if $n$ is even), each cut is counted twice, but overcounting only worsens the bound, so we accept this.
[/guided]
[/step]
[step:Bound the small-$k$ part of the sum via $\binom{n}{k} \leq n^k$]
Split the sum at $k_0 := \lfloor \varepsilon n / 4 \rfloor$. For $k \leq k_0$, use $\binom{n}{k} \leq n^k$ and $1 - p \leq e^{-p}$:
\begin{align*}
\binom{n}{k}(1-p)^{k(n-k)} \leq n^k e^{-p k(n-k)} = \left(n e^{-p(n-k)}\right)^k.
\end{align*}
Since $k \leq \varepsilon n / 4$, we have $n - k \geq n(1 - \varepsilon/4)$, so
\begin{align*}
p(n-k) \geq (1+\varepsilon) \tfrac{\log n}{n} \cdot n(1 - \varepsilon/4) = (1+\varepsilon)(1 - \varepsilon/4) \log n.
\end{align*}
Computing $(1+\varepsilon)(1-\varepsilon/4) = 1 + \varepsilon - \varepsilon/4 - \varepsilon^2/4 = 1 + 3\varepsilon/4 - \varepsilon^2/4 \geq 1 + \varepsilon/2$ (for $\varepsilon \leq 1$, the second-order term is dominated). Therefore
\begin{align*}
n e^{-p(n-k)} \leq n \cdot n^{-(1 + \varepsilon/2)} = n^{-\varepsilon/2},
\end{align*}
and
\begin{align*}
\binom{n}{k}(1-p)^{k(n-k)} \leq n^{-k\varepsilon/2}.
\end{align*}
Summing over $k = 1, \ldots, k_0$,
\begin{align*}
\sum_{k=1}^{k_0} \binom{n}{k}(1-p)^{k(n-k)} \leq \sum_{k=1}^{\infty} n^{-k\varepsilon/2} = \frac{n^{-\varepsilon/2}}{1 - n^{-\varepsilon/2}} \leq 2 n^{-\varepsilon/2}
\end{align*}
for $n$ large enough that $n^{-\varepsilon/2} \leq 1/2$, and this tends to $0$.
[guided]
The idea: for "thin" cuts ($|A| \leq \varepsilon n/4$), we have $n - k \approx n$, so $k(n-k) \approx kn$. Each summand is
\begin{align*}
\binom{n}{k}(1-p)^{k(n-k)}.
\end{align*}
The $\binom{n}{k}$ factor is at most $n^k$ (a crude but sufficient bound). The $(1-p)^{k(n-k)}$ factor is at most $e^{-pk(n-k)}$. Multiplying:
\begin{align*}
n^k e^{-pk(n-k)} = \big(n \cdot e^{-p(n-k)}\big)^k.
\end{align*}
We aim to show this base is less than $1$, so the whole term decays geometrically in $k$.
With $k \leq \varepsilon n/4$, $n - k \geq (1 - \varepsilon/4) n$. Substituting $p \geq (1+\varepsilon) \log n / n$:
\begin{align*}
p(n-k) \geq (1+\varepsilon)(1-\varepsilon/4) \log n.
\end{align*}
Expanding: $(1+\varepsilon)(1-\varepsilon/4) = 1 + 3\varepsilon/4 - \varepsilon^2/4 \geq 1 + \varepsilon/2$ for $\varepsilon \in (0, 1]$ (since $3\varepsilon/4 - \varepsilon^2/4 = \varepsilon(3 - \varepsilon)/4 \geq \varepsilon/2$ iff $3 - \varepsilon \geq 2$ iff $\varepsilon \leq 1$).
Hence $n e^{-p(n-k)} \leq n \cdot n^{-(1 + \varepsilon/2)} = n^{-\varepsilon/2}$. The base of our geometric series is $n^{-\varepsilon/2}$, which tends to $0$. Summing the geometric series and bounding by its infinite version:
\begin{align*}
\sum_{k=1}^{k_0} n^{-k\varepsilon/2} \leq \frac{n^{-\varepsilon/2}}{1 - n^{-\varepsilon/2}} \to 0.
\end{align*}
[/guided]
[/step]
[step:Bound the large-$k$ part of the sum via $\binom{n}{k} \leq 2^n$ and $k(n-k) \geq \varepsilon n^2/8$]
For $k_0 < k \leq \lfloor n/2 \rfloor$, use $\binom{n}{k} \leq 2^n$. For $k \geq \varepsilon n / 4$ and $k \leq n/2$, we have $n - k \geq n/2$, hence $k(n-k) \geq (\varepsilon n/4)(n/2) = \varepsilon n^2 / 8$. Also $1 - p \leq e^{-p}$, so
\begin{align*}
\binom{n}{k}(1-p)^{k(n-k)} \leq 2^n e^{-p k(n-k)} \leq 2^n e^{-p \varepsilon n^2 / 8}.
\end{align*}
Substituting $p \geq (1+\varepsilon) \log n / n$,
\begin{align*}
p \varepsilon n^2 / 8 \geq (1+\varepsilon) \varepsilon n \log n / 8.
\end{align*}
The number of terms in the large-$k$ range is at most $n/2$, so
\begin{align*}
\sum_{k = k_0 + 1}^{\lfloor n/2 \rfloor} \binom{n}{k} (1-p)^{k(n-k)} &\leq \tfrac{n}{2} \cdot 2^n e^{-(1+\varepsilon)\varepsilon n \log n / 8} \\
&= \exp\!\left(\log(n/2) + n \log 2 - (1+\varepsilon)\varepsilon \tfrac{n \log n}{8}\right).
\end{align*}
The $n \log n$ term dominates $n \log 2$ and $\log(n/2)$ as $n \to \infty$, so the exponent tends to $-\infty$ and the sum tends to $0$.
[guided]
For "thick" cuts ($|A| \geq \varepsilon n / 4$), both sides of the cut have size at least $\varepsilon n / 4$ and at most $n(1 - \varepsilon/4)$, so the product $k(n - k)$ is of order $n^2$. Specifically, $k \geq \varepsilon n / 4$ and $n - k \geq n/2$ give
\begin{align*}
k(n-k) \geq \frac{\varepsilon n}{4} \cdot \frac{n}{2} = \frac{\varepsilon n^2}{8}.
\end{align*}
The probability of no cross edges is thus at most $e^{-p \varepsilon n^2 / 8}$, an exponentially small quantity.
The number of subsets $A$ of size $k$ in the large range is at most $2^n$ (total subsets). The number of sizes is at most $n/2$. So
\begin{align*}
\sum_{k = k_0 + 1}^{\lfloor n/2 \rfloor} \binom{n}{k}(1-p)^{k(n-k)} \leq \frac{n}{2} \cdot 2^n \cdot e^{-p \varepsilon n^2 / 8}.
\end{align*}
Taking logs:
\begin{align*}
\log\!\left(\frac{n}{2} \cdot 2^n e^{-p\varepsilon n^2 / 8}\right) = \log(n/2) + n \log 2 - p \varepsilon n^2 / 8.
\end{align*}
Using $p \geq (1+\varepsilon)\log n / n$:
\begin{align*}
p \varepsilon n^2 / 8 \geq (1+\varepsilon) \varepsilon n \log n / 8.
\end{align*}
This grows like $n \log n$, which dominates the $n \log 2$ term (linear in $n$) and the $\log(n/2)$ term (logarithmic). So the exponent tends to $-\infty$ and the entire sum vanishes.
Intuition: there are at most $2^n$ bipartitions, each contributing a probability of order $e^{-p n^2}$ for the cut being empty. Since $p n^2 \gg n$, the exponential wins handily over the count.
[/guided]
[/step]
[step:Combine the two parts to conclude]
By the union bound and the previous two steps,
\begin{align*}
\mathbb{P}(G \text{ is disconnected}) &\leq \sum_{k=1}^{k_0} \binom{n}{k}(1-p)^{k(n-k)} + \sum_{k=k_0+1}^{\lfloor n/2 \rfloor}\binom{n}{k}(1-p)^{k(n-k)} \\
&\to 0 + 0 = 0.
\end{align*}
Hence $\mathbb{P}(G \text{ is connected}) \to 1$. Together with the lower regime from the first step, this establishes the claimed dichotomy and completes the proof.
[/step]
