The set of polytopes with given $f$-vector

Question

Let $f=(f_0,\ldots f_n)$ be a vector in $\Bbb N^{n+1}$. Let $X$ be the set of all (ordered) $f_0$-tuples in $\Bbb R^n$ whose convex hull has $f$ as its $f$-vector. Assume that $X$ is non-empty. Is anything known about $X$? For instance, is it algebraic? Semi-algebraic?

Edit: By “is $X$ algebraic”, I mean: Is $X$ locally closed, or maybe just constructible, in the Zariski topology on $\Bbb R^{f_0 n}$?

Answer 1

It is semi-algebraic. Let $x$ be an $f_0$-tuple of points in $R^n$. Take any subset of $n$ points from $x$, and find a hyperplane through these points. This involves only rational operations on the coordinates. Select from these hyperplanes those for which all points in $x$ are on one side. This involves checking some inequalities. So we obtain equations of faces. Solving linear equations obtain intersections of faces, and check which of them are really the facets. All this involves only rational operations and checking inequalities between rational functions of $x$. Therefore the set is semi-algebraic.

It is not algebraic, as seen on the simplest example for $n=1$.

Answer 2

Hopefully this answer to my question is correct despite my minimal knowledge of semi-algebraic things.

$X$ is not in general algebraic: Consider the case of a square, i.e. $f=(4,4)$ (using the notation from my post, this should actually be $(4,4,1)$, but it seems that the number of $n$-dimensional faces of an n-dimensional polytope is usually left out since it’s always one). Then $X$ is exactly the set of 4-tuples $(x_1,\ldots,x_4)$ of points in $\Bbb R^2$ such that $x_4$ is not in the convex hull of $\{x_1,\ldots,x_3\}$. Suppose $X$ is algebraic, and fix $x_1,\ldots,x_3$. Then so is the set of all $x_4$ not in the convex hull of $\{x_1,\ldots,x_3\}$. But this set is $\Bbb R^2$ minus a (solid) triangle, and such a set is not algebraic.

$X$ is semi-algebraic: By the definition of “face”, $X$ is exactly the set of tuples $(x_1,\ldots,x_{f_0})$ of points in $\Bbb R^n$ satisfying the following (lines are numbered and indented for clarity):

1. For all $k\in\{0,\ldots,n-1\}$,
2. $\quad$there exist exactly $f_k$ subsets $I\subseteq \{1,\ldots, f_0\}$ such that
3. $\quad\quad$there exists an affine linear functional $g\colon \Bbb R^n\to \Bbb R$ such that
4. $\quad\quad\quad g(x_i)\geq0$ for all $i\in \{1,\ldots, f_0\}$
5. $\quad\quad\quad$and $g(x_i)=0$ for all $i\in I$.

Lines 3-5 describe a semi-algebraic set when $I$ and $k$ are fixed. Since there are only finitely many possible $I$ and $k$, we get that $X$ is indeed semi-algebraic.