Colourful Triangles

By Ali Orozgani

Published July 23, 2023

Click here to view/download the Extended Abstract as a PDF

Abstract

In this report, we introduce and prove the two dimensional case of Sperner’s lemma regarding the number of multicoloured subtriangles in a given triangle. The one dimensional case will be stated but not proved here. We also explore applications of the lemma in other theorems and real life scenarios.

1. Introduction

We begin by introducing some terminology and definitions used throughout this report. We then state and prove Sperner’s lemma in two dimensions and explore some applications.

2. Sperner’s Lemma

3. Applications

Sperner’s lemma (in two dimensions) deals with triangles and colourings, but has applications in seemingly unrelated areas. One use of the lemma is in the game of Hex, played on an n × n diamond board with hexagonal cells. Two players each select a pair of opposite sides of the board and take turns placing pieces in the cells to form a path between their two sides of the board comprising only of their pieces. Using Sperner’s lemma, it can be proven that the game cannot end in a draw (see [5]). Perhaps more surprising is the lemma’s use in proving topological results such as the Brouwer fixed-point theorem and the hairy ball theorem (see [3]). The Brouwer fixed-point theorem states that every continuous function from a convex and compact set onto itself has at least one fixed point. Simply put, you cannot stir a cup of coffee without some atom returning to its original position. The hairy ball theorem states that you cannot continuously comb a ball of hair to have each hair tangential to the ball’s surface. It is counterintuitive to see a combinatorial result involved in the proofs of topological results, but Sperner’s lemma does exactly that.

References

[1] A. Wright, “SPERNER’S LEMMA AND BROUWER FIXED POINT THEOREM,” 2005. [Online]. Available: http://www-personal.umich.edu/ alexmw/BFPT.pdf.

[2] A. Maliwal, “Sperner’s Lemma, The Brouwer Fixed Point Theorem, the Kakutani Fixed Point Theorem, and Their Applications in Social Sciences,” Electronic Theses and Dissertations, 2016. [Online]. Available: http://digitalcommons.library.umaine.edu/etd/2574.

[3] J. Huang, “ON THE SPERNER LEMMA AND ITS APPLICATIONS,” 2004. [Online]. Available: http://jonathan-huang.org/research/old/sperner.pdf.

[4] C. Dalf´o and M. A. Fiol, “Graphs, friends and acquaintances,” 2016, doi: 10.48550/arxiv.1611.07462.

[5] S. Das and T. Szab´o, “Sperner’s Lemma and its applications,” 2017. [Online]. Available: http://discretemath.imp.fu-berlin.de/DMII-2019-20/Sperner.pdf.

Click here to return to 2023 Videos