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

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

Research output: Working paperDiscussion paperOther research output

243 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 f§1;§2; ¢ ¢ ¢ ;§ng 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 f§1;§2; ¢ ¢ ¢ ;§ng. 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 set f0; 1gn+q for some integral vector q. 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.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages21
Volume2007-88
Publication statusPublished - 2007

Publication series

NameCentER Discussion Paper
Volume2007-88

Keywords

  • Sperner lemma
  • Tucker lemma
  • integer labeling
  • simplicial algorithm
  • discrete nonlinear equations

Fingerprint Dive into the research topics of 'Combinatorial Integer Labeling Thorems on Finite Sets with an Application to Discrete Systems of Nonlinear Equations'. Together they form a unique fingerprint.

  • Cite this

    van der Laan, G., Talman, A. J. J., & Yang, Z. F. (2007). Combinatorial Integer Labeling Thorems on Finite Sets with an Application to Discrete Systems of Nonlinear Equations. (CentER Discussion Paper; Vol. 2007-88). Operations research.