Random graph

A random graph is a graph sampled from a probability distribution on graphs.

At each step offer a fixed number of independent uniform candidate edges on a fixed vertex set, and let a rule select one. The standard two-choice model offers two candidates. The rule may depend on the entire previously exposed history. Repeated already present edges make no change in the independent-candidate version; another usual version offers only absent edges. The forced merging of large components and persistence of unsampled graph components apply to both over a linear number of steps. Fixed choice is essential in the continuity of fixed-choice percolation argument.

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.

Fix positive $\alpha$, $D\ge 2$ and $B>0$. Suppose a size band $[k,Dk)$ of an Achlioptas process contains at least $\alpha n$ vertices at time $m$. For every fixed $k$, at least $\beta n$ of those vertices remain in unchanged graph components throughout the next $T=\lceil Bn/k\rceil$ steps, with high probability, where one may take $\beta =\alpha e^{-16BD}/4$. This is a deliberately nonoptimal positive constant.

For independent uniform candidate edges, an initial graph component with $w<Dk$ vertices is untouched if none of the $2T$ candidate edges meets it. A uniform edge hits it with probability at most $3w/n$. For sufficiently large $n$, $(1-3w/n{)}^{2T}\ge e^{-16BD}$, so the expected value of the untouched vertex mass $Y$ is at least $\alpha e^{-16BD}n$. Replacing one row of two candidate edges can change $Y$ by at most $8Dk$, because only the initial graph components hit by an old or new endpoint can change status. The McDiarmid inequality therefore makes $Y\ge \alpha e^{-16BD}n/2$ except on an event of probability $e^{-cn/k}$, for a positive constant $c$ depending only on $\alpha ,B,D$. An untouched graph component stays unchanged whichever offered edge is selected.

For candidates restricted to absent edges, generate each by an independent uniform proposal stream and reject already present edges. During any interval of $O(n)$ steps with $O(n)$ present edges, each proposal has rejection probability $O(1/n)$ conditional on the past. The number of rejections is at most $O(\log n)$ except on an event of probability smaller than any inverse power of $n$: if there were $r$ rejections among $2T+r$ proposals, a union bound over their positions bounds this by $\left(\genfrac{}{}{0ex}{}{2T+r}{r}\right)(C/n{)}^r$. The first $2T$ proposals are independent and give the previous untouched-mass estimate. Extra proposals can touch at most $2r$ additional initial graph components, losing only $O(Dk\log n)=o(n)$ vertices for fixed $k$. This leaves the stated $\beta n$ bound. A union bound makes these estimates simultaneous over starting times $m\le 3n$. They hold through the entire interval, so deterministic or random stopping times within it are allowed.

For the two-choice Achlioptas process, fix $a>0$ and $K\ge 1$. Conditional on any current graph with $N_{\ge K}\ge an$, put $W$ equal to the vertices in its large graph components. There are at most $n/K$ such initial graph components. If after $s$ more steps no graph component contains $an/3$ vertices of $W$, greedily assign final graph components to two groups so that each meets at least $|W|/3\ge an/3$ vertices of $W$. This induces a set partition of the initial large graph components, of which there are at most $2^{n/K}$ possibilities.

For any fixed such split $W=A\cup B$, a uniform candidate edge joins $A$ to $B$ with probability at least $2a^2/9$. If both candidates do so, the selected edge cannot avoid the crossing. Thus the probability that the split survives all $s$ steps is at most $(1-a^4/81{)}^s$. The deliberately weaker constant also covers distinct candidate sampling for sufficiently large $n$. In the absent-edge version, as long as the split has survived, every $A$--$B$ edge is absent, so conditioning on absence can only increase this crossing probability. A union bound with $s=\lceil A(a)n/K\rceil$ and $A(a)=81(\log 2+2)/a^4$ bounds failure by $e^{-2n/K}$. For fixed $K$, a further union bound makes the conclusion simultaneous over all starting steps $m\le 3n$. This proof is independent of how the rule chooses between the two candidates.

This is the total number of vertices in graph components with orders in the specified half-open interval. It differs from the number of those graph components. Write $N_{\ge k}$ for the total above the lower endpoint. Then $N_{[k,\ell )}=N_{\ge k}-N_{\ge \ell }$. Disjoint size bands count disjoint sets of vertices at a common time, even though their mass may move between bands as an Achlioptas process adds edges.

Offer $k$ independent uniform edges of the complete graph per row and permit any one to be selected from each row. If a chosen graph has no graph component of order at least $2n/3$, the balanced component cut provides an empty cut whose sides both have at least $n/3$ vertices. Each candidate edge crosses that cut with probability at least $4/9$, so a row can avoid crossing with probability at most $1-(4/9{)}^k$. The union bound over at most $2^n$ cuts gives failure probability at most $2^n[1-(4/9{)}^k{]}^{cn}$. Any fixed integer $c$ with $c[-\log (1-(4/9{)}^k)]>\log 2$ suffices. The guarantee is simultaneous even for choices made after seeing every offered edge.

A giant component in a sequence of random graphs on $n$ vertices has order proportional to $n$. Its existence can change at a threshold function for a monotone graph property. A giant component need not contain every vertex, and its uniqueness requires proof for the model in question.

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.

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.

An isolated vertex has degree zero.

In the $G(n,p)$ model, each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges is included independently with probability $p$.

During Breadth-first search of $G(n,p)$ let $U_t$ count unseen vertices, $A_t$ active vertices, and $t$ explored vertices. When $A_{t-1}=0$ start a new unseen root, recorded by $b_t=1$; otherwise $b_t=0$. The newly discovered count is conditionally $\mathrm{Bin}(U_{t-1}-b_t,p)$. Subtract its conditional mean to obtain a martingale difference $D_t$. With $q=1-p$, $U_0=n$ and $A_0=0$, iteration givesThe last sum is a martingale. Positive $A_t$ over an interval means that the graph component under exploration does not finish there. Independently adding phantom children couples each component exploration below a binomial branching process with offspring law $\mathrm{Bin}(n,p)$.

Start with the empty graph and reveal the edges of the complete graph in a uniformly random order. After $m$ steps its edge set is a uniform $m$-element subset. Independent uniform edge labels couple this process with all binomial random graphs: $G(n,p)=G_{n,M(p)}$, where $M(p)$ has a binomial distribution with parameters $\left(\genfrac{}{}{0ex}{}{n}{2}\right),p$. For a monotone graph property, concentration of $M(p)$ transfers a threshold estimate between edge probability and edge count.

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.

For $X_j$ the number of tree components of order $j$ in a binomial random graph, choose their vertices, choose one of $j^{j-2}$ labelled trees by the Cayley formula, require its $j-1$ edges, and exclude both the remaining internal edges and all crossing edges. For $j=1$ interpret $j^{j-2}=1$, recovering the isolated vertex count. If $p=\lambda /n$ for fixed positive $\lambda$ and $j=O(\log n)$, the Stirling formula gives $\mathbb{E}{X}_j\sim n(\lambda e^{1-\lambda }{)}^j/(\lambda \sqrt{2\pi }{j}^{5/2})$. Distinct overlapping vertex sets cannot both be graph components; for disjoint sets their joint occurrence gains the factor $(1-p{)}^{-j^2}$ relative to the product, because their between-set edges must be absent only once.

A graph property is increasing and monotone when adding edges cannot destroy it.

A function $p^{\ast }(n)$ is a threshold when the property holds with probability tending to zero for $p/p^{\ast }\to 0$ and with probability tending to one for $p/p^{\ast }\to \infty$.

Assign an independent uniform label $U_e$ to every possible edge and include $e$ in $G(n,p)$ exactly when $U_e\le p$. This couples all edge probabilities so that $p\le q$ implies $G(n,p)\subseteq G(n,q)$.

Sprinkling exposes independent rounds $G(n,p_1),\dots ,G(n,p_k)$. Their union has distribution $G(n,p)$ where

Let $N$ be the number of isolated vertices in $G(n,p)$. Indicator variables giveand, because a specified pair is simultaneously isolated precisely when the $2n-3$ incident edges are absent,

For $p=c\log n/n$, the number $N$ of isolated vertices satisfiesThe upper side follows from the first-moment bound. On the lower side, $\mathbb{E}N\to \infty$ and $\mathrm{var}(N)/(\mathbb{E}N{)}^2\to 0$, so the second-moment method applies.

For every fixed $\epsilon >0$,whereas the probability tends to zero when $p\le (1-\epsilon )\log n/n$. Above the threshold a union bound excludes every component of size at most $n/2$; below it isolated vertices remain with high probability.

If a fixed graph $H$ has $v$ vertices, $e$ edges, and $N_H(n)$ unlabelled copies in $K_n$, then the number $X_H$ of its copies in $G(n,p)$ satisfiesThis follows by writing $X_H$ as a sum of indicator random variables.

For $p=n^{-2/3}\log n$, the number $X$ of copies of $K_4$ satisfiesand $\mathrm{var}(X)=o((\mathbb{E}X{)}^2)$. Two distinct copies have dependent indicators only when they share at least two vertices; pairs sharing two or three vertices contribute respectively $O(n^6{p}^{11})$ and $O(n^5{p}^9)$ to the variance.

For $p=n^{-2/3}\log n$, the expected number of pairs of $K_4$ copies sharing a vertex isThus, with probability tending to one, all the $K_4$ copies are vertex-disjoint. Together with sparse clique-count concentration, this gives arbitrarily many vertex-disjoint copies with probability tending to one.