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 Medium level:

# Sperner's Lemma

 Figure 1

Divide a triangle T into lots of baby triangles, so that baby triangles only meet at a common edge or a common vertex. Label each main vertex of the whole triangle by 1, 2, or 3; then label vertices on the (12) side by either 1 or 2, on the (23) side by either 2 or 3, and the (13) side by either 1 or 3. Label the points in the interior by any of 1, 2, or 3. For instance, see Figure 1.

Fun Fact: any such labelling must contain an baby (123) triangle! (In fact, there must be an odd number!)

Actually, a version of Sperner's Lemma holds in all dimensions. Can you figure out how it generalizes?

Sperner's Lemma is equivalent to the Brouwer fixed point theorem.

Presentation Suggestions:
Have everyone make their own labelled triangle and see how many (123) triangles they have in their picture.

The Math Behind the Fact:
There are many proofs of this fact. Some short non-constructive proofs rely on parity arguments. Constructive proofs are the key to many fixed point algorithms as well as fair division procedures. See the reference.

Su, Francis E., et al. "Sperner's Lemma." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References:
F.E. Su, "Rental harmony: Sperner's lemma in fair division",
Amer. Math. Monthly, 1999.

Keywords:    triangles, combinatorics
Subjects:    combinatorics
Level:    Medium
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
3.85
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!