Organising a party… under health restrictions
-------------------------------------------------
The BDF considers that the party will be a success if at least three guests all know one another—since they will then be able to get the party off to a lively start—or if, conversely, at least three guests are complete strangers to one another—since meeting new people is always stimulating. Mindful of the health risks, the BDF also wants to invite as few people as possible. How many guests must it select at random to satisfy all these constraints?
The answer is six. But how many people would it have had to invite if, instead of three, the BDF had wanted to guarantee a group of k guests who all know one another or, conversely, are complete strangers to one another? In graph-theoretic terms, the question becomes: determine the kth diagonal Ramsey number R(k).
Shapes and colours
--------------------------
Let's translate the BDF's problem into mathematical terms.
Represent each guest by a point (a vertex) on a sheet of paper, then join every pair of points with a line (an edge), coloured red if the two guests they represent know each other and blue otherwise. We have now constructed a complete graph. Requiring either a group of three people who all know one another or a group of three people none of whom know one another is therefore equivalent to requiring our graph to contain either three points joined to one another by red edges (a red triangle) or three points joined to one another by blue edges (a blue triangle). Determining R(3) means finding the minimum number of vertices the graph must have to guarantee that, no matter how its edges are coloured, it necessarily contains either a red triangle or a blue triangle. Five vertices are not enough, as the figure on the left shows.
