Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 391-407 |
| Journal | Journal of Optimization Theory and Applications |
| Volume | 144 |
| Publication status | Published - 2010 |
Fingerprint
Cite this
}
Combinatorial integer labeling theorems on finite sets with applications. / van der Laan, G.; Talman, A.J.J.; Yang, Z.F.
In: Journal of Optimization Theory and Applications, Vol. 144, 2010, p. 391-407.Research output: Contribution to journal › Article › Scientific › peer-review
TY - JOUR
T1 - Combinatorial integer labeling theorems on finite sets with applications
AU - van der Laan, G.
AU - Talman, A.J.J.
AU - Yang, Z.F.
N1 - Appeared earlier as CentER DP 2007-88 (rt)
PY - 2010
Y1 - 2010
N2 - Tucker’s well-known combinatorial lemma states that, for any given symmetrictriangulation of the n-dimensional unit cube and for any integer labeling thatassigns 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.
AB - Tucker’s well-known combinatorial lemma states that, for any given symmetrictriangulation of the n-dimensional unit cube and for any integer labeling thatassigns 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.
M3 - Article
VL - 144
SP - 391
EP - 407
JO - Journal of Optimization Theory and Applications
JF - Journal of Optimization Theory and Applications
SN - 0022-3239
ER -