Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  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
All rights reserved.

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

Dinner Party Problem

Figure 1
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.

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

Keywords:    graph theory, Ramsey theory
Subjects:    combinatorics
Level:    Advanced
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
3.98
 
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!
Get the Math Fun Facts
iPhone App!

Want another Math Fun Fact?

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