Polymath3 (PHC6): The Polynomial Hirsch Conjecture – A Topological Approach

This is a new polymath3 research thread. Our aim is to tackle the polynomial Hirsch conjecture which asserts that there is a polynomial upper bound for the diameter of graphs of d-dimensional polytopes with n facets. Our research so far was devoted to an abstract combinatorial setting. We studied an appealing conjecture by Nicolai Hahnle and considered an even more general abstraction proposed by Yury Volvovskiy. Comments towards this abstract conjecture are most welcome!

Here, I would like to mention a topological approach which follows a result that was discovered independently by Tamon Stephen and Hugh Thomas in their paper An Euler characteristic proof that 4-prismatoids have width at most 4,
and by Paco Santos in his paper Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids. This post is based on a discussion with Paco Santos at Oberwolfach.

Two maps on a two dimensional Sphere

Theorem: Given a red map and a blue map drawn in general position on S^2 there is an intersection point of two edges of different colors which is adjacent (in the refined map) to a red vertex and to a blue vertex.

Blue and black maps

There are two proofs for the theorem. The proof by Stephen and Thomas uses an Euler characteristic argument. The proof by Santos applies a connectivity argument. Both papers are short and elegant. Both papers point out that the result does not hold for maps on a torus.

Santos’ counterexample to the Hirsch conjecture is based on showing that a direct extension of this result to maps in three dimensions fails. (Even for two maps coming from fans based on polytopes.) Of course, first Paco found his counterexample and then the two-map theorem was found in response to his question  of whether one can find in dimension four counterexamples of the kind he presented in dimension five.

The theorem by Santos, Stephen, and Thomas is very elegant. The proofs are simple but far from obvious and it seems to me that the result will find interesting applications. Its elegance and depth reminded me of Anton Klyachko’s car crash theorem.

A topological question in high dimensions

Now we are ready to present a higher-dimensional analog:

Tentative Conjecture: Let M_1 be a red map and let  M_2 be a blue map drawn in general position on S^{n}, and let $M$ be their common refinement.  There is a vertex w of M a blue vertex v \in M_1, a red vertex u \in M_2 and two faces F,~G \in M such that 1) v,w \in F, 2) w,u \in G, and 3) \dim F + \dim G =n.

A simple (but perhaps not the most general) setting in which to ask this question is with regard to the red and blue maps  coming from red and blue polyhedral fans associated to red and blue convex polytopes. The common refinement will be the fan obtained by taking all intersections of cones, one from the first fan and one from the second.

(Perhaps when n=2k we can even guarantee that \dim F=\dim G=k.)

Why the tentative conjecture implies that the diameter is polynomial

An affirmative answer to this conjecture will lead to a bound of the form dn for the graph of d-polytopes with n facets.

Here is why:

- It is known that the diameter of every polytope with n facets and dimension d is bounded above by the “length” of a Dantzig figure with 2n-2d facets and n-d vertices.

Here a Dantzig figure is a simple polytope of dimension D with 2D facets and two complementary vertices. (i.e., two vertices such that each vertex lies in half of the facets, and they do not belong to any common facet).

The length of the Dantzig figure is the graph distance between these two vertices. This is the classical “d-step theorem” of Klee and Walkup, 1967.

- The length of a Dantzig figure of dimension d is the same as the minimum distance between blue and red vertices in a pair of two maps in the (d-2)-sphere, with d cells each.

- Our tentative conjecture implies, by dimension on d, that the minimum distance between blue and red vertices in a pair of maps in the d-sphere and with n cells is bounded above by (essentially) nd. (n cells means “cells of the blue map plus cells of the red map”, not “cells of the common refinement”).

The abstract setting and other approaches

More comments, ideas, and updates on the abstract setting are of course very welcome Also very welcome are other approaches to the polynomial Hirsch conjecture, and discussion of related problems.

An example showing that the theorem fail for blue and red maps on a torus.

About these ads
This entry was posted in Convex polytopes, Geometry, Polymath3 and tagged , , . Bookmark the permalink.

37 Responses to Polymath3 (PHC6): The Polynomial Hirsch Conjecture – A Topological Approach

  1. In the statement of the theorem should it read “black” instead of “red?”

  2. Pingback: Polymath3 « Euclidean Ramsey Theory

  3. Daniel Moskovich says:

    This looks like a fun approach- the proofs are indeed elegant, and it makes sense to ask which constraints the tentative conjecture (or its negation) puts of the chain complex of M.

  4. Paco Santos says:

    I am glad you like this approach. Let me first put an update: the “Santos” proof and the “Stephen-Thomas” proof of the 2-dimensional case are now part of a single paper (http://front.math.ucdavis.edu/1104.2630).

    That said, let me add that besides the specific question asked by Gil, one can think about the general question of: given two maps (a blue map and a red map) drawn in a d-sphere, how big can the minimum distance between a blue and a red vertex, along the graph of the common refinement, be.

    If the two maps are sufficiently generic (which is no loss of generality) then every vertex of the common refinement is the intersection of an i-dimensional red face and a (d-i)-dimensional blue face. I say that such a vertex has “bidimension” (i,d-i). Every edge of the common refinement joins an (i,d-i) vertex with a (j,d-j) vertex for $j\in\{i-1,i,i+1\}$. The Hirsch conjecture would have been equivalent to the conjecture that you can always go from a (0,d) vertex to a (d,0) vertex monotonically, in just d steps. This is what we prove for d=2 and what I disproved for d=3.

    I have to say that every time I start (re)-thinking about the problem in this terms my first impression is that it is easy to proof that you can always go from a red vertex to a blue vertex in at most nd steps (which would imply the polynomial Hirsch conjecture, and actually match the “Hähnle bound”). Then it takes me a couple of days to realize/remember where the flaw in my argument is…

  5. Paco Santos says:

    A false proof:

    Let me try to revive this thread by being more explicit on my sentence “every time I start (re)-thinking about the problem in these terms my first impression is that it is easy to proof that you can always go from a red vertex to a blue vertex in at most nd steps”.

    As I said in my previous post, we want to go from a vertex of bidimension (0,d) to one of bidimension (d,0), and the edges in our graph connect each vertex of bidimension (i,j) with one of either (i+1,j), (i,j), or (i-1,j).

    With this in mind:

    proof: by induction on d. Consider any red d-cell that has a blue vertex (that is, a (0,d)-vertex in its interior. This implies the d-cell has some (1,d-1)-vertex in its boundary. The boundary of this red d-cell is itself decomposed by the red and the blue maps into a pair of maps in a (d-1)-sphere, and with at most n cells (actually, we can say at most n-1: the facets of the red d-cell are at most one less than the original number of red d-cells). By inductive hypothesis, in this (d-1)-dimensional map we can go from a red vertex to a blue vertex (that is, from a (0,d)-vertex to a (d-1,1)-vertex) in at most n(d-1) steps. Once we are in the (d-1,1)-vertex, which is the intersection of a red (d-1)-face and a blue edge, follow the blue edge. You may cross other red (d-1)-faces but, in at most n steps, (rather, in at most the number of red d-faces) you must get to a blue vertex. Done.

    Exercise 1: Find the mistake in this reasoning.

    Exercise 2: Correct the mistake in this reasoning. (This one looks harder to me, but you never know…).

    • Gil Kalai says:

      Many thanks, Paco!
      Now, what is the mistake?

    • Paco Santos says:

      The offending sentence is “The boundary of this red d-cell is itself decomposed by the red and the blue maps into a pair of maps in a (d-1)-sphere”, which is only partially true.

      Suppose, for example, that the red d-cell is “sliced” by several (d-1)-blue cells that do not meet each other (or meet outside the red cell). Then the blue d-cells restricted to (that is, intersected with) the boundary of the red d-cell are not even contractible. The blue map restricted to the boundary of the red d-cell, is not what you would normally call a map. This poses problems to the inductive hypothesis. For example, in this “pseudo-map” it is not true that a blue “edge” ends in a blue vertex. Blue edges may well be cycles…

  6. Uri Leder says:

    Let me try the ordinary approach, since it is the last post concerning polynomial Hirsch conjecture.

    Instead of Connected layer families of multisets let’s take connected layer families of numbers of length d in base n. That means the order in the multiset does matter. The connectivity is now according to the digit in regard of it’s place. If we have a number with “4” in the leftmost position in two layers there must be some number with “4” in the leftmost position in each layer between those two.

    The lemma of removal of a digit will be according to it’s place and should work the same. We will concat the two parts of the number after removal of digit to keep the order inside the number.

    Now let’s see what happenning if n=2. Binary vectors.

    WLOG suppose there is only one number in the first layer. There are two options for the second layer.
    1. If it has one number then since the number is different then the number of the first layer, there should be one place where a digit changes from 0 to 1 or from 1 to 0. So in all layers and in all numbers below second layer this digit must remain constant because of connectivity, and so we can use “removal lemma”.
    2. There are two or more numbers in layer two, then since those number are different there is a place where one of the numbers has 0 and the other one has 1. In the last layer there is at least one number. This number has either 1 or 0 in the same place, so we can perform the “removal lemma” in this case also.

    If we denote by D(2,d) the maximal length of the binary family with numbers of length d we would get :
    D(2,d)= 1+D(2,d-1) = d.

    Now let’s move to all numbers not just binary. We will replace the ordinary number in the following way. I’ll give an example : suppose n=4 d=6 then the number 123444 will turn to
    0001 0010 0100 1000 1000 1000. I claim that a connected family of numbers will be converted in this way to a connected family of binary numbers of length n*d. So D(n,d) = n*d

    At last for the multisets. Suppose we have a CLF of multisets, we will add to each layer all the permutations of all the d-multisets it contains. I claim that in this way the CLF of multisets will be coverted to a CLF of numbers and so we are done.

    I’m pretty sure I have a mistake somewhere, I already did tons of them before I came to that last version …

    • Uri Leder says:

      I have a bug in number converting. In base 4 there should be numbers 0, 1, 2, 3 , so it is 012333 that will become 0001 0010 0100 1000 1000 1000.

    • Paco Santos says:

      Dear Uri, I like your idea of considering ordered sequences rather then multisets (it seems to be the only new idea in quite some time). But I am afraid there is one part of the argument I don’t see. To clarify things, if I understand correctly you are making the following three claims:

      1) D(2,d) = d
      2) D(n,d) \le D(2, nd)
      3) f^*(n,d) \le D(n,d)

      Part (1) is clear to me (except in the notation of previous threads you are missing a +1; you seem to think of the length of a connected layer family as “number of layers minus 1″ rather than “number of layers”. That is also my preferred convention, actually). Part (3) seems OK as well.

      But your argument for part (2) fails in very simple cases such as n=3, d=1. Consider the sequence 1, 2, 3, which transforms to 001, 010, 100. The second digit goes from 0 to 1 and then back to 0. Or am I missing something?

      • Uri Leder says:

        I see what you mean now. I need to think about it, I’m just writing out of an inconvinient place.
        Sorry and thank you very much.

      • Uri Leder says:

        Can you think of an example that a digit will change twice ?

      • Uri Leder says:

        A bug, I mean more then twice …

      • Paco Santos says:

        Yes and no. The following will be true for the layer family of “dimension” nd obtained from a connected layer family of dimension d on n symbols: Each of the nd digits will have “connected support”, where the support is the set of layers containing a binary number with that digit set to 1. But this allows for the following to happen to a digit:
        {0}
        {1}
        {0} {1}
        {1}
        {0} {1}
        {1}
        {0}

        In fact, this is the restriction to the last digit of what you get from the following sequence with $d=1$ and $n=5$:
        {2}
        {1}
        {3} {1}
        {1}
        {4} {1}
        {1}
        {5}

  7. Uri Leder says:

    the 1,2,3 is the same number. I’ll give more accurate example :
    n=9 d=3
    Each layer contains 4 numbers which I put in {} as sets, but they are numbers

    {123} {234} {456} {001}
    {145} {378} {675} {124}

    Those two layers become:

    {000000010 000000100 000001000} {000000100 000001000 000010000} {000010000 000100000 001000000} {000000001 000000001 000000010}

    {000000010 0000010000 000100000} {000001000, 010000000 100000000} {0001000000 0010000000 000100000} {000000010 000000100 0000010000}
    The numbers are presented as “one hot binary vectors with 1 at the place of the digit within the binary vector of length n. then those binary vectores are concatinated in the order of the original number.

    • Paco Santos says:

      In my example 1,2,3 means three layers with one element each, of length one each. That is:
      {1}
      {2}
      {3}
      Do I understand correctly that in step 2 this translates to
      {001}
      {010}
      {100}
      which is not “connected” since the middle digit changes twice? (I am making the same “mistake” of thinking of “base 3″ as having 1 2 and 3 as digits rather than 0 1 and 2. This is partially intentional, since 1, 2, and 3 are mere symbols in your framework).

      • Uri Leder says:

        You are right there is a problem I answered you above.

      • Uri Leder says:

        Sorry for leaving replies not in the right place. I just don’t see the option to do it in the right place.
        By the way, let me introduce myself: I’m a student of Gil Kalai. And I’m also a full time job electrical engineer. I’m doing formal verification in a semiconductor company, a lot of SAT solvers and stuff. This is the reasons of my sporadic answers today and the reason of binary thinking.

        Concerning the example above There is the same number {1} used several times, I think it is not allowed, or maybe I misunderstand something ?

        I can summarize the problem in part 2 in the following way : when I perform the conversion, the digit “1” remains connected, but the connectivity of “0” is not assured.

        So maybe the first part can be changed to work with CLF with the weaker connection property. We can strengthen it by other property, that the number of ones in each binary number will be constantly d… Anyway either part 1 or part 2 must be changed.

        Thanks again for finding my mistake.

      • Uri Leder says:

        Another thought. Actually while converting , I used a tiny fraction of available binary numbers. Maybe by adding more to a layer will fix the connectivity. For example in the above we can add {000} in the middle layer. I can’t think however of a general rule that will fix every example.

      • Paco Santos says:

        Q: Concerning the example above There is the same number {1} used several times, I think it is not allowed, or maybe I misunderstand something ?

        A: You are right that is not allowed. But the example can be the restriction to a digit (in base 5) of something more complicated…

        Q: Actually while converting , I used a tiny fraction of available binary numbers. Maybe by adding more to a layer will fix the connectivity.

        A: When I first spotted the error in your argument I thought it could perhaps be fixed by encoding 1, 2, 3, 4 in binary as 0001, 0011, 0111, 1111 and making some assumption on the labeling of a digit (I mean, wlog assume that in every digit the symbols 1 to n appear in order, 1 being there since the first layer, etc). I could not make this work but it might be worth giving it a try.

      • Uri Leder says:

        Thank you for your answers. I’ll try to do both.

        1. I’ll run SAT solvers to give me some long examples of “half connected” CLFs of binary numbers.
        2.I’ll try to fix the converion, or maybe to see somehow that it is impossible. I thought to add all inverses to a layer, but it may lead to an unfixable problem. For example :

        {001} {110}
        {010}{101}
        {100}{011}

        cannot be fixed since we have no numbers left to fix the problem of {1 X 0} in the middle.

      • Uri Leder says:

        Ok, I tried the SAT solver on d=5. It can’t create more then 12 layers. Though it gave me some bizarre examples with 12 layers, my guess is that this one is best possible :

        {000001}
        {000011}
        {000111}
        {001111}
        {011111}
        {111111}
        {111110}
        {111100}
        {111000}
        {110000}
        {100000}
        {000000}

        Did we return to the original problem ?

    • Uri Leder says:

      Ok, they are not exactly the same, in the first problem we suspect that the example, where the families are singletons representing the best possible families.

      Here after trying some more SAT solvers, I received an example of 14 layers.
      (And there is no prove by the machine, that there are no bigger examples)
      It can’t be reached with layers of singletons, those are really bounded by 2d. (If I didn’t make another stupid mistake here is the proof).

      The proof : each “1” at each place has to “start” and to “end” as we “move” from the first layer to the last. There are at most 2d such transitions, and there must be a transition between each two layers, because they are disjoint, but there is only one number {000000}, so one transition cannot be made (“1″ at one place will begin but not end, or the opposite) so there are at most 2d layers in family made of singletons. (By the way the same proof is working for families of singletons made of multisets).

      • Paco Santos says:

        Yes, I believe the proof for singletons. Can you post the non-singleton example with length 14? Concerning “OK, they are not exactly the same”:

        You have introduced two different questions:

        a) what is the maximum length of connected layer families in the ordered case? (Your function D(n,d))

        b) what is the maximum length of layer families where each layer consists of binary numbers of the same length, with no repeated numbers in different layers, and with the restriction to any subset of digits being “semi-connected”: the layers containing a number with 1’s in all those digits form an interval, but no restriction is posed on the 0’s.

        Your original argument shows that upper bounds for (b) give upper bounds for (a) which give upper bounds for Nikolai’s original setting, and your example of length 14 shows that (b) is not the same as Nikolai’s original question. But whether (a) is equivalent to Nikolai’s is still open I would say.

        One thing I have been trying with no success is to prove the Kalai-Kleitman or the Barnette-Larman bounds in the (a) context.

  8. Uri Leder says:

    Concerning b), the example shows that it is not $nd$, but still, if it is polynomial, it would give polynomial upper bound for Nikolai’s question. I must admit, I didn’t do anything with a) yet.

    I have two results now for b), (Since those are machine examples they are ugly) .
    1) I have a machine prove that for $d=4$ the upper bound is 9 :
    {0000}
    {0100}
    {0101}
    {0110}{1100}{0010}{0111}{1001}
    {0011}{1111}{0001}{1011}
    {1110}
    {1010}
    {1000}

    2) I have an example of 15 layers for $d=6$

    {001000}
    {011000}
    {011100}
    {011101}
    {111101}
    {111100}{001101}{110101}{111001}
    {110111}{101001}{011001}{111110}{001111}
    {101101}{110110}{011111}{111011}
    {111111}
    {101111}
    {100111}
    {100101}
    {100100}
    {100000}
    {000000}

    Both examples are based on the same logic. The number of ones is growing towards the middle from both ends and then the middle can be expanded, but not that much… The computer is stuck for several hours trying to find an example for 16 layers. And I didn’t have the time to take a closer look at the examples yet.

    • Uri Leder says:

      Sorry there is a bug in first example the layer 4 is missing. It is : {1101}.

    • Paco Santos says:

      Uri, the way I understand (b), your examples are not valid. I would ask for “half-connectedness” not only on individual digits but also on subsets of them. For example, the one with d=6 would not be connected because layers 5 and 8 include digits of the form 1111*1 while layers 6 and 7 do not.

      • Uri Leder says:

        You are right. It seems that I should have to examine the examples better before I posted them. It seems that I have a “bug” in the programm. I’ll fix it right away, since af course I ask for “half-connectedness” of subsets.

      • Uri Leder says:

        After the fix the best examples for both $d=4$ and $d=6$ are of length $2d$, meanwhile…
        As expected.

      • Paco Santos says:

        In fact, now that I think of it, what I call (b) is completely equivalent to the original “connected layer families” of Eisenbrand et al, that is, without taking the order into account and without allowing for repeated elements in the sets. Indeed, a binary digit of length $d$ is just an encoding of a subset of $[d]$, and the “half-connectedness” we have been discussing is equivalent to the original connectedness property.

      • Uri Leder says:

        You are right about the “half-connectedness”, I was thinking of it also. Actually, when I converted the original problem to binary version for SAT solver, this is what I did. On the other hand (If I understood correctly what you mean), many digits are needed to encode all the subset. In the original setting in order to encode all the subsets n+(n choose 2)+(n choose 3)+ .. + (n choose d) digits are needed. So even if the upper bound for binary numbers would be polynomial, I think if the encoding is done that way, it would not tell us that the original CLF has polynomial upper bound.

  9. Paco Santos says:

    In reply to “On the other hand (If I understood correctly what you mean), many digits are needed to encode all the subset. In the original setting in order to encode all the subsets n+(n choose 2)+(n choose 3)+ .. + (n choose d) digits are needed.”

    No, I do not mean this, I think. Let me start from scratch.

    Following the notation of previous threads and the wiki, let me call f(n) the maximum length of connected layer families without repetition and with no restriction on the size of the sets in the families, and f(d,n) the same but restricted to all subsets having size d. There is also \tilde f(d,n) in which multisets, rather than sets are considered. Most of the discussions in the project are about Haehnle’s beautiful conjecture:

    Conjecture: \tilde f(d,n) =(n-1)d

    (Remark: I am taking the convention that the length of a layer family is the “number of layers minus one”. On the one hand this gives nicer formulas and in the other it agrees better with the Hirsch context, in which the length of a path is “number of vertices minus one”).

    You introduced an “ordered version”, in which the sets of size d are no longer multisets but rather vectors in [n]^d. The maximum length of such things we call D(d,n). We have the following inequalities:

    f(d,n) \le \tilde f(d,n) \le D(d,n).

    The second inequality is your first reduction step. Your second reduction step associates to each element of [n]^d an element of \{0,1\}^{nd} and translates the “connectedness” condition to what we have been calling “half-connectedness”. For the time being let me denote \tilde D(2,nd) the maximum length of such families.

    What I am now saying is that each element of \{0,1\}^{nd} can be interpreted as a subset of $[nd]$ (digits equal to 1 correspond to elements in the subset) and the “half-connectedness” is equivalent to the usual “connectedness” that we had in this context. That is, \tilde D(2,nd) = f(nd), and your second reduction step shows simply that

    D(d,n) \le f(nd).

    This inequality does not seem very useful. But we could try to explore D(d,n) directly. For example:

    – for f(d,n) one of the basic questions we wanted to answer (and failed) is whether f(3,n) grows as 3n or 4n. Can we answer that for D(3,n)?

    – can we prove D(d,n) \le 2^{d-1}n? Or at least D(2,n) \le 2n?

    • Uri Leder says:

      It’s a good summarization of what is written above. It’s clear now that the second reduction is actually the original problem.

  10. Paco Santos says:

    I have been thinking on and off about Uri’s “digit” or “vector” model, in which the objects in each layer are vectors in [n]^d. In particular, on adapting the upper bounds that we know for the cases of subsets and multisubsets (a.k.a. monomials). The proofs can indeed be adapted and lead to the following bounds, which leaves me with mixed feelings: The bounds are about as good as the ones we have for (multi)-subsets (the difference is that the “n” becomes an “nd”). But the fact that we cannot (at least I do not see how) even get the actual bounds we have for multisubsets makes me pessimistic about the model as a whole.

    Following Uri I denote D(d,n) the maximum length of a “connected layer family of vectors in [n]^d“.

    Lemma 1: D(d,n) \le nd 2^d.

    Lemma 2: D(d,n) \le 2^{O(\log nd \log d)}= (nd)^{O(\log d)} .

    For the proofs I actually need to generalize the model a little bit. Rather than vectors in [n]^d the objects in my layers are going to be elements of S_1 \times \cdots \times S_d, where the S_i are sets of certain sizes |S_i|. The case of vectors arises when all the S_i‘s have the same size n. Let me denote N=\sum |S_i|, so that N=nd in the case of vectors. With a slight abuse of notation, I denote D(d,N) the maximum length of such a family, and Lemmas 1 and 2 become the following, which looks much closer to the case of (multi)-subsets:

    Lemma 1′: D(d,N) \le N 2^d.

    Lemma 2′: D(d,N) \le 2^{O(\log N \log d)}= N^{O(\log d)} .

    Proof of Lemma 1′: As in the original proof (Corollary 1 in the wiki), divide the family in blocks. The first block consists of all layers that contain a vector with a coordinate in common with some vector of the first layer. The second block starts right after the first block and goes up to the last layer that has a vector with a coordinate in common to the first layer in this block, and so on. As in the original proof, if N_i denotes the number of different values used for all coordinates in the i-th block, we have that the length of the i-th block is bounded above by D(d-1,N_i) \le N_i 2^{d-1}. Also as in the original proof, the same value can only be used for a coordinate in two consecutive blocks, so \sum N_i \le 2N. QED

    Proof of Lemma 2′: Again as in the original proof (Theorem 1 in the wiki), consider the largest s and r such that the first s layers use at most N/2 of the N available elements of the S_i‘s, and the last r layers use at most N/2 of the N available elements of the S_i‘s. Clearly, both s and r are bounded by D(d,N/2). Also, the first layer after the first s has some coordinate in common with the last layer before the last r, so the total number of layers is bounded above by 2 D(d,N/2) + D(d-1,N-1). From this the result follows. QED

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