The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs

Statement

**General principle (Alon–Spencer, *The Probabilistic Method*, 3rd ed., Ch. 3, opening paragraph, p.27, read in full). The basic probabilistic method proves existence of a structure with a desired property by exhibiting a probability space of candidate structures in which that property holds with positive probability. The alteration method** (a.k.a. the *deletion method*) is used when a single random draw does not *quite* have the desired property but merely has few enough "blemishes" — bad local sub-configurations — that a small, deterministic surgical fix (deleting one vertex/point/edge per blemish) removes them all while leaving the bulk of the structure, and hence its good global properties, intact. Verbatim: *"In this chapter we consider situations where the 'random' structure does not have all the desired properties but may have a few 'blemishes.' With a small alteration we remove the blemishes, giving the desired structure."*

The canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs. P. Erdős, "Graph theory and probability," *Canadian J. Math.* 11 (1959), 34–38.

> Theorem [Erdős 1959]. For all positive integers $k,l$ there exists a graph $G$ with $\mathrm{girth}(G) > l$ and $\chi(G) > k$.

Proof (Alon–Spencer §"The Probabilistic Lens: High Girth and High Chromatic Number," pp.41–42, read in full). Fix $\theta < 1/l$ and let $G\sim G(n,p)$ with $p = n^{\theta-1}$ (each of the $\binom n2$ possible edges present independently with probability $p$).

*Step 1 — bound the expected number of short cycles.* Let $X$ = number of cycles of length $\le l$ in $G$. By linearity of expectation, $$\mathbb E[X] = \sum_{i=3}^{l}\binom ni\frac{(i-1)!}{2}p^i = O\!\big(n^{\theta l}\big) = o(n)$$ (each of the $l$ terms is $\le n^i p^i = n^{\theta i} \le n^{\theta l}$, and $\theta l<1$). By Markov's inequality, $$\Pr[X \ge n/2] \le \frac{\mathbb E[X]}{n/2} = o(1).$$

*Step 2 — bound the independence number by a union bound.* Set $x = \lceil (3/p)\ln n\rceil$. For any fixed $x$-subset, the probability it is independent is $(1-p)^{\binom x2}$; a union bound over the $\binom nx$ subsets gives $$\Pr[\alpha(G) \ge x] \le \binom nx (1-p)^{\binom x2} \le \big(n\,e^{-p(x-1)/2}\big)^x = o(1).$$

*Step 3 — union the two failure events.* For $n$ large enough, both $\Pr[X\ge n/2]$ and $\Pr[\alpha(G)\ge x]$ are $<1/2$, so their union has probability $<1$ and there exists a specific graph $G$ with $X<n/2$ short cycles and $\alpha(G) < x = O(n^{1-\theta}\ln n)$.

*Step 4 — alter: delete one vertex from each bad cycle.* Remove one vertex from each of the (fewer than $n/2$) cycles of length $\le l$. This yields $G^*$ on at least $n/2$ vertices with $\mathrm{girth}(G^*) > l$ (every short cycle had a vertex removed) and $\alpha(G^*) \le \alpha(G) < x$ (deleting vertices cannot enlarge an independent set).

*Step 5 — read off the chromatic number.* Every proper coloring's color classes are independent sets, so $\chi(G^*) \ge |V(G^*)|/\alpha(G^*) \ge \dfrac{n/2}{3n^{1-\theta}\ln n} = \dfrac{n^{\theta}}{6\ln n} \to \infty$ as $n\to\infty$; choose $n$ large enough that this exceeds $k$. $\blacksquare$

The alteration step is exactly: start from a random object that is simultaneously (a) *almost* free of the bad local feature (few short cycles) and (b) globally well-behaved with high probability (small independence number); then perform a *local, one-per-violation deletion* that kills the bad feature outright while only weakly damaging the global parameter, because deletion is monotone for the global parameter in question (removing vertices can only shrink $\alpha(G)$, never grow it).

Facts

- Historical significance. This 1959 paper is widely regarded as the paper that established the probabilistic method as a general tool in graph theory / combinatorics beyond its earlier number-theoretic uses; Alon–Spencer call it "one of the most pleasing uses of the probabilistic method, as the result is surprising and does not appear to call for nonconstructive techniques" (p.41) — before Erdős's proof, explicit hand-built constructions of high-girth, high-chromatic graphs existed only for bounded parameter ranges, not for *arbitrary* $(k,l)$. - Same-chapter siblings — the alteration method is a template applied across many domains, not a single trick, all read in full from Alon–Spencer Ch. 3: - *Diagonal Ramsey numbers* (§3.1, Theorem 3.1.1): random 2-coloring of $K_n$'s edges, $X$ = number of monochromatic $k$-cliques, $\mathbb E[X]=\binom nk2^{1-\binom k2}=m$; delete one vertex from each monochromatic $k$-clique to get $R(k,k) > n-m$, optimized over $n$ to give $R(k,k) > \tfrac1e(1+o(1))k2^{k/2}$. - *Off-diagonal Ramsey numbers* (§3.1, Theorem 3.1.3): same recipe with edge-probability $p\ne 1/2$, $X$ = red $k$-sets + blue $l$-sets, gives $R(k,l) > n - \binom nk p^{\binom k2} - \binom nl(1-p)^{\binom l2}$ — strictly stronger than the basic-method bound (Theorem 3.1.2, which needs $\mathbb E[X]<1$ for a *zero*-bad-event graph) because alteration tolerates $s>0$ bad sets and repairs them by deletion. - *Independent sets / half of Turán's theorem* (§3.2, Theorem 3.2.1): random vertex-subset $S$ (each vertex kept independently with probability $p=1/d$), $Y$ = edges inside $S$; $\mathbb E[|S|-Y]=np-\binom{}{}d p^2 n/2$-type calculation gives $\ge n/2d$; delete one endpoint of each surviving edge in $S$ to get an independent set of size $\ge n/2d$ in any graph with $n$ vertices and average degree $d$. - *Combinatorial geometry — Heilbronn's triangle problem* (§3.3, Theorem 3.3.1): $2n$ random points in the unit square, $X$ = number of triangles with area $<1/(100n^2)$, $\mathbb E[X]<n$; delete one vertex from each such triangle to leave $\ge n$ points with no small-area triangle, giving $T(n)=\Omega(1/n^2)$. - *Packing* (§3.4, Theorem 3.4.1): $n$ random translates of a centrally-symmetric convex body, $X$ = number of overlapping pairs, $\mathbb E[X]$ bounded; delete one point from each overlapping pair, optimize $n$, to get a packing-constant lower bound $\delta(C) \ge 2^{-d-1}$. - The unifying shape in every case: (construct random object) → (bound $\mathbb E[\text{bad events}]$ via linearity of expectation, or bound $\Pr[\text{bad tail event}]$ via Markov/union bound) → (fix a good draw by a union of "failure probability $<1$" events) → (delete one element per surviving bad event) → (argue the deletion cannot hurt the target parameter, only the bad-event count). - The union bound (Boole's inequality) is doing the heavy lifting in Step 3, not a deep concentration inequality: the proof only needs $\Pr[\text{bad}_1]+\Pr[\text{bad}_2]<1$, which requires each individual bad-event probability to merely be $o(1)$ — a *first-moment* (Markov / expectation) argument suffices; no variance, martingale, or Local Lemma dependency control is needed. This is what makes the alteration method the *simplest* member of the probabilistic-method toolkit, and also its main limitation (see Technique, below). - A recoloring variant exists in the same chapter (§3.5): instead of deleting blemished elements, one *recolors* them (Beck 1978's property-B bound, sharpened by Radhakrishnan–Srinivasan 2000 to $m(n)=\Omega\big(2^n(n/\ln n)^{1/2}\big)$) — evidence the "fix the blemishes after the fact" idea generalizes beyond literal deletion to any bounded local repair operation. - Relation to the Lovász Local Lemma and the Rödl nibble. The alteration method is the *coarsest* tool in this family: it only needs the *total* expected number of bad events to be small (a union bound), so it typically forces one to shrink the base random structure (lower $p$) enough that bad events are individually rare — at the cost of loosening the final quantitative bound. The Lovász Local Lemma (Erdős #165 — asymptotic formula for the Ramsey number R(3,k), Alon–Spencer Ch. 5) instead permits bad events with individually much *larger* probability, provided they are *sparsely dependent*, giving asymptotically sharper Ramsey/coloring bounds (e.g. $R(k,k)>\tfrac{\sqrt2}{e}(1+o(1))k2^{k/2}$ vs. alteration's weaker constant) without needing a delete-and-repair step at all. The Rödl nibble (Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings) is the *iterated*, many-round generalization of the same "random-then-repair" idea, replacing one global alteration pass with $\Theta(\log D)$ successive small random deletions plus a concentration argument, reaching much higher target densities (e.g. hypergraph packing) than a single alteration pass could certify. All three sit on a single spectrum: alteration (1 global repair, union bound) → Local Lemma (0 repairs, but needs local sparsity of dependencies) → nibble (many small repairs, needs concentration per round). - Erdős's 1947 diagonal-Ramsey lower bound predates and motivates this chapter's framing, but is usually presented (Alon–Spencer §1.1, Erdős's original 1947 paper) as the *basic* method (a coloring with zero monochromatic cliques exists because $\mathbb EX<1$) rather than alteration; Theorem 3.1.1 in the same chapter is the alteration-strengthened version that tolerates $\mathbb E X = m>0$ bad cliques and repairs by deletion, extending the reach of the same starting random coloring to larger $n$.

Technique

WHEN it applies. Reach for the alteration method when: 1. You want to prove *existence* of a combinatorial/geometric structure satisfying a global size or density parameter (chromatic number, independence number, Ramsey number, packing density, point-set-with-no-small-triangle) subject to a local forbidden-pattern constraint (no short cycle, no monochromatic clique, no overlapping pair, no small-area triangle). 2. A natural random model (usually $G(n,p)$, a random 2-coloring, a random subset, or i.i.d. random points) makes the *expected count* of local violations small — specifically $o(n)$ or $o(1)$ relative to the object's size — via a routine linearity-of-expectation computation, while simultaneously making the *target global parameter* concentrate favorably (e.g. small independence number) via a union-bound/Markov tail estimate. 3. Deleting one element per violation is "cheap" for the target parameter — i.e. the parameter you care about is monotone under deletion in the direction that helps (removing vertices cannot increase independence number or increase chromatic-number-lower-bound-denominator faster than numerator; removing points cannot create a small triangle that wasn't there before). This monotonicity check is the crux of whether alteration is even applicable to a given problem.

WHY it works (the mechanism). Two independent first-moment/tail bounds are combined by a union bound: $\Pr[\text{too many local violations}] + \Pr[\text{global parameter too extreme}] < 1$ for suitable choice of the random model's parameter (here, $\theta$ or $p$) and threshold (here, $n/2$ short cycles, $x$-size independent sets). Whenever this sum is $<1$, a single draw avoiding *both* bad events must exist — this is nothing more than Boole's inequality applied to two events, not a deep concentration result. Once such a draw is fixed, the "few bad local violations" property becomes a finite, deterministic repair budget: delete one vertex/point per violation, which by hypothesis (a) never creates new bad configurations that weren't already accounted for, and (b) removes only a controllably small fraction of the object, so the good global property (bounded independently of the repair) survives at only a constant-factor cost.

The reusable recipe

1. Choose the random model and its parameter (e.g. $p=n^{\theta-1}$ for $G(n,p)$) so that it trades off the two competing goals: keeping the *local* bad-event count expectation small (favors low $p$/low density) against keeping the *target global parameter* favorable (here, small $\alpha(G)$, which favors *higher* $p$ — since a sparser graph has a larger independent set). The single free parameter $\theta<1/l$ is chosen precisely to balance $\mathbb E[X]=o(n)$ (needs $\theta l<1$) against $\alpha(G)=O(n^{1-\theta}\ln n)$ being as small as possible (favors $\theta$ close to $1/l$) — this tension, and its optimization, is the one genuinely problem-specific step. 2. Bound $\mathbb E[\#\text{bad local events}]$ via linearity of expectation over all potential violations (all possible short cycles / monochromatic cliques / overlapping pairs / small triangles), each weighted by its occurrence probability under the model. 3. Bound the target global parameter's bad tail via a union bound over all candidate witnesses (all $x$-subsets for independence number, etc.), using Markov/Boole, not a sharper concentration tool — this is what makes the method the "basic" alteration technique rather than a second-moment or martingale argument. 4. Take $n$ (or the relevant scale parameter) large enough that both failure probabilities are individually $<1/2$ (or, more generally, that their sum is $<1$), guaranteeing by Boole's inequality that a single draw avoiding both exists. 5. Delete one element per surviving local violation. Verify explicitly that this deletion (a) eliminates every instance of the forbidden local pattern, and (b) can only help — never hurt — the target global parameter's favorable bound (monotonicity check). 6. Recompute the target parameter on the reduced object. Because only an $o(n)$ (or otherwise controllably small) fraction of the object was deleted, the surviving object's size is still $\Theta(n)$, so ratios like $\chi(G^*)\ge |V(G^*)|/\alpha(G^*)$ retain the same asymptotic order as before deletion — this final ratio step is what converts "girth large + independence number small" into "chromatic number large."

HOW to use this to prove new things (recombination guidance for a solver). - If the problem is "does there exist a combinatorial object avoiding [some local pattern] while forcing [some global extremal parameter to be large]," first check whether a natural random model makes the local-pattern count's *expectation* $o(\text{object size})$ — if yes, alteration is very likely to apply, and the entire proof reduces to (i) a linearity-of-expectation computation and (ii) a union-bound computation, both of which are typically short, explicit, and calculus-optimizable (as in step 1 above). - If a naive alteration argument gives a bound that feels too weak (e.g. constants that don't match known upper bounds, or a target density that plateaus below what's believed true), the standard escalation path is: (a) try the Lovász Local Lemma if the bad events, while individually not-that-rare, are *sparsely dependent*; (b) try the Rödl nibble / semi-random method (Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings) if a single alteration pass isn't enough but *iterating* many small random deletions with a concentration argument between rounds could push the density further; (c) try a second-moment argument (Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs) if the obstruction is that $\mathbb E[X]>0$ alone doesn't certify $X>0$ with the needed precision. - Alteration is a lower-bound / existence technique only — like the nibble and Local Lemma, it says nothing about matching upper bounds; if the open problem is impossibility or tightness, this technique alone will not resolve it (a separate deterministic or extremal argument is needed for the matching direction, e.g. the de Bruijn–Erdős compactness argument used on the *finite-vs-infinite* side of related chromatic-number problems, De Bruijn–Erdős compactness theorem — infinite chromatic number is determined by finite subgraphs). - Monotonicity is the load-bearing hypothesis to verify first before attempting alteration on a new problem: does deleting elements provably not worsen the parameter you're trying to bound favorably? For chromatic-number-via-independence-number arguments this is immediate ($\alpha$ is monotone decreasing under vertex deletion); for other parameters (e.g. some algebraic or geometric invariants) this check can fail and alteration will not directly apply without a more careful accounting of how much a single deletion can damage the parameter.

Related

- Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the iterated, many-round generalization of the same random-then-repair idea; reach for the nibble when a single alteration pass isn't enough to reach the target density and a concentration argument between successive small deletions can be supplied. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the escalation when a first-moment/Markov argument alone (as alteration uses) doesn't certify existence with the needed precision; variance-based concentration instead of union-bound tail estimates. - Random-set construction + Janson's inequality / Vu concentration (the Poisson paradigm) — a sibling "construct almost-good random object, then certify/repair via a sharper tail bound (Janson's inequality / Vu's polynomial concentration)" technique family, used when the alteration method's crude union bound is too lossy. - Vertex-exposure martingale + Azuma–Hoeffding concentration for graph parameters — an alternative concentration tool (Azuma–Hoeffding on a Doob martingale) for pinning down a graph parameter's concentration window, useful when the object being altered is too globally entangled for a simple linearity-of-expectation + union-bound argument. - De Bruijn–Erdős compactness theorem — infinite chromatic number is determined by finite subgraphs — the finite/infinite chromatic-number transfer theorem often paired with alteration-method constructions when a problem is stated for infinite chromatic number but the alteration method itself only directly produces finite witnesses. - Erdős #74 — almost-bipartite graph of infinite chromatic number — open Erdős problem (almost-bipartite graph of infinite chromatic number) whose provenance already flags this exact concept slug as "the closest known technique-shape to 'sparsify a highly-chromatic graph while preserving chromatic number,'" i.e. a candidate reverse-engineering target for this method. - Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — infinite-chromatic-number/cycle-length sibling problem, solved by Liu–Montgomery via sublinear expanders, not alteration — useful contrast for when a "graph of high chromatic number must contain X" question needs a fundamentally different (non-deletion) technique. - Erdős #165 — asymptotic formula for the Ramsey number R(3,k) — asymptotic formula for $R(3,k)$; the historical trajectory of its lower-bound record (alteration-style constructions superseded by nibble-based Kim 1995, then by pseudorandom-graph constructions) illustrates the alteration → nibble → beyond-nibble escalation path described in Technique, above, for a Ramsey-flavored problem in the same technique family as $R(k,k)$'s Theorem 3.1.1.