Triangulated Spheres and Colored Cliques
by
Andrei Kotlov
Aptima, Inc.

Part 1: We prove the following conjecture of Ron Aharoni, stated informally: Every (d-1)-dimensional PL (PL = peicewise linear) triangulated sphere can be extended to a triangulation of the ball by a series of adding a vertex of degree at most 2d (at the time the vertex is added). For example, the interior of the n-gon (1-dim sphere) can be triangulated by adding n-3 vertices of degree exactly 4 (at the time the vertex is added). Other similar results will be shown.

Part 2: Following work of Aharoni and Haxell, we show how the results from part 1 of our talk imply Hall's Bipartite Matching Theorem.

Date received: November 13, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafp-17.