hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, here is a Fun Fact at the Advanced level:

# Dinner Party Problem

 Figure 1

How many people must you have at dinner to ensure that there are a subset of 3 people who all either mutual acquaintances, or mutual strangers?

We can model this using graph theory; for background see the Fun Fact Six Degrees of Separation. Let people be vertices, and draw a red edge between two people if they know each other, and a blue edge if they do not. So every pair of people are connected by either a red or blue edge.

The question then becomes, what is the least number of vertices for which every complete red-blue graph on those vertices has either a red or blue triangle?

Answer: 6 people! First we show that 6 people are enough: take any vertex, Fred. Fred has 5 edges emanating from him; at least 3 are the same color. Suppose without loss of generality it is red. If any of those 3 people that Fred knows know each other, then we have a red triangle! If none of those 3 know each other, we have a blue triangle!

Now, using red-blue graphs, can you draw a red-blue complete graph on 5 vertices with no blue nor red triangle? (This shows that 5 people are not enough.) See the Figure for a solution (it appears after several seconds).

Presentation Suggestions:
Bring colored chalk into the class; draw pictures as you are giving the proof. It doesn't matter if students don't follow the exact argument in class--- they will probably go home and want to think about it anyways--- but they will draw the pictures you draw and it will help them construct the argument later.

The Math Behind the Fact:
Generalizations of this problem, involving the least number of people you have to invite to ensure subgraphs of other types, fall under the category of something called Ramsey Theory.

Su, Francis E., et al. "Dinner Party Problem." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

Keywords:    graph theory, Ramsey theory
Subjects:    combinatorics
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
3.94
current
rating
Click to rate this Fun Fact...
*   Awesome! I totally dig it!
*   Fun enough to tell a friend!
*   Mildly interesting
*   Not really noteworthy
and see the most popular Facts!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!