Matpic
mathematics, in pictures
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 5 essays across 3 fields — 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 A triangle appears when the count says it should. The measured probability of containing a triangle against the edge chance, on graphs of 200 points, beside the expected number of triangles capped at one.

Finding a threshold with two moments

Every monotone property of a random graph has a threshold, and locating one is nearly always the same two calculations — count what the property needs, and check the count does not concentrate on rare cases. The triangle is where the method is cleanest.

probability · Random graphs The complete graph on 7 points, drawn straight with 9 crossings. A straight-line drawing of the complete graph on 7 vertices with 9 crossings, the minimum for straight drawings; each crossing comes from four vertices in convex position.

The crossings a graph cannot avoid

Five points all joined need one crossing, six need three, seven need nine. Euler's formula gives a lower bound that grows like the square of the number of points and is badly wrong; a sampling trick turns the same formula into a bound that grows like the fourth power and is right to within a constant. And for drawings with straight edges the count turns out to be something else entirely: the number of quadrilaterals the points make.

discrete · Planarity Three polynomials of signs around the circle. The size of the polynomial around the unit circle divided by √64 for all-plus, random and Rudin–Shapiro sign polynomials of length 64; maxima 8.00, 2.50, 1.41.

The flattest polynomials of signs

A polynomial whose coefficients are all +1 or −1 has average size √n on the unit circle. Keeping it near √n everywhere is the problem Littlewood posed: the Rudin–Shapiro polynomials never exceed √2 times it, searching every sign pattern up to length 22 finds the best are the Barker sequences, and whether the maximum can come arbitrarily close to √n is still open.

algebra · Polynomial roots

Named alongside it

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

Complete graphCounting argumentExistence proofExpectationNonconstructiveRamsey numberAutocorrelationBinomial coefficientConjectureConvexityCounting two waysCrossing number

All concepts