Advanced Search
MyIDEAS: Login to save this paper or follow this series

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

Contents:

Author Info

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

    (Tilburg University, Center for Economic Research)

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.

Download Info

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
File URL: http://arno.uvt.nl/show.cgi?fid=65836
Our checks indicate that this address may not be valid because: 404 Not Found. If this is indeed the case, please notify (Richard Broekman)
Download Restriction: no

Bibliographic Info

Paper provided by Tilburg University, Center for Economic Research in its series Discussion Paper with number 2007-88.

as in new window
Length:
Date of creation: 2007
Date of revision:
Handle: RePEc:dgr:kubcen:200788

Contact details of provider:
Web page: http://center.uvt.nl

Related research

Keywords: Sperner lemma; Tucker lemma; integer labeling; simplicial algorithm; discrete nonlinear equations;

Other versions of this item:

Find related papers by JEL classification:

This paper has been announced in the following NEP Reports:

References

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
as in new window
  1. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
  2. Gerard van der Laan & Dolf Talman & Zaifu Yang, 2004. "Solving Discrete Zero Point Problems," Tinbergen Institute Discussion Papers 04-112/1, Tinbergen Institute.
  3. Laan, G. van der & Talman, A.J.J. & Yang, Z.F., 2007. "Computing integral solutions of complementarity problems," Open Access publications from Tilburg University urn:nbn:nl:ui:12-327117, Tilburg University.
  4. Herbert E. Scarf, 1994. "The Allocation of Resources in the Presence of Indivisibilities," Cowles Foundation Discussion Papers 1068, Cowles Foundation for Research in Economics, Yale University.
  5. Zhou Lin, 1994. "The Set of Nash Equilibria of a Supermodular Game Is a Complete Lattice," Games and Economic Behavior, Elsevier, vol. 7(2), pages 295-300, September.
  6. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
  7. Ning Sun & Zaifu Yang, 2006. "Equilibria and Indivisibilities: Gross Substitutes and Complements," Econometrica, Econometric Society, vol. 74(5), pages 1385-1402, 09.
  8. Talman, A.J.J. & Laan, G. van der, 1979. "A restart algorithm for computing fixed points without an extra dimension," Open Access publications from Tilburg University urn:nbn:nl:ui:12-153012, Tilburg University.
  9. Eaves, C. & Laan, G. van der & Talman, A.J.J. & Yang, Z.F., 1996. "Balanced Simplices on Polytopes," Discussion Paper 1996-25, Tilburg University, Center for Economic Research.
  10. Laan, G. van der & Talman, A.J.J. & Yang, Z.F., 2001. "Existence of balanced simplices on polytopes," Open Access publications from Tilburg University urn:nbn:nl:ui:12-87578, Tilburg University.
  11. Iimura, Takuya, 2003. "A discrete fixed point theorem and its applications," Journal of Mathematical Economics, Elsevier, vol. 39(7), pages 725-742, September.
  12. Iimura, Takuya & Murota, Kazuo & Tamura, Akihisa, 2005. "Discrete fixed point theorem reconsidered," Journal of Mathematical Economics, Elsevier, vol. 41(8), pages 1030-1036, December.
  13. Laan, G. van der & Talman, A.J.J. & Yang, Z.F., 2007. "A vector labeling method for solving discrete zero point and complementarity problems," Open Access publications from Tilburg University urn:nbn:nl:ui:12-284192, Tilburg University.
  14. Talman, A.J.J. & Laan , G. van der, 1982. "On the computation of fixed points on the product space of unit simplices and an application to noncooperative N-person games," Open Access publications from Tilburg University urn:nbn:nl:ui:12-153028, Tilburg University.
  15. Herbert E. Scarf, 1967. "The Approximation of Fixed Points of a Continuous Mapping," Cowles Foundation Discussion Papers 216R, Cowles Foundation for Research in Economics, Yale University.
  16. Francis Su, . "Rental Harmony: Sperner's Lemma in Fair Division," Claremont Colleges Working Papers 1999-10, Claremont Colleges.
Full references (including those not matched with items on IDEAS)

Citations

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:dgr:kubcen:200788. See general information about how to correct material in RePEc.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Richard Broekman).

If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

If references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

Please note that corrections may take a couple of weeks to filter through the various RePEc services.