Combinatorial Integer Labeling Theorems on Finite Sets with Applications

G. Laan (), Adolphus Talman and Zaifu Yang
Additional contact information
G. Laan: VU University Amsterdam

Journal of Optimization Theory and Applications, 2010, vol. 144, issue 2, No 10, 407 pages

Abstract: 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} 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}. Using a constructive approach, we prove two combinatorial theorems of Tucker type. The theorems state 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 set {0,1} n +q for some integral vector q. These theorems are used to show in a constructive way the existence of an integral solution to a system of nonlinear equations under certain natural conditions. An economic application is provided.

Keywords: Sperner lemma; Tucker lemma; Integer labeling; Simplicial algorithms; Discrete nonlinear equations (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-009-9603-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joptap:v:144:y:2010:i:2:d:10.1007_s10957-009-9603-7

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-009-9603-7

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().