3
$\begingroup$

Given a (convex) lattice polytope, suppose we want to list or count all (convex) lattice polytopes (of the same dimension) contained in it. Are there efficient ways to do this?

$\endgroup$
3
  • $\begingroup$ Define efficient. If you start with a simplex of $n$ vertices, then you would have $2^n-1$ subsets of the vertices, that all span different simplices. So listing them will be exponential. $\endgroup$ Apr 2, 2014 at 14:05
  • $\begingroup$ This is not exactly what I meant, I am interested in polytopes that are of the same dimension as the containing polytope, so facets do not count. As for efficiency, I meant more in the sense of an algorithm that doesn't just go over all possible subsets of lattice points in the given polytope, and then discards duplicates. This is for the list. For the number of such polytopes, it would be interesting to give some bound on the number of contained polytopes. $\endgroup$
    – wishcow
    Apr 2, 2014 at 18:18
  • $\begingroup$ It's easy to modify Per Alexandersson's suggestion so that the polytopes are the same dimension. If there are $n$ vertices of a convex hull, and some tetrahedron $T$ contained in the interior, then a subset of the vertices $S$ is determined by the convex hull of $S\cup T$, so there are at least $2^n$. $\endgroup$ Apr 3, 2014 at 1:41

1 Answer 1

2
$\begingroup$

An observation, and a remark.

For a polytope $P = \mathrm{conv} V$ with vertices $V$, let $S \subset V$ be an independent set of vertices, i.e., independent in the 1-skeleton graph of $P$. Then, if $|S|=k$, one can form $2^k-1$ internal lattice polytopes by removing (or not) each vertex of $S$ from $V$ and finding the convex hull of the remaining vertices of $V$ and the enclosed lattice points. For example, below $\{ v_1, v_2 \}$ forms an independent set.


          PolytopeCounting
It seems that it should be possible to enumerate all contained lattice polytopes by systematically peeling away the boundary vertices in this fashion. However, I am not seeing at the moment how to do this in a way that counts each enclosed polytope exactly once each.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.