# Polytope with indegree-increasing property.

I have a question about a simple polytope. I am worried that my question would be inappropriate for mathoverflow. So I am sorry that I am ignorant of combinatorics.

Let $\mathcal{P}$ be a simple convex polytope of dimension $n$ embedded in $\mathbb{R}^n$. Then any vector $v \in \mathbb{R}$ defines a height function $h_v$ of $\mathcal{P}$ such that $$h_v(x) = \langle v, x \rangle$$ where $\langle \cdot, \cdot \rangle$ is the usual inner product in $\mathbb{R}^n$. Assume that $v$ is chosen not to be perpendicular to any face of $\mathcal{P}$. Then $h_v$ gives an orientation on each edge of $\mathcal{P}$ such that $$\overrightarrow{pq} \Leftrightarrow h_v(p) < h_v(q)$$ for every edge $\overline{pq}$ connecting $p$ and $q$. With this orientation, we can define an index $\mathrm{ind}(p)$ (or, indegree of $p$ as a digraph) as a number of edges which end at p. And we call $h_v$ is `index-increasing' if $$\mathrm{ind}(p) < \mathrm{ind}(q) ~\mathrm{ implies} ~h_v(p) < h_v(q)$$.

Allowing to deform $\mathcal{P}$ continuously (preserving combinatorial structure and convexity, but a normal fan can vary), is it always possible to find a deformation of $\mathcal{P}$ and a vector $v \in \mathbb{R}^n$ such that $h_v$ is index-increasing?

I would really appriciate if you could give me any comment. Thank you.

• I guess that you know Kalai's algorithm for recognising graphs of simple polytopes. – Hao Chen Mar 8 '15 at 16:54
• Let us decorate cylinders with square and triangular grids, so that there are points with (undirected) degrees of four and six respectively. We can chain these cylinders together to form a graph which, as we travel from one end of the cylinder to the other, gives us alternating sets of degree 4 and degree 6 vertices. I imagine a combinatorial polytope with such alternations as to foil any hope for an index increasing function, regardless of how the cylinder (or stack of prisms) is deformed. – The Masked Avenger Mar 8 '15 at 19:44
• Of course, Joseph O'Rourke makes the same point in a more picturesque way, but the cylinder model might be more amenable to a proof of impossibility. – The Masked Avenger Mar 8 '15 at 19:47
• @TheMaskedAvenger: Much hinges on the phrase "simple polytope," as HaoChen points out. – Joseph O'Rourke Mar 8 '15 at 23:08

This answer benefited from a discussion with I. Izmestiev.

Consider a $3$-dimensional simple polytope $P$. The indegrees of the vertices can only be $0$, $1$, $2$ or $3$. The lowest vertex has indegree $0$, the highest vertex has indegree $3$, and the other vertices have indegree $1$ or $2$. For an index-increasing realization of $P$, there is a plane that separates the indegree-$\le 1$ vertices and the indegree-$\ge 2$ vertices.

Moreover, every face of $P$ contains a vertex of indegree $\le 1$ (its lowest vertex) and a vertex of indegree $\ge 2$ (its highest vertex). Therefore, the existence of the required realization means that there must be a plane that cuts all the faces.

From this point of view, it becomes much clearer that index-increasing realization is very unlikely to exist even in dimension $3$. Counter-examples can be easily constructed, for example, by taking truncations.

• Nice approach! But how do you know that every face of $\mathcal{P}$ contains a vertex of indegree 1 and a vertex of indegree 2 ? For example, for 3-dimensional simplex case, every facet is a triangle so that there must be a facet which contains vertices of indegree 0,2 (or 4),and 6. – Yunhyung Cho Mar 9 '15 at 14:18
• @YunhyungCho I just adjusted my answer to include extreme cases as simplex. – Hao Chen Mar 9 '15 at 14:29
• @ Hao Chen : Yes. I definitely agree with you that there must exist such plane. I should keep trying to construct a counter-example, because we allow to deform a polytope even after taking several truncations. – Yunhyung Cho Mar 9 '15 at 14:52
• @YunhyungCho I believe that "most" polytope can not be realized with such a plane. I don't have a characterization for those that can. – Hao Chen Mar 9 '15 at 14:56
• Of course. I just want to have an example. Thank you so much! – Yunhyung Cho Mar 9 '15 at 15:42

This is not an answer, but rather a request for clarification with an image. It seems to me much depends on what you mean by "a deformation of $\mathcal{P}$." You want to reorient and deform $\cal P$ so that the indegree increases monotonically with height. An example that might be problematical is a polytope with a mixture of high- and low-degree vertices, uniformly distributed around the surface. An example in $\mathbb{R}^3$ is the triakis icosahedron, which has 20 degree-3 vertices and 12 degree-10 vertices. It is convex, but its structure is more easily understood in this nonconvex version:

Perhaps you could clarify by describing a deformation and a $v$ that makes $h_v$ index-increasing for the convex version of the triakis icosahedron.
• @HaoChen: Ah, I was interpreting "simple" as in "simple polyhedron," rather than "simple polytope": all vertices degree $d$. Thanks for the clarifications. – Joseph O'Rourke Mar 8 '15 at 17:25
• I would rephrase the question as follows: can we always find a convex polytope $P'$ such that $P'$ is combinatorially equivalent to $P$ and $P'$ is index increasing w.r.t. a given vector (after all, we can fix the vector wlog) – Hao Chen Mar 9 '15 at 6:28