3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I guess that you know Kalai's algorithm for recognising graphs of simple polytopes. $\endgroup$ – Hao Chen Mar 8 '15 at 16:54
  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger Mar 8 '15 at 19:44
  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger Mar 8 '15 at 19:47
  • $\begingroup$ @TheMaskedAvenger: Much hinges on the phrase "simple polytope," as HaoChen points out. $\endgroup$ – Joseph O'Rourke Mar 8 '15 at 23:08
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yunhyung Cho Mar 9 '15 at 14:18
  • $\begingroup$ @YunhyungCho I just adjusted my answer to include extreme cases as simplex. $\endgroup$ – Hao Chen Mar 9 '15 at 14:29
  • $\begingroup$ @ 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. $\endgroup$ – Yunhyung Cho Mar 9 '15 at 14:52
  • $\begingroup$ @YunhyungCho I believe that "most" polytope can not be realized with such a plane. I don't have a characterization for those that can. $\endgroup$ – Hao Chen Mar 9 '15 at 14:56
  • $\begingroup$ Of course. I just want to have an example. Thank you so much! $\endgroup$ – Yunhyung Cho Mar 9 '15 at 15:42
1
$\begingroup$

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:


          TriIcosa
                  (Image from Wikipedia page.)
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ He said "simple convex polytope". I think "deformation" means any combinatorial equivalent realization. $\endgroup$ – Hao Chen Mar 8 '15 at 16:52
  • $\begingroup$ @HaoChen: Ah, I was interpreting "simple" as in "simple polyhedron," rather than "simple polytope": all vertices degree $d$. Thanks for the clarifications. $\endgroup$ – Joseph O'Rourke Mar 8 '15 at 17:25
  • $\begingroup$ @HaoChen: A deformation should be "preserving ... convexity," a stipulation I do not understand. $\endgroup$ – Joseph O'Rourke Mar 8 '15 at 23:09
  • $\begingroup$ For the geometric incognoscenti among us, are there brief descriptions which would convey an appropriate meaning of "simple" for this context? My guess is no holes. $\endgroup$ – The Masked Avenger Mar 8 '15 at 23:16
  • 2
    $\begingroup$ 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) $\endgroup$ – Hao Chen Mar 9 '15 at 6:28

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.