Combinatorial integer labeling theorems on finite sets with applications

G. van der Laan, A.J.J. Talman, Z.F. Yang

Research output: Contribution to journalArticleScientificpeer-review

223 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)391-407
JournalJournal of Optimization Theory and Applications
Volume144
Publication statusPublished - 2010

Fingerprint

Labeling
Labels
Finite Set
Triangulation
Integer
n-dimensional
Theorem
Integral Solution
Unit cube
System of Nonlinear Equations
Regular hexahedron
Assign
Euclidean space
Lemma
Economics
Nonlinear equations
Cell
Arbitrary
Vertex of a graph
Integral

Cite this

@article{ad8b5690751641b6b034761d0874b7ac,
title = "Combinatorial integer labeling theorems on finite sets with applications",
abstract = "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.",
author = "{van der Laan}, G. and A.J.J. Talman and Z.F. Yang",
note = "Appeared earlier as CentER DP 2007-88 (rt)",
year = "2010",
language = "English",
volume = "144",
pages = "391--407",
journal = "Journal of Optimization Theory and Applications",
issn = "0022-3239",
publisher = "SPRINGER/PLENUM PUBLISHERS",

}

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 journalArticleScientificpeer-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 -