Variable Dimension Complexes Part I: Basic Theory

Over the past several years, much attention in the field of simplicial pivoting algorithms has been focused on the new class of variable-dimension algorithms, wherein the sequence of simplices generated varies in dimension. This study is aimed at the combinatorial nature of variable-dimension algorithms. In Part I, we introduce the notion of a V-complex, short for variable-dimension complex. We show that when a labelling function is introduced on a V-complex, certain path-following properties arise. The main result of Part I is a characterization of paths on a labelled V-complex.

Part II of this study uses the path-following theory of labelled V-complexes developed in Part I to provide constructive algorithmic proofs of a variety of combinatorial lemmas in topology. We demonstrate two new dual lemmas on the n-dimensional cube, and use a generalized Sperner lemma to prove a generalization of the Knaster–Kuratowski–Mazurkiewicz covering lemma on the simplex. We also show that Tucker's lemma can be derived directly from the Borsuk–Ulam theorem. We report the interrelationships between these results, Brouwer's fixed point theorem, and the existence of stationary points on the simplex.