Skip to main content
SpringerLink
Log in

The topological structure of maximal lattice free convex bodies: The general case

  • Published:
Mathematical Programming Submit manuscript

Abstract

Given a genericm × n matrixA, the simplicial complexK(A) is defined to be the collection of simplices representing maximal lattice point free convex bodies of the form {x : Ax ⩽ b}. The main result of this paper is that the topological space associated withK(A) is homeomorphic withR m−1. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I. Bárány, R. Howe and H.E. Scarf, The complex of maximal lattice-free simplices,Mathematical Programming 66 (1994) 273–282.

    Google Scholar 

  2. D.E. Bell, A theorem concerning the integer lattice,Studies in Applied Mathematics 56 (1977) 187–188.

    Google Scholar 

  3. J.-P. Doignon, Convexity in Cristallographic lattices,Journal of Geometry 3 (1973) 77–85.

    Google Scholar 

  4. R. Kannan, L. Lovász and H.E. Scarf, The shapes of polyhedra,Mathematics of Operations Research 15 (1990) 364–380.

    Google Scholar 

  5. L. Lovász, Geometry of numbers and integer programming, in: M. Iri and K. Tanabe, eds.,Mathematical Programming: Recent Developments and Applications (Kluwer, Norwell, MA, 1989) 177–210.

    Google Scholar 

  6. H.E. Scarf, An observation on the structure of production sets with indivisibilities,Proceedings of the National Academy of Sciences USA 74 (1977) 3637–3641.

    Google Scholar 

  7. H.E. Scarf, Production sets with indivisibilities. Part I. Generalities,Econometrica 49 (1981) 1–32.

    Google Scholar 

  8. H.E. Scarf, Production sets with indivisibilities. Part II. The case of two activities,Econometrica 49 (1981) 395–423.

    Google Scholar 

  9. P. White, Discrete activity analysis, Ph.D. Thesis, Yale University, Department of Economics, 1983.

Download references

Author information

Authors and Affiliations

  1. Mathematical Institute, P.O. Box 127, 1364, Budapest, Hungary

    I. Bárány

  2. Cowles Foundation for Research in Economics, Yale University, 06520-8281, New Haven, CT, USA

    H. E. Scarf

  3. Bellcore, 445 South Street, 07962, Morristown, NJ, USA

    D. Shallcross

Authors
  1. I. Bárány
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. E. Scarf
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. D. Shallcross
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by NSF grant SES-9121936 and the program in Discrete Mathematics at Yale University.

Partially supported by the Hungarian NSF grant 1909 and the program in Discrete Mathematics at Yale University.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bárány, I., Scarf, H.E. & Shallcross, D. The topological structure of maximal lattice free convex bodies: The general case. Mathematical Programming 80, 1–15 (1998). https://doi.org/10.1007/BF01582128

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01582128

Keywords

Search

Navigation