Combinatorics

This article records tradition as it has been passed down and reported. Its sources are not yet part of the atlas's verified catalogue.

Paul Erdos owned almost nothing and lived almost nowhere. He carried a suitcase between the homes of mathematicians around the world, arrived unannounced, said Let n be an integer, and started working. What he left behind was not a single great theorem but a way of doing an entire field: combinatorics, the mathematics of counting, arranging and finding order inside finite structures, had existed before him as a scattering of clever individual results. Erdos, working with whichever mathematician was in the room, turned it into a single connected conversation. He wrote more than 1,500 papers with more than 500 different coauthors, so many that mathematicians now compute their own Erdos number, the length of the shortest coauthorship chain back to him, half joke and half genuine record of how far his collaborative habit reached. Extremal graph theory, which asks how large or small a graph can be while still avoiding some structure, and the modern form of Ramsey theory, which asks how much order is forced on a large enough structure no matter how it is built, both took their working shape substantially through Erdos and the mathematicians he worked beside. He also pioneered the probabilistic method: to prove that a structure with some property must exist, show that a randomly built structure has that property with positive probability, so at least one example does, without ever constructing it by hand. It is now one of combinatorics' standard tools, used across the field for problems that resist direct construction entirely. Erdos never held a permanent academic position for long and gave away most of the money from the prizes he won, offering small cash rewards of his own for problems he could not solve himself, some of which still stand unclaimed.

This article records tradition as it has been passed down and reported. Its sources are not yet part of the atlas's verified catalogue.

In 1928, a young English mathematician and philosopher named Frank Ramsey was not trying to found a branch of combinatorics. He was trying to settle a question in formal logic, the decision problem for a fragment of first-order logic, and along the way he proved a lemma so useful on its own that it eventually outgrew the paper that contained it. The result now called Ramsey's theorem says, in its simplest form, that if the connections between enough objects are each colored one of two colors, some large fully one-colored group of connections is guaranteed to exist, no matter how the coloring is chosen. Color every pair of people at a large enough party as mutual acquaintances or mutual strangers, and Ramsey's theorem guarantees a group of a certain size who all know each other, or a group of a certain size who are all strangers, however the party's friendships happen to fall. The theorem generalizes far beyond parties and pairs, to larger groups, more colors and more abstract objects than people, but the party version is the one that made the result famous outside mathematics. Ramsey died in 1930 at twenty-six, having never seen his lemma become a field. Ramsey theory, the branch of combinatorics built on generalizing it, asks how large a structure has to be before some specified kind of order becomes unavoidable inside it, and the honest, almost paradoxical answer his theorem gives is that past a certain size, complete disorder is not a possibility at all. The exact size where order becomes unavoidable, the Ramsey number for a given case, is itself often extremely hard to compute; some small Ramsey numbers are still not known exactly, only bounded, decades after the theorem that guarantees their existence.