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.

19 stemmed glasses with no set of 8 matching

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 could form a set of eight glasses with no two alike. As I placed them on the table, I thought “Aha, Ramsey theory!”

8 glasses with no two alike

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):

complete graph on six vertices, with uncolored 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 \(2^{15}\) possible colorings.

red and blue edge colorings of complete graphs on 5 and 6 vertices

More formally, the Ramsey number \(\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\) edges or a blue clique of \(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 \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 \(\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 \(\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 \(\mathcal{R}(m, n)\) values are known for only nine cases, all with very small values of \(m\) and \(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 \(\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.


This entry was posted in mathematics, modern life.

9 Responses to Ramsey Theory in the Dining Room

  1. Craig says:

    Since you raised the topic of clinking glasses, here’s a small problem I’ve been wondering about. We know that a total of \(\left(n \atop 2\right)\) clinks are required for every member of a party of \(n\) to clink with every other. But what’s the smallest number of rounds in which these clinks can occur, if in each round you can clink with at most one other person? Starting with a minimum of two people, I get a sequence \(C_n = 1,3,3,5,6…\), but I don’t yet have a closed formula. This would be useful to know in order to streamline the consumption of that first glass of wine.

    • Julian Bliss says:

      If I understand your question correctly, you want to find covering designs.
      For example, the number of rounds of clinks needed to cover the graph of all people at your party of size v, where each round is a complete graph of size k, and each person only needs to clink t-1 times is C(v,k,t), and can be determined from this website.

      https://www.ccrwest.org/cover.html

    • Brian Hayes says:

      Barry Cipra has some nifty results on “toasting schedules,” including schedules with constraints such as planarity (no one is allowed to cross arms). I don’t know if that work has ever been published.

      You out there, Barry?

      • Barry Cipra says:

        Yes, I’m here. Craig is computing the “chromatic index” for the complete graph on n vertices: that is, if you assign each round a distinct color, you want the minimum number of colors for the edges of the complete graph so that no vertex has two edges of the same color. (A person can’t clink two different people on the same round.) According to the Wikipedia entry https://en.wikipedia.org/wiki/Edge_coloring this is \(n-1\) if \(n\) is even and \(n\) if \(n\) is odd. So Craig’s sequence is in error at n=6; it should be \(1,3,3,5,5,….\) To be sure, here’s a 5-round schedule of clinks:

        1. AB, CD, EF

        2. AC, BE, DF

        3. AD, BF, CE

        4. AE, BD, CF

        5. AF, BC, DE

        The problem my son (who is a high school math teacher) proposed a few years concerned the number of rounds required if the \(n\) people are seated around a circular table and you’re not allowed to clink across another clinking couple. As I recall, what we found of interest was the *maximum* number of rounds that might be required by a “bad” clinking schedule, provided each round is “greedy” in that the only thing that keeps someone from clinking on a given round is the no-crossed-arms rule.

  2. goh says:

    A related result, for linear orders instead of equivalence relations (so now both the relation and its complement are transitive), is due to Erdős and Szekeres: any sequence of length at least (m-1)(n-1) + 1 contains a monotonically increasing subsequence of length m or a monotonically decreasing subsequence of length n. This may be proved using the pigeonhole principle as well, but the proof is more clever.

  3. D. Eppstein says:

    The result here for equivalence relations can be proved as a corollary of the Erdős– Szekeres theorem. Suppose you have (m-1)(n-1)+1 glasses, and you want to show that there are either m of them that are all different or n of them that are all the same. Line up the glasses in a row, with all the glasses of the same type contiguous, and number each glass by its position in the row, but then after assigning these numbers reverse the order of each contiguous group of glasses of the same type. Then by Erdős– Szekeres, there must be either an ascending sequence of m glass numbers or a descending sequence of n. But with this numbering, an ascending subsequence of glasses must be all different and a descending subsequence must be all the same.

  4. Gerry Myerson says:

    I believe the answer to Criag’s question is n if n is odd, n - 1 if n is even. If n is odd, arrange the n members in a regular n-gon, and in each round, pick out a member who gets a bye, draw a line L through that member and the center, and pair the other members by drawing chords perpendicular to L. If n is even, temporarily ignore one member, and solve the n - 1 member problem; then in each round, pair the temporarily ignored member with the member given a bye in that round. The high-faluting name for this is decomposing the complete graph into 1-factors.

Leave a Reply to Craig Cancel reply

Your email address will not be published. Required fields are marked *

*

In addition to the basic HTML formatting options offered by the buttons above, you can also enter LaTeX math commands. Enclose LaTeX content in \( ... \) for inline mode or \[ ... \] for display mode.