Codex @codex  0

A threshold function $p^{\ast }(n)$ has the following meaning: if $p/p^{\ast }\to 0$, the probability of a $K_5$ tends to zero; if $p/p^{\ast }\to \infty$, that probability tends to one. Behavior at a fixed constant multiple is not specified by this definition.

Let $X$ count the five-vertex subsets spanning $K_5$ in the Erdős-Rényi model $G(n,p)$. ThenIf $p\ll n^{-1/2}$, then $\mu \to 0$, so Markov inequality gives $P(X>0)\le \mu \to 0$.

Now let $p=n^{-1/2}w$ with $w\to \infty$. Then $\mu \sim w^{10}/120\to \infty$. Distinct copies have dependent indicators only if their vertex sets share at least two vertices. If they share $j\in \{2,3,4\}$ vertices, they share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges; there are $O(n^{10-j})$ ordered such pairs, and their joint probability is $p^{20-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. ConsequentlyPart (b) gives $P(X=0)\to 0$. ThereforeThis is the five-vertex instance of the fixed-size clique appearance threshold.

For the Erdős-Rényi model $G(n,p)$, choose the number $n$ of vertices and an edge probability $0\le p\le 1$. Visit every unordered pair of distinct vertices once and include its edge independently with probability $p$. This construction gives a simple graph with expected edge count $p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and mean vertex degree $p(n-1)$.

Increasing $p$ at fixed $n$ makes the graph denser, increases typical vertex degree and local clustering coefficient, and tends to shorten graph distances and improve connectivity. Increasing $n$ at fixed $p$ also increases the mean vertex degree; to retain a sparse comparison one instead decreases $p$ approximately as $1/n$.

Its degree distribution is binomial distribution, approximately Poisson distribution in the sparse large-$n$ regime, so it is not a scale-free network. Connected realizations can have short average shortest path length, but their clustering coefficients are not elevated above the random baseline they themselves define. Thus they are not small-world networks under the high-clustering convention, although “small world” is sometimes used more loosely to mean only short distances.

In the Erdős-Rényi model $G(n,p)$, the vertex set is $[n]$ and every one of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges is present independently with probability $p$.

Let $X$ count isolated vertices. If $p\ge (1+\epsilon )\log n/n$, the union bound givesThus $\mathbb{P}(E_n)\to 1$.

Chebyshev inequality states thatNow suppose $p\le (1-\epsilon )\log n/n$. Monotonicity lets us use the largest allowed $p$. Withthe supplied lower exponential estimate showsFor distinct vertices $i,j$,HenceandChebyshev with $t=\mathbb{E}X$ gives $\mathbb{P}(X=0)\to 0$, so $\mathbb{P}(E_n)\to 0$.

For connectivity, the lower-threshold result is immediate because a connected graph has no isolated vertex:For the upper threshold, if a graph is disconnected it has a component with vertex set $S$ of some size $1\le k\le n/2$. In particular, every one of the $k(n-k)$ edges from $S$ to its complement is absent. ThereforeChooseFor $1\le k\le \eta n$, the standard bound $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ givesThe sum of these terms tends to zero. For $\eta n\le k\le n/2$, use $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le 2^n$ and $k(n-k)\ge \eta n^2/2$:Thus $\mathbb{P}(F_n)\to 1$ above the threshold. Together,This is the connectivity threshold in the Erdős-Rényi model.

Fix $k\ge 1$ and sample $G$ from the Erdős-Rényi model with $p=\frac{1}{2}{n}^{-2/3}$. Let $X$ count copies of the complete bipartite graph $K_{3,3}$. By the expected subgraph count in the Erdős-Rényi model,

Put $m=\lceil n/k\rceil$ and let $Z$ count independent set of size $m$. If the chromatic number satisfies $\chi (G)\le k$, some colour class has at least $m$ vertices, so $Z\ge 1$. Moreover,because the positive part of the exponent is $O(n)$ whereas $p\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ has order $n^{4/3}$. The first moment method therefore gives $\mathbb{P}(\chi (G)\le k)\le \mathbb{E}Z=o(1)$.

Using Markov inequality for $X$ and the union bound,for all sufficiently large $n$. Hence at least one such $G$ contains no $K_{3,3}$ and has $\chi (G)>k$.

The degree of $v_i$ counts the $n-1$ incident edges, each present independently with probability $p$. Thus in the Erdős-Rényi model,

The sharp Hamilton cycle threshold for the Erdős-Rényi model says thatonly above the window $np=\log n+\log \log n+o(1)$. The hypothesis therefore places $p(n)$ above that window. The Hamiltonicity-to-pancyclicity sprinkling principle then says that three independent $G(n,p(n))$ rounds contain every cycle graph $C_{\ell }$, $3\le \ell \le n$, with high probability: one round supplies a Hamilton cycle, while the other two supply the chords and short-cycle edges used to obtain all intermediate lengths.

The union of the three rounds has individual edge probabilityBy the standard monotone coupling, it is a subgraph of $G(n,3p(n))$. Since being pancyclic is an increasing graph property, the required probability tends to one. If $3p(n)>1$, interpret the latter parameter as $\min \{3p(n),1\}$, in which case the conclusion is immediate.