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

Gerard van der Laan, Adolphus Talman and Zaifu Yang

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

Abstract: This discussion paper resulted in a publication in the 'Journal of Optimization Theory and Applications', 2010, 144, 391-407.

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: C58 C61 C62 C68 C72 (search for similar items in EconPapers)
Date: 2007-10-31
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://papers.tinbergen.nl/07084.pdf (application/pdf)

Related works:
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: https://EconPapers.repec.org/RePEc:tin:wpaper:20070084

Access Statistics for this paper

More papers in Tinbergen Institute Discussion Papers from Tinbergen Institute Contact information at EDIRC.
Bibliographic data for series maintained by Tinbergen Office +31 (0)10-4088900 ().