Archive for May, 2010

Martin Gardner

May 23, 2010

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.

Advertisements

Hirsch Conjecture 3

May 18, 2010

I 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, 2010

Here 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, 2010

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!

Polymath5

May 10, 2010

We have a new upper bound for a sequence with discrepancy 2. It must have length less than 2016. The longest such sequence we have is 1124. see here for more information. For more about the computation there is this post .

Also this link describes the Polymath5 project in simple terms.

Introduction to Paper

May 1, 2010

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