Ramsey-type concentration of the independence/clique number of G(n,1/2)

Statement

Let $G\sim G_{n,1/2}$ (each of the $\binom n2$ possible edges present independently with probability $1/2$). Write $\omega(G)$ for the clique number and $\alpha(G)$ for the independence number; because $G_{n,1/2}$ and its complement $\bar G$ have exactly the same distribution, $\omega(G_{n,1/2})$ and $\alpha(G_{n,1/2})$ are identically distributed, so a concentration statement about one is automatically a concentration statement about the other.

Theorem (Bollobás–Erdős 1976; Matula 1970/72, independently). Fix $p\in(0,1)$ (the "dense" or constant-$p$ regime; $p=1/2$ is the canonical case) and set $b=1/p$. Let $$d(n) = 2\log_b n \;-\; 2\log_b\log_b n \;+\; 2\log_b(e/2) \;+\; 1 \;+\; o(1).$$ Then with probability $\to 1$ as $n\to\infty$, $\omega(G_{n,p})$ takes one of at most two consecutive integer values around $d(n)$; for a.e.\ (all but finitely many, in the Borel–Cantelli sense along a sequence of "milestone" $n$'s) $n$ these two candidate values coincide, giving genuine one-point concentration at exactly $\lfloor d(n)+o(1)\rfloor$ for those $n$. For $p=1/2$ ($b=2$) this reads $$\omega(G_{n,1/2}) \;=\; \big(2+o(1)\big)\log_2 n,$$ with the sharper form $d(n)=2\log_2 n - 2\log_2\log_2 n + 2\log_2(e/2)+1+o(1)$ pinning the *second-order* term as well, which is what forces the window down to $O(1)$ rather than just $o(\log n)$.

Coarser a.s. asymptotic (Grimmett & McDiarmid 1975, predates the sharp two-point result): $\omega(G_{n,p})/\log n \to 2/\log(1/p)$ almost surely.

Extension to sparser $p$ (Frieze 1990; Bohman–Hofstad 2022/2024). For $\omega(1/n)<p<o(1)$, $$\alpha(G_{n,p}) = \frac2p\Big[\log(np)-\log\log(np)+\log(e/2)\pm o(1)\Big]\ \text{whp (Frieze)},$$ and genuine two-point concentration of $\alpha(G_{n,p})$ (not just the above asymptotic-value statement) persists down to $p>n^{-2/3+\epsilon}$ (Bohman–Hofstad, arXiv:2208.00117, Theorem 1), which is close to best possible: Sah–Sawhney show that for $p=o\big((\log n/n)^{2/3}\big)$, $\alpha(G_{n,p})$ is provably *not* concentrated on two values (arXiv:2208.00117, Theorem 2, cited therein). The regime $\omega(1/n)<p\le n^{-2/3}$ remains open.

Why "Ramsey-type." The quantity governed here — the largest clique-or-independent-set forced to exist in *every* graph on $n$ vertices — is exactly the diagonal Ramsey number $R(s,s)$: $n\ge R(s,s)$ iff every 2-colouring of $K_n$'s edges (equivalently every graph on $n$ vertices, colouring edges present/absent) contains a monochromatic $K_s$. Erdős's original 1947 probabilistic lower bound (P. Erdős, "Some remarks on the theory of graphs," *Bull. Amer. Math. Soc.* 53(4) (1947)) is obtained by taking a *uniformly random* 2-colouring of $K_n$ (equivalently sampling $G_{n,1/2}$) and bounding $\Pr[\exists\text{ mono }K_s]\le\binom ns 2^{1-\binom s2}$; choosing $n=\lfloor 2^{(s-1)/2}\rfloor$ makes this $<1$, so *some* colouring with no monochromatic $K_s$ must exist, giving $R(s,s)>2^{(s-1)/2}$, refined to the standard modern form $R(s,s)\ge(1+o(1))\frac{s}{\sqrt{2e}}2^{s/2}$ (Spencer's Lovász-Local-Lemma argument sharpens the constant by a further factor $\sqrt2$). The concentration theorem above is the precise, sharpened version of exactly the estimate Erdős's argument needs: it says that $G_{n,1/2}$'s clique number is not merely bounded in expectation but *rigidly pinned* to $\sim2\log_2 n$, i.e. a "generic" (random) graph on $n$ vertices is a near-optimal — and essentially the *unique-scale* — witness that $R(s,s)>n$ once $n$ is below the concentration threshold for clique size $s$. This is the sense in which the result is "Ramsey-type concentration": it is the sharp-concentration companion fact underlying the deletion/counting step of the classical probabilistic construction of Ramsey lower bounds, rather than a Ramsey-number statement itself.

Facts

- Origin, two independent 1970s proofs. B. Bollobás, P. Erdős, "Cliques in random graphs," *Math. Proc. Cambridge Philos. Soc.* 80 (1976) 419–427 (renyi.hu/~p_erdos/1976-05.pdf); D. W. Matula, "On the complete subgraphs of a random graph," *Proc. 2nd Chapel Hill Conf. Combin. Math. Appl.* (1970) 356–369, announced also as "The employee party problem," *Notices AMS* 19(2) (1972) A-382. Bollobás–Erdős's own introduction states Matula's result is "considerably finer" and predates their note; Grimmett & McDiarmid, "On colouring random graphs," *Math. Proc. Cambridge Philos. Soc.* 77 (1975), gave the coarser a.s. ratio result independently and slightly earlier. - Proof mechanism, exactly first-moment (Markov) + second-moment (Chebyshev). Let $X_r=$ number of $r$-cliques (equivalently $r$-independent-sets) in $G_{n,p}$; $\mathbb E[X_r]=\binom nr p^{\binom r2}$ for cliques, $\binom nr(1-p)^{\binom r2}$ for independent sets. Because $\binom r2$ is quadratic in $r$ while $\log\binom nr$ is only $\Theta(r\log n)$, $\mathbb E[X_r]$ collapses from $\to\infty$ to $\to0$ within essentially one unit step of $r$ near $r\approx d(n)$ — Bollobás–Erdős's Theorem 1 makes this precise via the numbers $n_r$ (largest $n$ with $\mathbb E[X_r]<r^{-(1+\varepsilon)}$) and $n_r'$ (smallest $n$ with the reverse), showing $n_r'-n_r\le3(\log_b r)\,b^{r}$, i.e. a vanishingly thin transition window on the $n$-scale, and Borel–Cantelli (summing $\Pr[\exists n\in(n_r',n_{r+1}]:\,\omega\ne r]\le 4r^{-(1+\varepsilon)}$) upgrades "whp for each fixed large $n$" to "a.s. eventually always" as $n$ ranges over that milestone sequence. - The two-value (not always one-value) subtlety. Bollobás–Erdős's Corollary 1 gives, for *all* sufficiently large $n$, the two-sided bound $d(n)-\frac{2\log\log n}{\log n\log b}\le\omega(G_{n,p})\le d(n)+\frac{2\log\log n}{\log n\log b}$ whp — a window whose width is $o(1)$ relative to $d(n)$ but not identically $0$; they remark explicitly that "the upper and lower bounds... differ by at most 1 if $n$ is large and for most values of $n$ they simply coincide," which is the precise sense in which "two-point" (not always exactly one-point) is the correct general claim. - This is a load-bearing classical fact for chromatic-number asymptotics. Bollobás, "The chromatic number of random graphs," *Combinatorica* 8 (1988) 49–55, uses "$\omega(G_{n,1/2})<(2+o(1))\log_2 n$ whp" as a direct input to the sharp $\chi(G_{n,1/2})\sim n/(2\log_2 n)$ asymptotic (via a greedy/independent-set-removal argument), which is itself the input to the (much later, and much harder) question of whether $\chi$ is similarly tightly *concentrated* — it is emphatically not; see Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou). - Modern sharpening/frontier (2022–2024). T. Bohman, J. Hofstad, "Two-Point Concentration of the Independence Number of the Random Graph," arXiv:2208.00117, *Forum of Math. Sigma* 12 (2024) e24, replace plain independent-$k$-set counts by "augmented independent sets" (an independent set padded by a matching whose exterior vertices each see $\ge2$ neighbours in it) to push genuine two-point concentration from the classical constant-$p$ regime down to $p>n^{-2/3+\varepsilon}$; A. Sah, M. Sawhney (cited within the same paper) show this is close to sharp via an explicit anti-concentration construction for $p=o((\log n/n)^{2/3})$. Bohman–Hofstad also extend to the uniform $G_{n,m}$ model (arXiv:2410.05420) for $m>n^{5/4+\varepsilon}$, a regime where the analogous $G_{n,p}$ is provably not two-point concentrated. - Ramsey-number connection, quantitative. Erdős's 1947 random-2-colouring argument gives $R(s,s)>2^{(s-1)/2}$, refined to $R(s,s)\ge(1+o(1))\frac{s}{\sqrt{2e}}2^{s/2}$; Spencer's Lovász-Local-Lemma variant (J. Spencer, "Ramsey's theorem — a new lower bound," *J. Combin. Theory Ser. A* 18 (1975) 108–115) improves the constant by $\sqrt2$. As of 2025, J. Ma, W. Shen, S. Xie gave the first improvement in 50 years to near-diagonal (asymmetric, $R(s,t)$ with $t$ somewhat larger than $s$) Ramsey lower bounds, replacing Erdős's coin-flip $G_{n,1/2}$ random graph with points placed randomly on high-dimensional spheres and edges coloured by pairwise distance — reported by Quanta Magazine (2026-06-26, "After 80 Years, Mathematicians Give Famed Erdős Method an Upgrade") as a structural descendant of the same random-deletion idea, improving the growth-rate base from $(\frac{\sqrt5+1}2)^k$ towards $(\frac{\sqrt5+1}2+10^{-21})^k$ in the relevant asymmetric regime (this last figure sourced only from the popular-science article, not independently verified against the primary paper — flagged lower confidence).

Technique

When it applies. Whenever the object of interest is the largest clique (or independent set, or more generally the largest copy of some fixed "dense" pattern $H$ whose density is governed by $\binom{\cdot}2$-type quadratic growth) inside a dense random graph $G_{n,p}$ with $p$ constant (or, per Bohman–Hofstad/Frieze, $p$ polynomially close to constant, down to $p>n^{-2/3+\varepsilon}$). It is the tool of choice specifically because the target statistic's defining count $\mathbb E[X_r]=\binom nr p^{\binom r2}(\text{or }(1-p)^{\binom r2})$ has *doubly-exponential* decay in $r$ (via the $\binom r2$ exponent), which is what makes an $O(1)$-width (rather than merely $O(\sqrt n)$ or $O(\log n)$) window achievable at all — contrast with statistics like the chromatic number, whose defining structure is not a simple clique-count and which is *not* similarly rigid (see Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou)).

Why it works (the mechanism). 1. Reduce "is $\omega(G)\ge r$?" to "is $X_r>0$?" where $X_r=\sum_S \mathbf 1[S\text{ is an }r\text{-clique}]$, a sum over the $\binom nr$ potential $r$-subsets. This turns an extremal/max-type question into a pure counting-random-variable question, unlocking moment methods. 2. Upper bound the top via Markov (first moment). For $r$ with $\mathbb E[X_r]\to0$, Markov gives $\Pr[X_r\ge1]\le\mathbb E[X_r]\to0$: whp no $r$-clique exists at all, so $\omega(G)<r$. This is the entire non-existence half — no variance computation needed, and it is genuinely a one-line computation once $\mathbb E[X_r]=\binom nr p^{\binom r2}$ is written down. 3. Lower bound the bottom via Chebyshev (second moment). For $r$ just below that threshold, $\mathbb E[X_r]\to\infty$, but existence still needs ruling out the "rare huge spike" failure mode. Compute $\mathrm{Var}(X_r)$ by summing pairwise covariances of $r$-set indicators grouped by intersection size $\ell=|S\cap T|$ (Bollobás–Erdős's eq. (5) does this explicitly): the dominant terms come from near-disjoint pairs, and a direct calculation shows $\mathrm{Var}(X_r)=o(\mathbb E[X_r]^2)$ in the relevant range of $r$. Chebyshev then gives $\Pr[X_r=0]\le\mathrm{Var}(X_r)/\mathbb E[X_r]^2\to0$: whp $\omega(G)\ge r$. 4. The two bounds meet in an $O(1)$ window because $\log\mathbb E[X_r]$ falls off with slope $\Theta(r)=\Theta(\log n)$ in $r$ near the crossover. Because the crossover is this steep, "$\mathbb E[X_r]\to\infty$" and "$\mathbb E[X_r]\to0$" are separated by essentially one integer step of $r$ once the leading log-scale term $2\log_b n$ is fixed — this is the structural reason the window is $O(1)$-wide rather than growing with $n$; solving the transition condition $\mathbb E[X_r]=\Theta(1)$ for $r$ explicitly (via Stirling on $\binom nr$) produces the closed-form threshold $d(n)$. 5. Borel–Cantelli, applied along a discretely-indexed sequence of "milestone" thresholds $n_r$ (not along all $n$ directly), upgrades whp-for-fixed-$n$ into a.s.-eventually-exact-one-value statements for a.e.\ $n$: because the per-$r$ failure probabilities $4r^{-(1+\varepsilon)}$ are summable, only finitely many $r$ can ever see a "bad" $n$ in their transition window, giving a genuinely almost-sure (not just in-probability) pinning of $\omega(G_n)$ as $n$ ranges continuously, not just at one fixed target $n$. 6. Recombination pattern for open problems. This is the canonical template for any question of the form "what is the extremal size of structure $\mathcal S$ that a *random* instance of a combinatorial object typically contains/avoids, and how sharply is that size pinned down?" — (a) define the counting r.v. $X_r$ for the structure at scale $r$; (b) use Markov for the cheap one-sided non-existence bound; (c) use Chebyshev with an intersection-size-indexed covariance decomposition for the existence bound; (d) check the *steepness* of $\log\mathbb E[X_r]$'s transition to see how narrow a window this buys — quadratic-in-$r$ exponents (clique/independent-set counting) buy $O(1)$-width windows; the same skeleton applied to structures with gentler transitions (Bohman–Hofstad's augmented independent sets, needed once plain $X_r$'s variance stops being tight for sparser $p$) can still work but needs a cleverer auxiliary counting object. When this recipe is run *inside a Ramsey lower-bound argument* (Erdős 1947), the "existence" half alone (a positive-probability, not even whp, statement that some $n$-vertex graph avoids both a red and a blue $K_s$) already suffices for the Ramsey number bound; the *full* two-point concentration theorem above is the strictly stronger, later-proved fact about what a *typical* such graph looks like, and is not needed for the Ramsey lower bound itself — but it explains exactly how tight/generic that random construction is.

What it does NOT give. Only the *value* (up to $O(1)$) of the extremal clique/independent-set size — it says nothing about the *chromatic number* of the same random graph, which is governed by a structurally different (non-clique-counting) extremal quantity and is, surprisingly, *not* similarly rigidly concentrated (Heckel 2019/2021; see Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou)). It also does not by itself give the two-point concentration for $p$ below $n^{-2/3}$ (open; Sah–Sawhney show plain two-point concentration genuinely fails for $p=o((\log n/n)^{2/3})$), nor does it directly improve the constant in the deterministic Ramsey number bounds themselves (those improvements — Spencer's Lovász Local Lemma argument, or Ma–Shen–Xie's 2025 high-dimensional-sphere geometric random construction — replace or augment the *coin-flip* $G_{n,1/2}$ model with a different random object entirely).

Related

- Independence/clique number of G(n,1/2) is two-point concentrated at ⌊α₀+o(1)⌋ — the detailed solved-problem writeup of exactly this Bollobás–Erdős/Matula/Bohman–Hofstad result, with the full first/second-moment proof sketch this page's Technique section abstracts. - Frieze's trick — boosting a positive-probability (second-moment) existence bound to whp via the vertex-exposure martingale — the sparse-regime ($p=d/n$) extension of the same asymptotic value, using a martingale-concentration-plus-existence "boosting" trick rather than a direct second-moment argument, needed because plain second-moment alone only gives positive-probability (not whp) existence once $p\to0$. - Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou) — the surprising contrasting fact (Heckel 2019/2021, Heckel–Riordan 2023) that $\chi(G_{n,1/2})$, unlike $\omega/\alpha$, is *not* tightly concentrated; explicitly cites this concept as the classical baseline that made non-concentration of $\chi$ a surprise. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the general Markov/Chebyshev machinery this page's Technique section instantiates on clique/independent-set counts specifically. - Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988) — an Erdős–Gimbel–Straight cochromatic-vs-chromatic-number problem whose minimum-counterexample-size argument (Steiner 2024) uses a Ramsey-number-based finiteness bound, in the same broader "clique/independence-number-of-random-or-extremal-graphs" problem cluster. - Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — the open Erdős–Gimbel \$1000 cochromatic-number question for $G_{n,1/2}$, whose known partial results use this concentration result as the classical scale-setting input ($\omega,\alpha\sim2\log_2 n$).