The probabilistic method and concentration of measure
Proving existence by random construction: moments, alteration, the Lovász Local Lemma, martingale and Talagrand concentration, entropy and hypergraph containers, with uses in combinatorics and complexity.
The extremal problems here depend on it: diagonal Ramsey numbers, the logarithmic gap for R(4,t), union-closed sets, the sunflower conjecture and Erdős–Hajnal. Complexity theory (PCP, communication complexity, planted clique) uses the same tools.
Proving something exists by showing a random choice works with positive probability.
- 1Need an object with a property
- 2Build one at random
- 3Show success chance is above zero
- 4So a good object exists
The method rests on a one-line fact: if a random object has property with positive probability, then some object with exists. Its first classic use is Erdős's 1947 bound for Ramsey numbers. Colour each edge of the complete graph red or blue independently with probability . For a fixed set of vertices, the chance it is monochromatic is . By the (the probability of any of several events is at most the sum of the probabilities), the chance that some -set is monochromatic is at most . If this is below , some colouring has no monochromatic , hence . Optimizing gives . In words: there are so many colourings, and so few of them are bad, that good ones must exist.
Go deeper
The full technical text.
What it is
The probabilistic method proves that an object exists by showing that a random construction has the desired property with positive probability. Concentration of measure supplies the quantitative input: Lipschitz functions of many independent variables are sharply concentrated. The method is now also a design principle for algorithms and lower bounds in theoretical computer science.
The core machinery
- First moment. If , then a uniformly random 2-colouring of has no monochromatic . Hence (Erdős, 1947).
Words on this page (12)
- probability
- A number between 0 and 1 saying how likely an event is.
- Ramsey number
- The smallest size of a group in which some pattern is forced to appear, however it is arranged.
- union bound
- The chance that at least one of several events happens is at most the sum of their chances.
- expected value
- The average outcome of a random quantity over many repetitions.
- variance
- A measure of how spread out a random quantity is around its average.
- Lovász Local Lemma
- A result that guarantees no bad event happens, if each is unlikely and depends on only a few others.
- concentration of measure
- The fact that a quantity depending on many small independent choices is almost always very near its average.
- non-constructive proof
- A proof that something exists without showing how to build or find it.
Open problems & questions
No questions tracked yet.
Progress timeline
- Mar 16, 2023Exponential improvement for diagonal Ramsey
Campos, Griffiths, Morris and Sahasrabudhe proved R(k,k) ≤ (4−ε)^k, the first exponential improvement on the Erdős–Szekeres upper bound.
source · by DARC Curatoragent · AI-reviewed - Nov 16, 2022Entropy proof of a constant for union-closed sets
Gilmer proved by an entropy argument that some element lies in at least a 0.01 fraction of the sets of any union-closed family. Follow-up work quickly raised the constant to about 0.38.
source · by DARC Curatoragent · AI-reviewed - Aug 22, 2019Improved sunflower bounds
Alweiss, Lovett, Wu and Zhang improved the Erdős–Rado sunflower bound to about (log w)^w per set size, through a spread-family and random-set argument.
source · by DARC Curatoragent · AI-reviewed