Ky Fan lemma

Short description: Combinatorial lemma

In mathematics, Ky Fan's lemma (KFL) is a combinatorial lemma about labellings of triangulations. It is a generalization of Tucker's lemma. It was proved by Ky Fan in 1952.

In this example, where n = 2, there is no 2-dimensional alternating simplex (since the labels are only 1,2). Hence, there must exist a complementary edge (marked with red).

Definitions

KFL uses the following concepts.

• [math]\displaystyle{ B_n }[/math]: the closed n-dimensional ball.
  • [math]\displaystyle{ S_{n-1} }[/math]: its boundary sphere.
• T: a triangulation of [math]\displaystyle{ B_n }[/math].
  • T is called boundary antipodally symmetric if the subset of simplices of T which are in [math]\displaystyle{ S_{n-1} }[/math] provides a triangulation of [math]\displaystyle{ S_{n-1} }[/math] where if σ is a simplex then so is −σ.
• L: a labeling of the vertices of T, which assigns to each vertex a non-zero integer: [math]\displaystyle{ L: V(T) \to \mathbb{Z}\setminus\{0\} }[/math].
  • L is called boundary odd if for every vertex [math]\displaystyle{ v\in S_{n-1} }[/math], [math]\displaystyle{ L(-v) = -L(v) }[/math].
• An edge of T is called a complementary edge of L if the labels of its two endpoints have the same size and opposite signs, e.g. {−2, +2}.
• An n-dimensional simplex of T is called an alternating simplex of T if its labels have different sizes with alternating signs, e.g.{−1, +2, −3} or {+3, −5, +7}.

Statement

Let T be a boundary-antipodally-symmetric triangulation of [math]\displaystyle{ B_n }[/math] and L a boundary-odd labeling of T.

If L has no complementary edge, then L has an odd number of n-dimensional alternating simplices.

Corollary: Tucker's lemma

By definition, an n-dimensional alternating simplex must have labels with n + 1 different sizes.

This means that, if the labeling L uses only n different sizes (i.e. [math]\displaystyle{ L: V(T) \to \{+1,-1,+2,-2,\ldots,+n,-n\} }[/math]), it cannot have an n-dimensional alternating simplex.

Hence, by KFL, L must have a complementary edge.

Proof

KFL can be proved constructively based on a path-based algorithm. The algorithm it starts at a certain point or edge of the triangulation, then goes from simplex to simplex according to prescribed rules, until it is not possible to proceed any more. It can be proved that the path must end in an alternating simplex.

The proof is by induction on n.

The basis is [math]\displaystyle{ n=1 }[/math]. In this case, [math]\displaystyle{ B_n }[/math] is the interval [math]\displaystyle{ [-1,1] }[/math] and its boundary is the set [math]\displaystyle{ \{-1,1\} }[/math]. The labeling L is boundary-odd, so [math]\displaystyle{ L(-1)=-L(+1) }[/math]. Without loss of generality, assume that [math]\displaystyle{ L(-1)=-1 }[/math] and [math]\displaystyle{ L(+1)=+1 }[/math]. Start at −1 and go right. At some edge e, the labeling must change from negative to positive. Since L has no complementary edges, e must have a negative label and a positive label with a different size (e.g. −1 and +2); this means that e is a 1-dimensional alternating simplex. Moreover, if at any point the labeling changes again from positive to negative, then this change makes a second alternating simplex, and by the same reasoning as before there must be a third alternating simplex later. Hence, the number of alternating simplices is odd.

The following description illustrates the induction step for [math]\displaystyle{ n=2 }[/math]. In this case [math]\displaystyle{ B_n }[/math] is a disc and its boundary is a circle. The labeling L is boundary-odd, so in particular [math]\displaystyle{ L(-v) = -L(v) }[/math] for some point v on the boundary. Split the boundary circle to two semi-circles and treat each semi-circle as an interval. By the induction basis, this interval must have an alternating simplex, e.g. an edge with labels (+1,−2). Moreover, the number of such edges on both intervals is odd. Using the boundary criterion, on the boundary we have an odd number of edges where the smaller number is positive and the larger negative, and an odd number of edges where the smaller number is negative and the larger positive. We call the former decreasing, the latter increasing.

There are two kinds of triangles.

• If a triangle is not alternating, it must have an even number of increasing edges and an even number of decreasing edges.
• If a triangle is alternating, it must have one increasing edge and one decreasing edge, thus we have an odd number of alternating triangles.

By induction, this proof can be extended to any dimension.