I am sorry to say Martin Gardner died May 22. He was 95 years old. He was the author of many books on recreational mathematics and on other subjects. He was one of the first authors I read in mathematics.

## Archive for May, 2010

### Martin Gardner

May 23, 2010### Hirsch Conjecture 3

May 18, 2010I have more information about the counterexample

to the Hirsch conjecture. A version of the paper is circulating. It should be available May 24 to the public if all goes well. It looks like there are more vertices then previously thought $2^{46}$ rather than a billion. Also there is an estimate of computation time of $2^{30}$ thousand year periods. My source for this is the following post.

### Hirsch Conjecture 2

May 12, 2010Here is more information about the counterexample to the Hirsch conjecture:

“my proof has two parts: (1) there is a 5-polytope with 48 facets, with the following properties: it has two vertices $u$ and $v$ contained in all the facets (each in 24 of them) and no path of length five joins $u$ to $v$. (2) Then there is what I call the “generalized $d$-step theorem” saying that from this, using certain wedges and perturbations, you can get a 43-dimensional polytope with 86 facets and without the Hirsch property. Part (1) is totally explicit and has been verified with computer software (polymake). Part (2) is not explicit.”

The above is from this post.

Also from the above post the polytope which provides the counterexample may have a billion vertices.

### Hirsch Conjecture

May 11, 2010Francisco 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!

### Polymath5

May 10, 2010### Introduction to Paper

May 1, 2010A draft of an introduction to the paper ““Density Hales-Jewett and Moser numbers” is here.