Matpic
mathematics, in pictures
Concept

Random permutation

An ordering of a list chosen so that every one of the possible orderings is equally likely. Shuffling a pack of cards thoroughly produces one, and many guarantees about algorithms hold on average over such an ordering rather than for every order.

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

400 random points and their longest rising chain, 34 long. 400 uniform random points in a unit square with the longest chain increasing in both coordinates marked: 34 points, against 2√n = 40.0.

The longest climb of a shuffle

Erdős and Szekeres guarantee that any n distinct numbers hold a climb or a fall of √n, and there are orders that allow nothing more. Shuffle a deck at random instead and the longest climb is almost exactly 2√n — with fluctuations of size n to the power one-sixth, distributed exactly as the largest eigenvalue of a large random matrix.

discrete · Ramsey theory The same rule in the adversary's order and in a random order. Two copies of the 8-a-side triangular graph matched greedily with the worst ranking: 4 matched in the adversary's order, 5 in a random order (average 5.30).

Matching when the arrivals are shuffled

An adversary who chooses the order in which applicants arrive can hold any fixed matching rule to half the best. Take the order away and let it be random, and the plainest rule of all — give each arrival its first free place in a fixed list — rises to 1 − 1/e, because shuffling the arrivals turns out to be exactly the trick RANKING plays with the places, seen from the other side. Shuffle both and the guarantee rises again, to somewhere between 0.696 and 0.727, and where in that interval it lies is not known.

discrete · Halls theorem

Named alongside it

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

Bipartite graphCompetitive ratioFluctuationsGreedy algorithmLimit shapeLongest increasing subsequenceMatchingMonte CarloOnline algorithmRandom matrixRandomisationRobinson schensted

All concepts