Counterexamples to the Connectivity Conjecture of the Mixed Cells

In [4] a conjecture concerning the connectivity of mixed cells of subdivisions for Minkowski sums of polytopes was formulated. This conjecture was, in fact, originally proposed by Pedersen [3]. It turns out that a positive confirmation of this conjecture can substantially speed up the algorithm for the ``dynamical lifting' developed in [4]. In the mean time, when the polyhedral method is used for solving polynomial systems by homotopy continuation methods [2], the positiveness of this conjecture also plays an important role in the efficiency of the algorithm. Very unfortunately, we found that this conjecture is inaccurate in general. In Section 1 a counterexample is presented for a general subdivision. In Section 2 another counterexample shows that even restricted to ``regular' subdivisions induced by liftings, this conjecture still fails to be true. Received September 18, 1996, and in revised form February 17, 1997.