Test Your Intuition (12): Perturbing a Polytope

Let P be a d-dimensional convex polytope. Can we always perturb the vertices of P moving them to points with rational coordinates without changing the combinatorial structure of P?

In order words, you require that a set of vertices whose convex hull is a k-dimensional face of P will have this property after the perturbation.

4 thoughts on “Test Your Intuition (12): Perturbing a Polytope

  1. mircea p

    Below I enumerate the times when I “use my intuition”, assuming things that I’m not sure of (please forget about this comment in case I’m misunderstanding the spirit of this “test your intuition” title!).
    0) In general, the only problem which arises for a generic perturbation is that it will break the faces of the polytope into triangles, because “linear dependence is not robust”.
    If we represent the polytopes in the space of configurations R^v (v is the (fixed) number of vertices) then
    1)I expect that a given combinatorial structure c becomes an algebraic variety V_c (possibly of positive codimension), and
    2) I imagine that requiring that the combinatorial structure agrees with the one arising from the faces of the convex hull selects a subset C_c in V_c in this which is the closure of its interior in V_c.
    3) I expect therefore that the problem is equivalent to asking if a variety of R^v has dense rational points, which
    4) I think is in general false.
    5) I immagine that the V_c’s arising like this have no special properties, which would save them from irrationality, so I guess the answer is “no”
    Other “intuitions” about which I would like to know whether they are true or not, even though they didn’t seem useful for the answer:

    6) In high enough codimension, this task of “rationalizing the polytope by perturbation” is possible (i.e. extra degrees of freedom do help).
    6′) A guess about the right codimension in the point above: maybe it is enough that P is embedded in R^v?

  2. Scott McKuen

    I have a feeling that I’m overlooking something basic here, but here goes: look at the polytope as a semilinear set. The combinatorial structure should be expressible by a first-order sentence using the vertices as parameters, but then the parameters can be replaced by existentially quantified variables. I think there is quantifier elimination in this situation, so you might be able to show completeness. In that case, the sentence would also be true of the rationals, showing that an appropriate set of vertices exists. So if it’s not true, I’d be interested to know which of these guesses is wrong.

  3. Antonio

    Assume this: I don’t read any post.
    You can pick a UNSAT formula and rewrite this formula with disequation. You can always put this polytope in a [0,1]^n space. The formula is unsat then the polytope doesn’t have any integer value point. if you move one of the vertices of the polytope in a integer ( then rational ) point then you make this formula SAT and then you change the “combinatorial property of the formula”. I don’t think about the convex property of the new polytope but i think this isn’t a real problem!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s