Party Games

Like driftwood spars, which meet and pass

Upon the boundless ocean-plain,

So on the sea of life, alas!

Man meets man,—meets and quits again.

—Matthew Arnold (1822-1881), "Switzerland"

In work and play. from hour to hour and year to year, we pass from one gathering to another. Sometimes we are surrounded by people we know; sometimes we find ourselves in the presence of strangers. The restless ebb and flow of human concourse appears to be random, yet there are curious patterns present in the composition of these random groupings of strangers and acquaintances who come and go.

Whether in large crowds, modest social gatherings, or small groups, people congregate in all sorts of combinations of strangers and acquaintances. Consider the varied possibilities in a party of six.

You're one of six people at a dinner party. You look across the table at your five companions. You would undoubtedly find that the dinner party includes either a group of at least three people who all know one another or a group of at least three people who don't know one another.

The reason for this certainty lies in a mathematical proof that any gathering of six people will always automatically include one or the other of these two groupings. No such guarantee is possible when five or fewer people are present.

To prove that any party of six must contain at least three acquaintances or at least three strangers, you could write down all the possible combinations, starting with a group in which everyone knows one another. However, there are 32,768 such possibilities.

This number reflects the fact that any pair in a group of six must be either acquainted or strangers. Moreover, there are six choices of people for the first member of a pair, which leaves five choices for the second member of the pair, for a total of 30 possibilities. Because the order of the choices in a particular case doesn't matter (picking Alice first and then Barry is the same as picking Barry, then Alice), the number of possibilities that count is down to 30/2, or 15. Overall, for two possible relations (stranger or acquaintance), the number of possibilities is 2¹⁵, or 32,768.

Luckily, there's a shorter path to a proof. You need consider only two particular cases.

Suppose a party is attended by the conveniently named guests Alice, Barry, Charles, Diana, Edith, and Frank. Of the five partygoers Barry, Charles, Diana, Edith, and Frank, either at least three are friends of Alice or at least three are strangers to Alice.

Suppose Alice knows Barry, Charles, and Diana. If either Barry and Charles, Barry and Diana, or Charles and Diana are friends, then Alice and the acquainted pair make three people who know one another. Otherwise Barry, Charles, and Diana are mutual strangers.

In the second case, suppose Alice knows only two (or fewer) of the others, say, Barry and Charles. If either Diana and Edith, Diana and Frank, or Edith and Frank are strangers, then Alice and the unacquainted pair make three people who do not know one another. Otherwise, Diana, Edith, and Frank are mutual acquaintances.

This argument covers all possible cases for each of the six dinner-party guests.

The result represents a special case stemming from a branch of mathematics known as Ramsey theory, named for the mathematician Frank Plumpton Ramsey (1903-1930).

Instead of talking about six people, you could consider groups consisting of any number of people. Instead of specifying just two relationships (acquaintances and strangers), you could have any number of mutually exclusive relations. For example, you could consider people (or nations) who are allies, foes, and neutral parties—representing three mutually exclusive relationships—embroiled in a widespread conflict.

In general, Ramsey theory concerns the existence of highly regular patterns in sufficiently large sets of randomly selected objects, whether they are gatherings of people, sequences of randomly generated numbers, randomly placed points in the plane, or even stars in the night sky.

Tabulating the outcomes of 2,500 flips of a coin by sequentially filling in the squares of a 50-by-50 grid (black for tails, white for heads) produces a random array. It is not difficult, however, to pick out fragments of patterns among the black or white squares, in much the same way that you can find patterns among stars randomly scattered across the sky. In this case, one array represents tosses of a fair coin and the other represents tosses of a slightly biased coin. Can you tell which is which?

It's straightforward to convert a party puzzle into a graph theory problem. In general, a graph consists of an array of points, or vertices, connected by straight lines, which are often called edges.

In the dinner-party case, you can draw a point for each of the six people present in the group. You can then draw lines to join the points, with each line colored red to signify two people who know each other or blue to mean the two people are strangers. When all pairs of points are joined, the resulting network of points and lines is known as a complete graph.

Depending on the relationships specified in a given case, such a graph may contain only red lines (all acquaintances), only blue lines (all strangers), or a mixture of red and blue lines joining the points. The problem comes down to proving that no matter how the lines are colored, you can't avoid producing a red triangle (representing three mutual acquaintances) or a blue triangle (three strangers).

A graph depicting relationships among six people at a party, where red lines link acquaintances and blue lines connect strangers.

Such a coloring is guaranteed for a complete graph of six points, but not necessarily for a graph of five or fewer points, as the following figure demonstrates.

This graph representing the relationships of five people shows that it is possible to obtain a gathering in which there is no group of three strangers or three acquaintances. In other words, there is no triangle in the diagram that is made up entirely of red or blue lines.

Wolfgang Slany turned the party problem into a two-person game he called HEXI (see his paper "Graph Ramsey Games"). You and your opponent take turns coloring in the uncolored edges of a complete graph laid out as a hexagon, with each player using a different color. The first person to build a triangle with all three edges of the same color loses.

Slany also had a variant of the game in which a player may choose to color in more than one edge with each turn.

In both cases, Ramsey theory ensures that HEXI never ends in a draw.

Previously: The Long Run

Next: Pigeonhole Congestion