Francisco Santos has announced a counterexample to the Hirsch conjecture:

“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.”

The above is from this website:

https://sites.google.com/a/alaska.edu/kleegrunbaum/

In July the result will presented at a conference in Seattle. More information is available at the above website.

The question of a polynomial upper bound is still open: http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/#comment-3040

http://personales.unican.es/santosf/

“I am afraid my construction says nothing about the polynomiality. As far as I know $2n-2$ (for example) could still be an upper bound for the diameter.”

The question of polynomiality could still be the subject of Polymath3 as that question is open.

I heard about this here:

http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/#comment-3041

Francisco Santos has a website here:

http://personales.unican.es/santosf/

Congratulations to him for solving this!

### Like this:

Like Loading...

*Related*

This entry was posted on May 11, 2010 at 7:09 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

May 13, 2010 at 3:41 am |

[…] Hirsch Conjecture « Euclidean Ramsey Theory […]