Jason (jcreed) wrote,
Jason
jcreed

Quick and somewhat naïve question to any of you out there who know things about polytopes:

Is there a known simple criterion for whether a given lattice is the face lattice of some polytope?

Ideally a criterion that is subjectively "finite"-feeling, something combinatorial rather than about convex subsets of huge infinite things like Rn.

---

Hmm this paper (mentioned at mathoverflow under a similar question) suggests that it is NP-hard to answer this question already with 4-dimensional polytopes. I was kind of hoping it would be decidable at least, but I'm not sure if that question is open or not. In other words, I don't know whether the mathematical community at large knows how to reliably know whether a given lattice is a face lattice. That's three knowings! That's a lot, unless perhaps you're a complexity theorist, in which case you have to deal with this kind of nonsense all the time.
Tags: math, polytopes
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 13 comments