# Number of lattice polytopes contained in a given lattice polytope?

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?

• 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. Apr 2, 2014 at 14:05
• 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. Apr 2, 2014 at 18:18
• 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$. Apr 3, 2014 at 1:41

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.