Independence/clique number of G(n,1/2) is two-point concentrated at ⌊α₀+o(1)⌋

Statement

Let $G \sim G_{n,1/2}$ be the binomial random graph on $n$ vertices with each edge present independently with probability $1/2$, and let $\alpha(G)$ denote its independence number (equivalently, by self-complementarity of the model, $\omega(G)$ its clique number has the identical distribution). Define $$\alpha_0 = \alpha_0(n) = 2\log_2 n - 2\log_2\log_2 n + 2\log_2(e/2) + 1.$$

Claim

with high probability (whp, i.e. probability $\to 1$ as $n\to\infty$), $$\alpha(G_{n,1/2}) = \lfloor \alpha_0 + o(1)\rfloor,$$ meaning $\alpha(G_{n,1/2})$ takes one of only two consecutive integer values around $\alpha_0$ — an astonishingly sharp pinning-down for a quantity defined as the max over an exponential family of random events, compared to the naive expectation that it might fluctuate over a window of size $\Theta(\sqrt n)$ or worse (as, famously, the *chromatic* number of the same model does — see Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021)).

Facts

- Solved independently by two groups in the 1970s: Béla Bollobás & Paul Erdős, "Cliques in random graphs," *Math. Proc. Cambridge Philos. Soc.* 80(3) (1976), 419–427; and David W. Matula, "On complete subgraphs of a random graph," *Proc. 2nd Chapel Hill Conf. on Combinatorial Mathematics and its Applications* (1970/72), 356–369 (also announced as "The employee party problem," *Notices AMS* 19 (1972), A-382). Both prove two-point concentration of $\omega(G_{n,p})$ (equivalently $\alpha(G_{n,p})$ by complementation) for any fixed constant $p\in(0,1)$, of which $p=1/2$ is the canonical case. Independently, Grimmett & McDiarmid (1975) established the coarser but same-flavor asymptotic $\omega(G_{n,p}) = (1+o(1))\,2\log n/\log(1/p)$. - This is a genuinely *classical, load-bearing* result: it underlies the standard $n/(2\log_2 n)$-scale asymptotics for the chromatic number (Bollobás 1988, *Combinatorica* 8, 49–55) and the cochromatic number, both of which use "clique/independence number $<2\log_2 n$ whp" as an input fact — see Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? Facts. - The proof mechanism is exactly the first-moment / second-moment method applied to $X_k$ = number of independent $k$-sets in $G_{n,1/2}$: $\mathbb E[X_k] = \binom{n}{k}2^{-\binom k2}$. Because $\binom k2$ grows quadratically in $k$ while $\log\binom nk$ grows only like $k\log n$, $\mathbb E[X_k]$ collapses from $\to\infty$ to $\to 0$ within a *single unit increment* of $k$ around $k\approx\alpha_0$ — this razor-thin transition window is the structural reason the concentration is two-point rather than merely $O(\log n)$-point or $O(\sqrt n)$-point. - Sharper/extended versions (post-2020), same technique family: - Frieze (1990) extended the *asymptotic value* (not the two-point sharpness) down to $\omega(1/n)<p<o(1)$: $\alpha(G_{n,p})=\frac2p[\log(np)-\log\log(np)+\log(e/2)\pm o(1)]$ whp, combining second-moment with a large-deviation inequality. - Bohman & Hofstad, "Two-Point Concentration of the Independence Number of the Random Graph," arXiv:2208.00117, *Forum of Math. Sigma* 12 (2024) e24, revisit the *classical constant-$p$* Bollobás-Erdős/Matula theorem as their explicit starting point and push genuine two-point concentration down to $p > n^{-2/3+\epsilon}$, by upgrading the second-moment argument from plain independent-set counts to counts of "augmented independent sets" (independent sets padded with a matching whose exterior vertices each see $\ge 2$ neighbours in the set) once plain-$X_k$ second moments stop being tight. - Sah & Sawhney (cited in the same paper) show this is close to best possible: for $p = o\big((\log n/n)^{2/3}\big)$, $\alpha(G_{n,p})$ is *not* concentrated on two values, so the classical technique's reach has a genuine, now-located boundary. The regime $\omega(1/n)<p\le n^{-2/3}$ remains open. - Bohman & Hofstad also treat the closely related uniform model $G_{n,m}$, arXiv:2410.05420, extending two-point concentration to $m>n^{5/4+\epsilon}$ — a regime where the corresponding $G_{n,p}$ is provably *not* two-point concentrated, showing the two models genuinely diverge here.

Solution

Answer: yes — two-point concentration holds, with $\alpha(G_{n,1/2})\in\{\lfloor\alpha_0\rfloor,\lfloor\alpha_0\rfloor+1\}$ whp for $\alpha_0$ as above (Bollobás–Erdős 1976; Matula 1970/72).

The transferable technique — first moment kills the top, second moment forces the bottom, and both land in the same unit interval:

1. Count, don't search. Let $X_k$ be the number of independent $k$-vertex subsets of $G_{n,1/2}$. By linearity of expectation, $\mathbb E[X_k]=\binom nk 2^{-\binom k2}$ exactly — a closed form, no probabilistic subtlety yet. 2. Upper bound via Markov/first moment. If $k$ is large enough that $\mathbb E[X_k]\to 0$, then by Markov's inequality $\Pr[X_k\ge 1]\le\mathbb E[X_k]\to 0$: whp *no* independent $k$-set exists at all, so $\alpha(G)<k$. This is the entire upper-bound argument — no variance computation needed. 3. Lower bound via Chebyshev/second moment. For a $k$ one or two steps *below* that threshold, $\mathbb E[X_k]\to\infty$, but a nonzero mean alone does not imply $X_k>0$ whp (it could be a rare, large spike). The fix is to compute $\mathrm{Var}(X_k)$ by summing over *pairs* of $k$-sets by their intersection size $i=|S\cap T|$: the covariance contribution is dominated by near-disjoint pairs, and a direct calculation shows $\mathrm{Var}(X_k) = o\big(\mathbb E[X_k]^2\big)$. Chebyshev's inequality then gives $\Pr[X_k=0]\le \mathrm{Var}(X_k)/\mathbb E[X_k]^2\to 0$: whp an independent $k$-set *does* exist, so $\alpha(G)\ge k$. 4. The two bounds meet in one integer. Because $\log\mathbb E[X_k]$ is (to leading order) a smooth, rapidly decreasing function of $k$ that crosses zero with slope $\Theta(k)=\Theta(\log n)$ near $k=\alpha_0$, the "$\mathbb E[X_k]\to\infty$" regime and the "$\mathbb E[X_k]\to0$" regime are separated by an $o(1)$-width window in $k$ once expressed on the right normalized scale — i.e. by essentially one unit step of the integer $k$. Combining steps 2 and 3 therefore pins $\alpha(G)$ into an interval of length $O(1)$ around $\alpha_0$; a more careful boundary analysis (tracking exactly how $\mathbb E[X_k]$ and $\mathrm{Var}(X_k)$ behave at the two candidate integers flanking $\alpha_0$) sharpens this from "$O(1)$ values" to exactly two values. 5. Why this generalizes. The recipe — *(a)* define a counting random variable $X_k$ for the extremal structure of size $k$; *(b)* use Markov/first moment on $\mathbb E[X_k]$ for the one-line upper-tail (non-existence) bound; *(c)* use Chebyshev/second moment with a same-structure-intersection variance decomposition for the lower-tail (existence) bound; *(d)* exploit that $\mathbb E[X_k]$ falls off super-polynomially (here, doubly-exponentially, $\exp(-\Theta(k^2))$) in $k$ so the two regimes meet in a vanishingly narrow window — is the paradigmatic "first/second moment method" of the probabilistic method, and it is *exactly* the tool Bohman-Hofstad (2022/2024) reuse, upgrading only the "shape" of the counted structure (augmented independent sets instead of plain ones) to push the same two-step argument into sparser regimes where plain $X_k$'s second moment is no longer tight. It is also the direct technical ancestor of the second-moment/"tame colouring profile" machinery that later cracked *non*-concentration of the chromatic number of the very same model (Heckel 2021; Heckel–Panagiotou arXiv:2306.07253) — see Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021), where step 1's "large relative fluctuation of $X_a$" is precisely the leftover slack this page's Chebyshev step needed to be small.

Related

- Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — open Erdős–Gimbel \$1000 cochromatic-number question for $G_{n,1/2}$; its Facts section cites this exact two-point-concentration result as the classical fact giving the $n/2\log_2 n$-scale lower bound on the cochromatic number $\zeta$. - Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021) — the surprising contrasting result (Heckel 2021) that the *chromatic* number of the same $G_{n,1/2}$ model, unlike its clique/independence number, is emphatically not two-point (or even $o(\sqrt n)$-point) concentrated; its coupling proof directly exploits fluctuation in the same $X_k$ independent-set-count random variable this page's technique controls. - Ramsey-type concentration of the independence/clique number of G(n,1/2) — concept-level pointer to the Bollobás–Erdős/Matula result line; this page is its detailed solved-problem writeup. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the general first/second-moment (Markov + Chebyshev on a counting random variable) technique this page's Solution instantiates; reused directly in the chromatic-number non-concentration proof and in Bohman-Hofstad's sparser-$p$ extension. - Vertex-exposure martingale + Azuma–Hoeffding concentration for graph parameters — the complementary martingale-concentration technique (Shamir–Spencer 1987, Bollobás 1988) used for the *chromatic* number's coarser $O(\sqrt n)$-window concentration, contrasted with this page's sharper two-point result for clique/independence number.