Ramsey theory most commonly asks questions either about the integers or about graphs. A graph, in this context, refers to collections of points called nodes, connected by lines called edges, which can have properties like length or \u2014\u00a0as in the case of the Ramsey numbers \u2014 color.<\/p>\n

A complete graph is both complicated and simple \u2014 every node is connected to every other node. The Ramsey number describes how many nodes a complete graph must contain to be forced to have a particular structure. Say the edges of a complete graph are assigned one of two colors: red or blue. And say you try to color the edges in a way that avoids connecting a group of nodes with edges of the same color. In 1930, Frank Ramsey proved that if a graph is big enough, it becomes impossible to avoid creating what mathematicians call a monochromatic clique \u2014 a group of nodes whose common edges are either all red, or all blue.<\/p>\n

How big, exactly, must a graph be before a monochromatic clique is forced to emerge? The answer depends on the size of the clique. Ramsey showed that there exists a number, now called the Ramsey number, representing the minimum number of nodes for which a monochromatic clique of a given size must exist, no matter how the edges are colored.<\/p>\n

But the size of the Ramsey number is hard to pin down. In 1935, five years after Ramsey showed it exists, Erd\u0151s and George Szekeres provided a new, tighter upper bound on how big the Ramsey number is for a clique of a given size. But since then, mathematicians have barely been able to improve on Erd\u0151s and Szekeres\u2019 calculation.<\/p>\n

To get a better intuition for what this means, consider a classic example, in which nodes represent guests at a party. Color the edge between any two guests red if they\u2019ve met before, and blue if they haven\u2019t. You can pick any clique size you like \u2014 invite enough people to the party, and you can\u2019t avoid either inviting a group of people who all know one another (a clique in multiple senses of the word) or inviting a group of people who have never met before.<\/p>\n