9
$\begingroup$

Suppose I give a list of vertices $(v_1, v_2, ..., v_n)$, and a list of "adjacencies", i.e. pairs of vertices $(v_i,v_j)$. Does it exists a unique polytope that has this vertices and realises the adjacencies with 1-dimensional faces? I do not know if that is important, but each and every vertex has exactly d adjacent vertices, and I'd expect the polytope to be simple.

I should add some information. The data I gave above is represented by a graph of which I know 1) it's connected 2) every vertex has the same valence d. I may come up with further constraints but these are the first I can think of.

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
13
$\begingroup$

I don't know conditions of existence ($d$-connectivity is necessary), but the uniqueness was proved by Blind and Mani in 1987, see also the 1988 article "A simple way to tell a simple polytope from its graph" by Gil Kalai. Kalai's proof is also presented in Guenter Ziegler's book "Lectures on polytopes".

The simplicity assumption is important: for $d \ge 4$ there are different combinatorial classes of $1$-neighborly polytopes (polytopes whose $1$-skeleton is a complete graph).

Improve this answer
$\endgroup$
6
$\begingroup$

In fact, elaborating on Guillermo Pineda-Villavicencio's answer, Jürgen Richter-Gebert's universality theorem for 4-polytopes shows that even in four dimensions, deciding whether a graph is realized by the vertices and edges of a simple polytope is equivalent to the existential theory of the reals.

I am fairly sure that the proof of this theorem can be extended to graphs of degree 4, so for an arbitrary semi-algebraic set defined by inequalities, you can in polynomial time find a graph so that the polytope is realizable if and only if this set is non-empty (although you should check this before you cite it in a paper).

See Realization spaces of 4-polytopes are universal by Richter-Gebert and Ziegler, although I suspect this theorem might have a better exposition in Richter-Gebert's monograph Realization Spaces of Polytopes.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Are these statements constructive? So if a graph in d>=4 is the 1-skeleton of a polytope, there is a machinery to realise it in a vector space using planes? $\endgroup$
    – giulio bullsaver
    Commented Jun 15, 2018 at 14:19
  • $\begingroup$ @Giulio: Yes. If you have a graph in $d \geq 4$, it is fairly straightforward to turn it into a semi-algebraic set that is non-empty if and only if the graph is realizable as a polytope over $\mathbb{R}^d$. If you have a semi-algebraic set and a dimension $d \geq 4$, then there is a constructive method to turn it into a graph that is realizable as a polytope over $\mathbb{R^d}$ if and only if the semi-algebraic set is non-empty. $\endgroup$
    – Peter Shor
    Commented Jun 15, 2018 at 14:54
  • $\begingroup$ So determining whether polytopes are realizable is exactly as hard as determining whether semi-algebraic sets are non-empty. (For graphs of degree $d$, semi-algebraic sets defined by inequalities.) This problem is in PSPACE (this fact is neither obvious nor easy), so there is machinery that is constructive but takes exponential time in the size of the graph. $\endgroup$
    – Peter Shor
    Commented Jun 15, 2018 at 14:55
  • $\begingroup$ This might prove very useful for me, thanks! There is any reference to look up for this algorithm? $\endgroup$
    – giulio bullsaver
    Commented Jun 15, 2018 at 15:30
  • 1
    $\begingroup$ First, use Kalai's algorithm to find which vertices must belong to which facets (an exponential algorithm is sketched in Kalai's paper). Express each facet in terms of unknown variables. Then write down equations saying (1) all vertices of the graph are on the inside of each facet and (2) all vertices that belong to a facet are on that facet. If there is a solution to these equations, then you have an embedding. Finding the solutions to these equations is possible thinks to the existential theory of the reals being computable. $\endgroup$
    – Peter Shor
    Commented Jun 15, 2018 at 20:24
4
$\begingroup$

Ivan Izmestiev's answer, and Blind and Mani's and Kalai's results, applies if you know beforehand that the graph is the graph of a d-dimensional polytope. There are many regular graphs, in the graph theoretical sense, that are not graphs of polytopes. See, for instance, the paper "Polytopality and cartesian products of graphs" by Pfeifle et al.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .