Matpic
mathematics, in pictures
Concept

Longest increasing subsequence

The longest run of terms of a sequence, not necessarily adjacent, that rises from left to right. For a random permutation of n numbers its length is close to twice the square root of n, and the same question can be asked of points in a square or a cube.

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 longest rising chain in a random cloud, by dimension. Mean longest chain divided by n^(1/d) for d = 2, 3, 4, 5 and n = 250, 500, 1000, 2000, 4000, 8000: d=2: 1.768, 1.804, 1.836, 1.863, 1.895, 1.919; d=3: 1.846, 1.928, 1.981, 2.022, 2.091, 2.125; d=4: 1.773, 1.884, 1.934, 2.026, 2.062, 2.141; d=5: 1.694, 1.762, 1.812, 1.913, 2.037, 2.030.

The longest climb in a cube

Among n random points in a square, the longest chain rising to the right has about 2√n points, a fact with a famous proof. Put the points in a cube and ask for a chain rising in all three directions, and its length is about c·n^(1/3) for a constant nobody knows. Béla Bollobás and Peter Winkler proved that the constants for every dimension stay below e and creep up to it. The upper bound is a single count of chains, and simulation shows how far below it the real chains fall.

discrete · Ramsey theory

Named alongside it

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

Random permutationFirst moment methodFluctuationsLimit shapeMonte CarloPartial orderRandom matrixRobinson schenstedStirling formulaYoung tableau

All concepts