Why Complete Disorder Is Mathematically Impossible

By Jordana Cepelewicz

Each week Quanta Magazine explains one of the most important ideas driving modern research. This week, our math editor, Jordana Cepelewicz , discusses Ramsey theory, the mathematical study of how order inevitably emerges from chaos.

When he died in 1930 at just 26 years old, Frank Ramsey had already made transformative contributions to philosophy, economics and mathematics. John Maynard Keynes sought his insights; Ludwig Wittgenstein admired him and considered him a close friend. In his lifetime, Ramsey published only eight pages on pure math: the beginning of a paper about a problem in logic. But in that work, he proved a theorem that ultimately led to a whole new branch of mathematics — what would later be called Ramsey theory.

His theorem stated that if a system is large enough, then no matter how disordered it might be, it’s always bound to exhibit some sort of regular structure. Order inevitably emerges from chaos; patterns are unavoidable. Ramsey theory is the study of when this happens — in sets of numbers, in collections of vertices and edges called graphs, and in other systems. The mathematicians Ronald Graham and Joel Spencer likened it to how you can always pick out patterns among the stars in the night sky.

Problems in Ramsey theory look like this: Say you have a graph of five vertices, where each pair of vertices is connected by an edge. Can you color each edge red or blue in such a way that you don’t end up creating a red or blue triangle? Yes. But if you start with six or more vertices, you no longer can. You’re always guaranteed to have a monochromatic triangle, no matter how you color your edges.

Mathematicians use so-called Ramsey numbers to measure how big graphs must get before they inevitably contain such a monochromatic structure, or clique. The Ramsey number R(3) is 6, because a graph must have at least six vertices to guarantee the presence of a red or blue clique of size 3. But Ramsey numbers are notoriously difficult to prove. Mathematicians know that R(4) is 18, but they have yet to compute the exact value of R(5) and beyond.

Efforts to solve Ramsey-type problems have led mathematicians to develop some of their most important techniques, like the probabilistic method. Ramsey theory has also been applied to the study of communications networks, information transmission and more.

What’s New and Noteworthy

In the century since Ramsey inadvertently founded Ramsey theory, it’s been a particularly active area of research, with several major breakthroughs in just the past few years.

Last year, for instance, four mathematicians proved a new, more accurate upper bound on Ramsey numbers — the first advance of its kind since 1935. “I was floored” on hearing the news, one mathematician said. “I was literally shaking for half an hour to an hour.” Just a few months later, mathematicians made progress on estimates of asymmetric Ramsey numbers, which deal with graphs that are guaranteed to have red or blue cliques of different sizes. Mathematicians once again found this progress “completely shocking.”

Also shocking: Some of the mathematicians making headway on these problems are even younger than Ramsey was when he launched the field. In 2020, Quanta wrote about Ashwin Sah, now a graduate student at the Massachusetts Institute of Technology, who as an undergraduate proved major results in Ramsey theory and related areas.

Many of these recent breakthroughs involve the study of graphs that grow infinitely large. But mathematicians are also still trying to make sense of small Ramsey numbers, which remain stubbornly elusive. And they’re not just looking for monochromatic cliques in graphs; they also want to analyze the emergence of other structures, like branching, treelike patterns, as well as loops called Hamiltonian cycles.

In fact, Ramsey theory isn’t just about inevitable patterns found in graphs. Hidden structure emerges in lists of numbers, strings of beads and even card games. In 2019, for example, mathematicians studied collections of sets that can always be arranged to resemble the petals of a sunflower. That same year, Quanta reported on research into sets of numbers that are guaranteed to contain numerical patterns called polynomial progressions. And last year, mathematicians proved a similar result, about sets of integers that must always include three evenly spaced numbers, called arithmetic progressions.

In its hunt for patterns, Ramsey theory gets to the core of what mathematics is all about: finding beauty and order in the most unexpected places.

Around the Web

• The New Yorker published a profile of Frank Ramsey in 2020, describing him as “the man who thought too fast.”
• Scientific American has a 1990 article by Graham and Spencer on the birth of Ramsey theory and some of its most important problems.
• Plus magazine walks through a proof of Ramsey’s “friends and strangers” theorem. In a group of six or more people, you’re always guaranteed to find either a clique of three people who all know each other, or a clique of three strangers.