Monthly Archives: May 2010

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.

Francisco Santos Disproves the Hirsch Conjecture

A title and an abstract for the conference “100 Years in Seattle: the mathematics of Klee and Grünbaum” drew a special attention:

Title: “A counter-example to the Hirsch conjecture”

Author: Francisco Santos, Universidad de Cantabria


I have been in Seattle only once, in January 2002, when I visited to give a colloquium talk at UW. Although Victor Klee was already retired–he was 76 years old–he came to the Department of Mathematics to talk to me. We had a nice conversation during which he asked “Why don’t you try to disprove the Hirsch Conjecture”?

I have later found out that he asked the same question to many people, including all his students, but the question and the way it was posed made me feel special at that time. This talk is the answer to that question. I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the $d$-step theorem of Klee and Walkup.

Great news! Congratulations Paco!

Hirsch’s conjecture (1957) states that the  graph of a d-dimensional polytope with n facets  has diameter no more than nd. That is, any two vertices of the polytope may be connected to each other by a path of at most nd edges.

We had quite a few posts regarding the Hirsch conjecture and related problems.

Drunken Time and Drunken Computation

The problem

We are used to computer programs or models for computations that perform at time i step U_i, i=1,2,\dots,N.  Suppose that time is drunk, so instead of running these steps in their correct order, we apply at time i step \pi(i), where \pi is a random permutation which is substantially correlated with the identity permutation.  What then is our computational power?

Continue reading