
For most of the past century, mathematicians have been exploring the limits of Ramsey theory, the study of order hiding inside chaos — or, more accurately, how much disorder can be packed into a system before order must inevitably emerge. Progress has been frustratingly slow, but now a potential breakthrough result is pointing the way toward more rapid advances — and a clearer view of the still-hazy transition between randomness and structure.
The systems in question are called graphs: mathematical networks made of points connected by lines. These graphs can represent anything interconnected — from friendships to airline routes to molecules. And as any graph grows, sooner or later it will include either a tight-knit group in which everything is connected to everything else — a "clique" — or encompass a large collection of points with no connections between them at all, known as an "independent set."












Comment: