Hirsch Conjecture

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:

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
“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:

Francisco Santos has a website here:

Congratulations to him for solving this!


One Response to “Hirsch Conjecture”

  1. Rumor: Pegatron Tapped For CDMA IPhone Manufacture Says:

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

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: