the deletion (alteration) method
The deletion or alteration method is a two-stage refinement of the basic probabilistic method that often beats a pure first-moment argument by a constant factor or more. The plain first moment method asks for a random object with no bad substructures at all, and works only when the expected number of bad substructures is below 1. The alteration method is bolder: it allows the random object to contain some bad substructures, then removes (deletes) a small piece from each one to fix it, and argues that what remains is still large enough to be useful. You pay a little — the deleted elements — to buy yourself a much higher initial density.
The recipe has two steps. First, choose a random object more aggressively than a first-moment argument would permit, so that the expected count E[X] of bad substructures is moderate (perhaps comparable to the size of the object) rather than below 1. Second, delete one element from each bad substructure; this destroys all of them and removes at most X elements. The expected size of the surviving object is then at least (initial size) minus E[X]. By linearity this expectation is a concrete number, and by the first moment principle there exists an outcome achieving at least this expected surviving size, with no bad substructures left. Optimising the parameter that controls the aggressiveness of the random choice balances the two terms and yields the bound.
This method is responsible for many of the best-known existence bounds in extremal combinatorics. Its showcase application is graphs of high girth and high chromatic number: a random graph with the right edge density has few short cycles in expectation, so deleting one edge (or vertex) per short cycle leaves a graph with no short cycles (high girth) that is still dense enough to force a high chromatic number — a striking object whose existence is hard to see constructively. It also sharpens the Ramsey lower bound R(k,k) > (1/e)(1+o(1)) k 2^(k/2), improving the pure first-moment constant. The honest caveat is bookkeeping: you must verify that the deletion genuinely destroys every bad substructure and that the surviving object still has the property you care about, which is not automatic for non-monotone properties.
Independent sets: in G(n,p) the expected number of edges is C(n,2)p and the expected number of independent k-sets we want to avoid can be handled by deletion. Classic version: take a random graph, count its triangles (expected ~ n^3 p^3), delete one vertex per triangle (~ that many vertices), and the surviving triangle-free graph still has ~ n - n^3 p^3 vertices; optimising p ~ n^(-2/3) leaves ~ n^(1/3) vertices with no triangles yet many edges, giving a lower bound on the Ramsey-type quantity that a pure first-moment count cannot reach.
Allow bad structures, delete one element from each, keep what survives — denser start, small loss.
Deletion works cleanly for monotone-friendly targets (girth, triangle-freeness); for non-monotone properties you must check that removing elements does not destroy the property you wanted to keep.