Ramsey Theory in the Dining Room

Friends were coming for dinner, and we would be eight at the table. When I pulled the wine glasses out of the cupboard, I found quite a miscellaneous array of stemware—an equilibrium distribution reached after many years of occasional additions and steady attrition.

When I looked over the collection, I quickly realized that we could not form a set of eight matching glasses. The closest we could come was 6 + 2. But then I saw that we couldform a set of eight glasses with no two alike. As I placed them on the table, I thought “Aha, Ramsey theory!”

At the root of Ramsey theory lies this curious assertion: If a collection of objects is large enough, it cannot be entirely without structure or regularity. Dinner parties offer the canonical example: If you invite six people to dinner, then either at least three guests will already be mutual acquaintances (each knows all the others) or at least three guests will be strangers (none has met any of the others). This result has nothing to do with the nature of social networks; it is a matter of pure mathematics, first proved by the Cambridge philosopher, mathematician, and economist Frank Plumpton Ramsey (1903–1930).

Ramsey problems become a little easier to reason about when you transpose them into the language of graph theory. Consider a complete graph on six vertices (where every vertex has an edge connecting it with every other vertex, for a total of 15 edges):

The aim is to color all the edges of the graph red or blue in such as way that no three vertices are connected by edges of the same color (forming a “monochromatic clique”). The red edges might signify “mutually acquainted” and the blue ones “strangers.” As the diagrams below show, it’s easy to find a successful red-and-blue coloring of a complete graph on five vertices: In the pentagon at left, each vertex is connected to two other vertices by red edges, but those vertices are connected to each other by a blue edge. Thus there are no red triangles, and a similar analysis shows there are no blue ones either. The same scheme doesn’t work for a six-vertex graph, however. The attempt shown at right fails with two blue triangles. In fact, any two-coloring of this graph has monochromatic triangles. Ramsey’s 1928 proof of this assertion is based on the pigeonhole principle. These days, we also have the option of just checking all 215$2^{15}$ possible colorings.

More formally, the Ramsey number R(m,n)$\mathcal{R}(m,n)$ is the number of vertices in the smallest complete graph for which a two-coloring of the edges is certain to yield a red clique of m$m$edges or a blue clique of n$n$ edges (or both). In applying this notion to the wine glass problem, I was asking: How many glasses do I need to have in my cupboard to ensure there are either eight all alike or eight all different?

---

At dinner that night we cheerfully clinked our eight dissimilar glasses. Maybe we even completed the full round of (8×7)/2=28$(8\times 7)/2=28$ clinks. Later on, after everyone had gone home and all the glasses were washed, my thoughts returned to Ramsey theory. I was wondering, “What is the value of R(8,8)$\mathcal{R}(8,8)$, the smallest complete graph that is sure to have a monochromatic subgraph of at least eight vertices? Lying awake in the middle of the night, I worked out a solution in terms of wine glasses.

Suppose you start with an empty cupboard and add glasses one at a time, aiming to assemble a collection in which no eight glasses are all alike and no eight glasses are all different. You could start by choosing seven different glasses—but no more than seven, lest you create an all-different set of eight. Every glass you subsequently add to the set must be the same as one of the original seven. You can keep going in this way until you have seven sets of seven identical glasses. When you add the next glass, however, you can’t avoid creating a set that either has eight glasses all alike or eight all different. Thus it appears that R(8,8)=72+1=50$\mathcal{R}(8,8)=7^2+1=50$.

The moment I reached this conclusion, I knew something was dreadfully wrong. Computing Ramsey numbers is hard. After decades of mathematical and computational labor, exact R(m,n)$\mathcal{R}(m,n)$ values are known for only nine cases, all with very small values of m$m$and n$n$. Lying in the dark, without Google at my fingertips, I couldn’t remember the exact boundary between known and unknown, but I was pretty sure that R(8,8)$\mathcal{R}(8,8)$ lay on the wrong side. The idea that I might have just calculated this long-sought constant in my head was preposterous. And so, in a state of drowsy perplexity, I fell asleep.

Next morning, the mystery evaporated. Where did my reasoning go wrong? You might want to think a moment before revealing the answer.

In the classic Ramsey-number problem, we ask about cliques of dinner guests who are all mutually acquainted or all strangers. Superficially, the wine-glass problem seems similar: We are looking for sets of glasses that are all alike or all different. But the analogy is imperfect. Alike is a transitive relation, essentially a version of equal. Thus if a=b$a=b$ and b=c$b=c$, it follows that a=c$a=c$. The mutual acquaintance relation doesn’t work this way. If a$a$and b$b$ know each other, and b$b$ and c$c$ know each other, we can’t necessarily conclude that a$a$and c$c$ are also mutual acquaintances.

Because alikeness is transitive, a set of all-alike glasses is always a clique, and this fact dramatically reduces the number of possible red-and-blue colorings of the full graph. In this way a very hard problem becomes trivially easy. For the all-equal-or-all-different case, the minimum graph size to guarantee a monochromatic clique is given by a simple formula: S(m,n)=(m−1)(n−1)+1$\mathcal{S}(m,n)=(m-1)(n-1)+1$. These are not Ramsey numbers; perhaps they might be called semi-Ramsey numbers, since they apply to situations where one relation is transitive and the other is not. (Note that the opposite of alikeness is intransitive: a≠b$a\ne b$and b≠c$b\ne c$ does not imply a≠c$a\ne c$.)

By the way, the value of R(8,8)$\mathcal{R}(8,8)$ is not known. It is bracketed by a lower bound of 282 and an upper bound of 1,870. For the current status of Ramsey number calculations, see the survey maintained by Stanisław P. Radziszowski.

This entry was posted in mathematics, modern life.

Posted on 30 November 2015 by Brian Hayes