Tucker's lemma

Let T be a triangulation of the closed n-dimensional ball

Assume T is antipodally symmetric on the boundary sphere

be a labeling of the vertices of T which is an odd function on

Then Tucker's lemma states that T contains a complementary edge - an edge (a 1-simplex) whose vertices are labelled by the same number but with opposite signs.

[2] Later, constructive proofs were found, which also supplied algorithms for finding the complementary edge.

[3][4] Basically, the algorithms are path-based: they start at a certain point or edge of the triangulation, then go 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 a simplex which contains a complementary edge.

An easier proof of Tucker's lemma uses the more general Ky Fan lemma, which has a simple algorithmic proof.

Start outside the ball and consider the labels of the boundary vertices.

edges on the boundary must be odd, there must be a new, unvisited

This walk must end inside the ball, either in a

The run-time of the algorithm described above is polynomial in the triangulation size.

This is considered bad, since the triangulations might be very large.

It would be desirable to find an algorithm which is logarithmic in the triangulation size.

However, the problem of finding a complementary edge is PPA-complete even for

This implies that there is not too much hope for finding a fast algorithm.

Additionally, each result in the top row can be deduced from the one below it in the same column.