Combinatorial Integer Labeling Theorems on Finite Sets with an Application to Discrete Systems of Nonlinear Equations

Gerard van der Laan, Dolf Talman () and Zaifu Yang ()
Additional contact information
Zaifu Yang: Yokohama National University

No 07-084/1, Tinbergen Institute Discussion Papers from Tinbergen Institute

Abstract: Tucker's well-known combinatorial lemma states that for any given symmetric triangulation of the n-dimensional unit cube and for any integer labeling that assigns to each vertex of the triangulation a label from the set {1,2,...n,-1,-2,....-n} with the property that antipodal vertices on the boundary of the cube are assigned opposite labels, the triangulation admits a 1-dimensional simplex whose two vertices have opposite labels. In this paper we are concerned with an arbitrary finite set D of integral vectors in the n-dimensional Euclidean space and an integer labeling that assigns to each element of D a label from the set {1,2,...n,-1,-2,....-n}. Using a constructive approach we prove two combinatorial theorems of Tucker type, stating that under some mild conditions there exists two integral vectors in D having opposite labels and being cell-connected in the sense that both belong to the same unit cube. These theorems will be used to show in a constructive way the existence of an integral solution to a system of nonlinear equations under certain natural conditions.

Keywords: Sperner lemma; Tucker lemma; integer labeling; simplicial algorithm; discrete nonlinear equations (search for similar items in EconPapers)
JEL-codes: C61 C62 C68 C72 (search for similar items in EconPapers)
Date: 2007-10-31
View list of references

Downloads: (external link)
http://www.tinbergen.nl/discussionpapers/07084.pdf (application/pdf)

Related works:
Working Paper: Combinatorial Integer Labeling Thorems on Finite Sets with an Application to Discrete Systems of Nonlinear Equations (2007)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:dgr:uvatin:20070084

Access Statistics for this paper

More papers in Tinbergen Institute Discussion Papers from Tinbergen Institute
Series data maintained by Walther Schoonenberg ().