The perfect Christmas party guest list
Ramsey numbers; when order matters
“I don’t feel the least humble before the vastness of the heavens. The stars may be large, but they cannot think or love, and these are qualities which impress me far more than size does.” — F. P. Ramsey.
English-born Frank Plumpton Ramsey (1903–1930) made an essential contribution to philosophy, economics, and mathematics during his short life. He was one of the last century’s greatest minds; nevertheless, most of Ramsey’s ideas were not appreciated until decades later. Feasibly he was ahead of his time and therefore misunderstood.
Ramsey was genial, open, jolly, humble, and modest. Perhaps his modesty did not help him to become very popular in the academic circles. But, arriving at the University of Cambridge in 1920, the influential economist John Maynard Keynes described him as “by far the most brilliant student who has appeared for many years in the border country between philosophy and mathematics.”
While employed as a mathematician at Cambridge, Ramsey only published one paper in this field, which yielded impressive results. Its first contribution was closer to philosophy than mathematics, was the seed of the Dutch Book argument. Ramsey’s Test was its second contribution, in which its initial and modified versions have influenced the development of the logics of conditionals and the present artificial intelligence. Ramsey’s third contribution, proved in the paper “On a problem of formal logic” (1930), was in the form of two closely related theorems; the Infinite and Finite Ramsey theorems, a generalization of the Pigeonhole Principle stated by Dirichlet almost one century earlier, 1832.
Ramsey theory
Ramsey’s Theorems, later popularized in an influential paper of Paul Erdős and George Szekeres (1935), showed that there is always some order in the world's randomness. A few years later, Ramsey’s Theorems originated the establishment of Ramsey Theory, a specific field in the branch of mathematics known as Combinatorics.
These days, Ramsey’s Theory still has applications in logic and is an exciting subject since its basic ideas can be understood easily. It is also an active research area since it raises some difficult and challenging questions.
The fundamental kind of question Ramsey’s theory asks is: can one always find order in randomness? And if so, how much?
The (Christmas) party problem
One of the most known application examples of Ramsey’s Theory is the Party Problem. Mathematicians have been working on it for nearly a century because on maybe what you are pursuing; the answer can be complicated.
The party problem consists of finding the minimum number of guests that must be invited to a (Christmas) party so that at least r will know each other (are friends) or at least s will not know each other (strangers). The solutions to this problem are known as Ramsey numbers, R(r,s).
Theorem. For two positive fixed integers r and s. Every sufficiently large party will contain a group of r mutual friends or a group of s mutual non-friends.Ramsey numbers
Ramsey numbers can be understood with a graph (a set of vertices and a set of edges between them). Consider a graph with N vertices, and connect each of them to form a complete graph. That is, a graph where there is always a path between any two vertices:
Consider a 6 vertices complete graph, where each vertex is a guest, and use colors to illustrate the type of friend relationship between guests. For example, friends are connected by a red edge, and a blue edge connects non-friends. Notice can be found a group of 3 friends represented by a red triangle and 3 non-friends by a blue triangle. Therefore, and without loss of generality, R(3,3) ≤ 6.
The Christmas party
For example, imagine that you want to organize a Christmas party by considering the premise of inviting the minimum number of guests that guarantees that at least three persons are all friends or three persons all non-friends. To ensure this, the minimum number of people that shall be invited is 6, R(3,3) = 6. In other words, in this case, every two guests are either friends or strangers.
What if we would like four persons to be friends or non-friends? What is the minimum number of persons who must invite a party to be confident about this premise? This question has been answered. It is R(4,4) = 18.
What if we would like five persons to be friends or non-friends? In this case, the smallest number of persons invited to the Christmas party to be guaranteed is not known, 43 ≤ R(5,5) ≤ 48.
Suppose aliens invade the earth and threaten to obliterate it in a year unless human beings can find the Ramsey number for red five and blue five. We could marshal the world’s best minds and fastest computers, and within a year, we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack. — Paul Erdős (1913–1996).
While the (Christmas) party problem is easy to describe and perhaps sounds relatively simple, it is notoriously difficult.
Therefore, enjoy your Christmas party, and maybe you can use this short story to challenge your guests with a Mathematical/Philosophical conversation.
Thanks for reading.
Code used to illustrate this story:
