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.

PY - 2010

Y1 - 2010

N2 - 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}

AB - 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}

U2 - 10.1007/s10957-009-9603-7

DO - 10.1007/s10957-009-9603-7

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 -