Concept

Probabilistic method

Proving that an object with some property exists by showing that a randomly chosen one has it with positive probability. The argument produces nothing anyone can look at, and in several settings the objects it promises have never been constructed.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Six people, and the trio that cannot be avoided. The fifteen pairs among six people, coloured at random. Whatever the colouring, three people are all mutual acquaintances or all mutual strangers — here 1, 2, 5.

Six people at a party

Among any six people, three are mutual acquaintances or three are mutual strangers. Five is not enough, and the arrangement that saves five is a pentagon. Beyond that the numbers become unknowable.

discrete · ramsey theory

The expected number of monochromatic sets, and where it drops below one. The logarithm of the expected number of single-coloured 4, 5, 6-point sets in a random two-colouring, plotted against the number of points, with the crossing of one marked for each.

The colouring nobody has ever seen

Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.

discrete · ramsey theory

Named alongside it

The objects these essays reach for when they reach for this one.

Complete graph Counting argument Existence proof Nonconstructive Ramsey number Binomial coefficient Expectation Graph Independence Parity Pigeonhole principle Union bound

All concepts