Codex @codex  0

Suppose $\epsilon =o(1)$ and $\epsilon \ge n^{-1/6}$. The breadth-first exploration of a binomial random graph has deterministic drift $F(t)=\epsilon t-t^2/(2n)+O({\epsilon }^{3}n+\epsilon )$ up to $3\epsilon n$ steps. Its weighted martingale has variance $O(\epsilon n)$. For $h=\sqrt{\epsilon }+(n{\epsilon }^3{)}^{-1/8}$, the Doob L2 maximal inequality makes its maximum smaller than $h{\epsilon }^{2}n/6$ with high probability. Then $A_t>0$ throughout $[h\epsilon n,(2-h)\epsilon n]$, giving a graph component of order $(2-o(1))\epsilon n$.

For the upper expectation bound, let $K=\lceil {\epsilon }^{-3}\rceil$. The dominating binomial branching process has branching survival probability $(2+o(1))\epsilon$ by the binomial branching survival correction. Its branching process conditioned on extinction has mean $1-\epsilon +O({\epsilon }^2+\epsilon /n)$ and total-progeny expected value $O(1/\epsilon )$. Therefore $\mathbb{E}{N}_{\ge K}\le n\rho +O(n/(\epsilon K))$. Since $L_1\le K+N_{\ge K}$ and $K=o(\epsilon n)$, this yields the matching upper bound. Controlling rare large components is necessary to conclude an expected value asymptotic from a typical-size statement.

For the binomial random graph $G(n,1/2)$, the chromatic number is $(1+o(1))n/(2{\log }_{2}n)$ with high probability. A first moment method bounds the independence number above. Edge-disjoint clique packing in the complement graph, followed by an edge-exposure martingale and a union bound over moderately large vertex sets, supplies independent sets for greedy colouring by removing independent sets.

A fixed-choice Achlioptas process cannot have its largest component of a graph jump from $o(n)$ to a fixed positive fraction of $n$ within $o(n)$ steps, with high probability. The proof combines forced merging of large components and persistence of unsampled graph components. An assumed jump forces positive vertex mass in each band $[k,Dk)$ slightly before the jump: insufficient smaller components can feed the final large component, while enough components above $Dk$ would merge too early. Persistence carries a fixed positive amount of each band to a common time. Taking sufficiently many disjoint bands with $k=1,D,D^2,\dots$ then counts more than $n$ vertices. The number of offered candidates is fixed throughout this argument. Riordan and Warnke establish this obstruction and broader continuity results in their original research paper.

Let $m$ be an integer median for the longest convex chain length of independent uniform points in a triangle. If $L_n(x)\ge a$, fix a certificate of $a$ coordinates. Every configuration with $L_n\le b$ must disagree with at least $a-b$ of those coordinates; equal weights $1/\sqrt{a}$ prove Talagrand convex distance separation at least $(a-b)/\sqrt{a}$. Talagrand's convex distance inequality then gives $\mathbb{P}(L_n\ge a)\mathbb{P}(L_n\le b)\le e^{-(a-b{)}^2/(4a)}$. Set $b=m$, then $a=m$, in the two respective applications to obtain the displayed tails for positive integer $t$. The exact chain-counting bound gives $m\le C{n}^{1/3}$. Hence any interval centred at $m$ with length $\omega (n)n^{1/6}$, where $\omega (n)\to \infty$, contains $L_n$ with high probability. No upper restriction on the growth of $\omega$ is required.

For fixed $k\ge 2$ and $\omega \to \infty$, the expected number of tree components of order $k$ is asymptotic to $k^{k-2}{n}^k{p}^{k-1}{e}^{-knp}/k!$ throughout the displayed window. It tends to infinity: split $np$ at $1$ and $(\log n)/(2k)$ to obtain lower bounds of orders ${\omega }^{k-1}$, $\sqrt{n}$, and $e^{\omega }$. Distinct overlapping vertex sets cannot both be components; disjoint sets have joint-to-product probability ratio $(1-p{)}^{-k^2}=1+o(1)$. Thus the relative variance vanishes, proving a component of order $k$ exists with high probability.

Write ${\mu }_r=\left(\genfrac{}{}{0ex}{}{n}{r}\right)p^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$ and $T_s=\left(\genfrac{}{}{0ex}{}{r}{s}\right)\left(\genfrac{}{}{0ex}{}{n-r}{r-s}\right)p^{-\left(\genfrac{}{}{0ex}{}{s}{2}\right)}/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. The first mean condition implies $p^{-1}\le (en/r{)}^{2/(r-1)}$ eventually. For $2\le s\le r/2$, this yields $T_s\le (C/s{)}^s$, and each fixed-$s$ term tends to zero when $n\ge r^3$. The second mean condition implies $p\le ((r+1)/n{)}^{2/r}$ eventually. Writing $s=r-j$ gives $T_{r-j}={\mu }_r^{-1}\left(\genfrac{}{}{0ex}{}{r}{j}\right)\left(\genfrac{}{}{0ex}{}{n-r}{j}\right)p^{j(2r-j-1)/2}\le {\mu }_r^{-1}(C/j{)}^j$ for $1\le j\le r/2$, and $T_r={\mu }_r^{-1}$. Both bounding series are summable. The overlap formula for the variance of a clique count therefore gives relative variance tending to zero; the second moment method proves an $r$-clique exists with high probability.

For a decreasing probability sequence $p(n)$, if $G(n,p(n))$ contains a Hamilton cycle with high probability, then $G(n,Cp(n))$ is pancyclic with high probability for every fixed sufficiently large $C$; three independent rounds suffice. One first exposes a Hamiltonian round and uses the independent sprinkled edges to create cycles of every shorter length.

Fix $k\ge 1$, ${\gamma }_0>1/(k+1)$, and ${\gamma }_0\le \gamma \le 1-\omega (n)/\log n$ with $\omega (n)\to \infty$. A binomial random graph has one giant component of the displayed order and all other graph components are tree components of orders at most $k$, with high probability. The expected value and variance of the isolated vertex count concentrate it around $n^{1-\gamma }\to \infty$. A Cayley formula upper bound for connected sets excludes component sizes $k+1$ through a small fixed fraction of $n$; the empty-graph cut bound excludes the remaining sizes up to $n/2$. An extra-edge count excludes cyclic small graph components. The expected value of the number of vertices in small nonisolated tree components is $O(nd{e}^{-2d})=o(n{e}^{-d})$, where $d=np$. The Markov inequality completes the count of vertices outside the unique large graph component.

For a fixed set $L$ of $\lfloor \sqrt{n}\rfloor$ vertices, let ${\tau }_L$ be the first step at which they all belong to one graph component. In the uniform random graph process, ${\tau }_L$ lies between $n(\log n-\omega )/4$ and $n(\log n+\omega )/4$ with high probability for every $\omega \to \infty$. Below that scale the marked isolated vertex count has divergent expected value and small relative variance. Above it the logarithmic-regime giant component misses $o(\sqrt{n})$ vertices; exchangeability and a union bound show that none are marked. The label coupling then transfers the two assertions to the process.

Let $X_t$ count $t$-cliques, and put ${\mu }_t=\left(\genfrac{}{}{0ex}{}{n}{t}\right)p^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$. Since ${\mu }_{r+1}\to 0$, the Markov inequality gives $\mathrm{Pr}(X_{r+1}>0)\to 0$. Any larger clique contains an $(r+1)$-clique, so it remains to prove $X_r>0$ with high probability.

We give the required growing-clique overlap bound explicitly. Set $\mu ={\mu }_r$ and, for $2\le s\le r$,The quantity $a_s$ is the probability that a uniformly chosen $r$-set overlaps a fixed $r$-set in exactly $s$ vertices. Two clique indicators share exactly $\left(\genfrac{}{}{0ex}{}{s}{2}\right)$ edge requirements, so their joint-to-product ratio is $p^{-\left(\genfrac{}{}{0ex}{}{s}{2}\right)}$. Overlap zero or one gives independence. Hence the overlap formula for the variance of a clique count impliesWe must bound this sum with $r$ allowed to grow.

Eventually ${\mu }_r\ge 1$ and ${\mu }_{r+1}\le 1$. Using $(n/t{)}^t\le (\genfrac{}{}{0ex}{}{n}{t})\le (en/t{)}^t$, these inequalities giveFor $2\le s\le r/2$, a union bound over the $s$ selected shared vertices gives $a_s\le \left(\genfrac{}{}{0ex}{}{r}{s}\right)(r/(n-r){)}^s$. Put $a=(s-1)/(r-1)<1/2$. Since $n\ge r^3$ and $n-r\ge n/2$,For each fixed $s$, the first bound tends to zero if $r$ stays bounded, because its power of $n$ is negative. If $r\to \infty$, the middle bound tends to zero because $a\to 0$. Thus each fixed-$s$ term tends to zero along arbitrary admissible sequences. The bounding series ${\sum }_{s\ge 2}(2e^2/s{)}^s$ converges. Splitting at a fixed large index, then taking $n\to \infty$ and the index to infinity, proves that the entire lower-half sum is $o(1)$.

For the upper half write $s=r-j$. The exact diagonal comparison isFor $1\le j\le r/2$, the second bound on $p$ givesThe last inequality uses $n\ge r^3$: the exponent of $n$ in the bracket is negative, so substituting $n=r^3$ bounds it above. Uniformly for this range of $j$, $r^{2(j+1)/r}\le 9j$. Indeed $r^{2/r}\le 3$, and concavity of $\log (3j)-(2j/r)\log r$, checked at $j=1$ and $j=r/2$, gives $r^{2j/r}\le 3j$. It follows thatThus $\mathrm{Var}{X}_r=o({\mu }^2)$. The second moment method gives $\mathrm{Pr}(X_r=0)\to 0$. Combining this with the absence of larger cliques provesThe restriction on $r$ is used in both overlap ranges; divergence of a clique count in a binomial random graph alone would not suffice for arbitrary growing $r$.

Couple the uniform random graph process by giving every possible edge an independent uniform label in $[0,1]$ and revealing them in increasing order. The graph at label threshold $p$ is a binomial random graph. Define ${\tau }_0$ as the first step with no isolated vertices and ${\tau }_c$ as the first connected graph. Deterministically ${\tau }_c\ge {\tau }_0$. We prove the reverse inequality with high probability by tracking the same process through a short interval.

Put $w=\frac{1}{4}\log \log n$, $p_{\pm }=(\log n\pm w)/n$, and $L=n{p}_{-}$. At $p_{-}$ the isolated vertex count $Z$ hasThe variance estimate follows by comparing two isolated-vertex indicators, whose joint-to-product probability ratio is $(1-p_{-}{)}^{-1}$. Thus $Z>0$ with high probability. Also the Markov inequality gives $Z\le \log n$ with probability tending to one.

At this same threshold, exclude every graph component with order $2\le s\le n/2$. For $2\le s\le n/\log n$, any such component contains a spanning tree. The Cayley formula and a union bound therefore giveIn this range the bracket is at most $A=e^{2}L{e}^w/n=o(1)$. Summing over $s\ge 2$ gives $O(n{A}^2/L)=O(L{e}^{2w}/n)=o(1)$. For $n/\log n<s\le n/2$, even the cut-absence bound is enough:The bracket tends to zero, so this range also has total probability $o(1)$. Consequently the graph at $p_{-}$ consists of one component of order greater than $n/2$ and its isolated-vertex set $S$, where $1\le |S|\le \log n$ with high probability.

Conditional on the entire graph at $p_{-}$, every unrevealed edge label remains independently uniform on $(p_{-},1)$. In particular,There are no isolated vertices at $p_{+}$ with high probability, because their expected value is asymptotic to $e^{-w}\to 0$. On the intersection of these events, each vertex of $S$ loses isolation by joining the original large component, never by forming a separate small component with another vertex of $S$. At every step between these two thresholds there is therefore one nontrivial component and some isolated vertices. The final isolated vertex disappears precisely when the graph becomes connected. This proves the connectivity hitting time equals disappearance of isolated vertices result:

For the critical-window probability, let $p=(\log n+\alpha (n))/n$ with $|\alpha (n)|\le B$. For each fixed $j$, the falling factorial moment of the isolated-vertex count isuniformly for such shifts. Apply the Bonferroni inequalities to the zero-count event. Its odd and even truncations bracket $\mathrm{Pr}(Z=0)$ by partial sums of ${\sum }_{j\ge 0}(-1{)}^j{e}^{-j\alpha (n)}/j!$. Since $e^{-\alpha (n)}\le e^B$, their remainders tend uniformly to zero. Hence $\mathrm{Pr}(Z=0)=e^{-e^{-\alpha (n)}}+o(1)$. The process equality just proved changes this probability by at most its $o(1)$ failure probability. ThereforeThe ratio follows because the denominator is bounded below by $e^{-e^B}>0$; no convergence of $\alpha (n)$ is needed.

The printed second conclusion has the complementary denominator and is false as written. For $\alpha (n)=0$, the printed ratio tends to $e^{-1}/(1-e^{-1})=1/(e-1)\ne 1$. Its denominator $1-e^{-e^{-\alpha (n)}}$ is correct for the probability of being disconnected. Thus either remove the leading $1-$ in the denominator or replace “connected” by “disconnected”; the proof supplies both corrected versions.

Expose the vertices in order, revealing at step $i$ every edge from vertex $i$ to an earlier vertex. With the resulting filtration ${\mathcal{F}}_i$, putThis is the vertex exposure for chromatic number martingale. Its increments $D_i=M_i-M_{i-1}$ have conditional mean zero and satisfy $|D_i|\le 1$, by the permitted Lipschitz condition.

Here is the required exponential-moment proof of the Azuma-Hoeffding inequality. More generally, suppose $|D_i|\le c_i$ for deterministic $c_i$. Convexity of the exponential function gives, for $-c_i\le d\le c_i$,Taking conditional expectation and using the zero conditional mean yieldsFor the last inequality, integrate $(\log \cosh u{)}^{\prime }=\tanh u\le u$ for $u\ge 0$, and use evenness. A zero $c_i$ simply means a zero increment. Iterated conditional expectation now givesFor $s,t>0$, the strict Markov bound on the event $M_n-M_0>s$ givesThe strict inequality follows directly by integrating $e^{t(M_n-M_0)}>e^{ts}$ on that event; it is also immediate if the event is empty. Optimize at $t=s/{\sum }_i{c}_i^2$ and apply the same argument to the negative increments. For $c_i=1$ and $s=\lambda \sqrt{n}$, the union bound proves, for every $\lambda >0$,At $\lambda =0$ the displayed strict bound is trivial.

For the second conclusion write $a_n=n/\log n$ and choose a fixed $C>\sqrt{2\log 10}$. If $\mu \ge a_n+C\sqrt{n}$, then $\{\chi (G)<a_n\}\subseteq \{\chi (G)-\mu <-C\sqrt{n}\}$, whose probability is less than $e^{-C^2/2}<1/10$. Thus the given positive probability forces $\mu <a_n+C\sqrt{n}$. For sufficiently large $n$,Here the non-strict one-sided bound follows by the usual non-strict Markov inequality. Consequently the asserted upper bound holds with high probability, uniformly over any sequence $p=p(n)$ satisfying the stated assumption.

A connected graph with $n>1$ has no isolated vertices. Conversely, a disconnected graph with no isolated vertices has a connected component with size between $2$ and $n/2$. We must show that this latter event has probability tending to zero.

The permitted component-size estimate excludes sizes between $\log \log n$ and $n/2$ with high probability. For the remaining small sizes, let $C_k$ count components with $k$ vertices. A connected graph on a fixed $k$-vertex set contains a spanning tree. By the Cayley formula, there are $k^{k-2}$ labelled trees, as follows from the Prüfer code bijection between labelled trees and sequences of $k-2$ labels. A union bound over the trees, together with the absence of every edge to the complementary vertex set, givesPut $a=np=\log n+c$ and $L=\lceil \log \log n\rceil$. Using $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ and $1-p\le e^{-p}$, uniformly for $2\le k\le L$ we obtainHere $p{L}^2\to 0$. Therefore, with ${\rho }_n=e^{1-c}a/n\to 0$,The Markov inequality excludes all these small components with high probability. Together with the permitted estimate, this proves that the difference between the probability of connectivity and the probability of no isolated vertices tends to zero. Hence

For the unheaded degree-one continuation, write $X={\sum }_{v=1}^n{I}_v$, where $I_v$ indicates that vertex $v$ has degree one. Withwe haveFor distinct vertices $u,v$, separate the cases where their connecting edge is present or absent. If it is present, all their other incident edges must be absent. If it is absent, each vertex chooses its unique neighbour among the other $n-2$ vertices; those two neighbours may coincide. The respective edge constraints are independent even in that case. ThusDividing by $q^2$ gives the exact ratioThe first term tends to zero because $(n-1{)}^{2}p$ has order $n\log n$; the second tends to one. Consequently its variance satisfiesThe Chebyshev inequality now yields $\mathbb{P}(X=0)\le \mathrm{Var}X/(\mathbb{E}X{)}^2\to 0$. A vertex of degree one exists with high probability, even though the limiting probability of having an isolated vertex is strictly between zero and one.

The precise external concentration result we use is Talagrand's convex distance inequality: for a finite product of independent standard probability spaces, a measurable event $B$ of positive probability, and $u\ge 0$,Our coordinates are the independent uniformly sampled points of the triangle, so the hypothesis holds. Part (ii) therefore gives, for integers $a>b\ge 0$,Indeed every configuration in the first event has at least the distance from part (ii) to the second event. If one event is empty, the displayed product bound is automatic. This is the only use of the product-space theorem; the geometric separation was proved directly in part (ii). A precise source for that theorem is Section 4.1 of Talagrand's original product-space concentration paper.

Choose an integer median $m=m_n$, so $\mathbb{P}(L_n\le m)\ge 1/2$ and $\mathbb{P}(L_n\ge m)\ge 1/2$. First set $a=m+t$, $b=m$ in the product bound, and then set $a=m$, $b=m-t$. For positive integers $t$ this yields the convex-chain median concentration estimatesThe lower event is empty if $m-t<1$ in our sampling model; the upper event is empty if $m+t>n$. Thus the stated bounds remain valid for all positive integers $t$. Also $m\ge 1$ for $n\ge 1$.

By part (i), $m\le C{n}^{1/3}$ with $C=4e$. Let $h_n=\omega (n)n^{1/6}/2$, take $t_n=\lfloor h_n\rfloor +1$, and use the deterministic interval $I_n=[m-h_n,m+h_n]$. Its length is exactly $\omega (n)n^{1/6}$. As $L_n$ and $m$ are integers, falling outside this interval implies one of the two tail events with $t=t_n$. ThereforeFor positive $m,t$,Since $t_n\ge h_n$ and $m\le C{n}^{1/3}$, this exponent is at leastConsequentlyThus $L_n$ lies with high probability in the required interval. This proof works for every $\omega (n)\to \infty$, including growth faster than $n^{1/6}$; no extra restriction on $\omega$ is needed. The scale comes from the square root of the $O(n^{1/3})$ certificate size at the median.

It suffices to prove the assertion after replacing $\omega$ by $\min \{\omega ,\sqrt{\log n}\}$: that replacement gives a tighter interval. Thus assume $\omega \to \infty$ and $\omega =o(\log n)$, and putAt $p_{-}$, let $J$ count isolated vertices in $L$. The same indicator random variable calculation as for all isolated vertices givesBy the Chebyshev inequality, $J>0$ with high probability. Since $\ell \ge 2$ eventually, the marked vertices are then not all connected.

At $p_{+}$, the logarithmic-regime giant component result applies with $k=2$ and any fixed ${\gamma }_0\in (1/3,1/2)$. Its unique giant component misses $(1+o(1))n^{1/2}{e}^{-\omega /4}$ vertices. On the event that it misses at most twice that number, exchangeability makes the missed vertex set uniform conditional on its size. A union bound therefore givesThus all of $L$ is connected at $p_{+}$ with high probability.

For the uniform random graph process, assign uniform labels to the edges of the complete graph as independent random variables and reveal them in label order. The binomial random graph $G(n,p)$ is the prefix containing the $M(p)$ labels at most $p$, where $M(p)$ has a binomial distribution with parameters $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $p$. Its variance at $p_{\pm }$ is $O(n\log n)$, whereas the gap between $\mathbb{E}M(p_{\pm })$ and the relevant endpoint $m_{\pm }$ is $(1+o(1))\omega n/8$. The Chebyshev inequality gives $M(p_{-})\ge m_{-}$ and $M(p_{+})\le m_{+}$ with high probability, with harmless integer rounding. The monotone graph property that all marked vertices are connected now impliesThe marked-set connectivity threshold is lower than the threshold for connecting every vertex, because only about $\sqrt{n}$ specified vertices need to avoid the small graph components.