Tag Archives: Hirsch conjecture

Karim Adiprasito: Flag simplicial complexes and the non-revisiting path conjecture (A combinatorial proof of the Adiprasito-Benedetti theorem.)

Posted on November 12, 2012 by Gil Kalai

This post is authored by Karim Adiprasito The past months have seen some exciting progress on diameter bounds for polytopes and polytopal complexes, both in the negative and in the positive direction.  Jesus de Loera and Steve Klee described simplicial polytopes which are not  … Continue reading →

Posted in Convex polytopes, Guest blogger | Tagged , , , | Leave a comment

Polymath3 (PHC6): The Polynomial Hirsch Conjecture – A Topological Approach

Posted on April 13, 2011 by Gil Kalai

This is a new polymath3 research thread. Our aim is to tackle the polynomial Hirsch conjecture which asserts that there is a polynomial upper bound for the diameter of graphs of -dimensional polytopes with facets. Our research so far was … Continue reading →

Posted in Convex polytopes, Geometry, Polymath3 | Tagged , , | 37 Comments

Polynomial Hirsch Conjecture 5: Abstractions and Counterexamples.

Posted on November 28, 2010 by Gil Kalai

This is the 5th research thread of polymath3 studying the polynomial Hirsch conjecture. As you may remember, we are mainly interested in an abstract form of the problem about families of sets. (And a related version about families of multisets.) The … Continue reading →

Posted in Open problems, Polymath3 | Tagged , | 60 Comments

Polymath3: Polynomial Hirsch Conjecture 4

Posted on October 21, 2010 by Gil Kalai

So where are we? I guess we are trying all sorts of things, and perhaps we should try even more things. I find it very difficult to choose the more promising ideas, directions and comments as Tim Gowers and Terry Tao did so … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems, Polymath3 | Tagged , | 74 Comments

Polymath 3: The Polynomial Hirsch Conjecture 2

Posted on October 3, 2010 by Gil Kalai

Here we start the second research thread about the polynomial Hirsch conjecture.  I hope that people will feel as comfortable as possible to offer ideas about the problem. The combinatorial problem looks simple and also everything that we know about it is rather simple: … Continue reading →

Posted in Convex polytopes, Open problems, Polymath3 | Tagged , | 104 Comments

Polymath 3: Polynomial Hirsch Conjecture

Posted on September 29, 2010 by Gil Kalai

I would like to start here a research thread of the long-promised Polymath3 on the polynomial Hirsch conjecture. I propose to try to solve the following purely combinatorial problem. Consider t disjoint families of subsets of {1,2,…,n}, . Suppose that … Continue reading →

Posted in Convex polytopes, Open problems, Polymath3 | Tagged , | 120 Comments

“A Counterexample to the Hirsch Conjecture,” is Now Out

Posted on June 15, 2010 by Gil Kalai

  Francisco (Paco) Santos’s paper “A Counterexample to the Hirsch Conjecture” is now out:  For some further information and links to the media see also this page. Here is a link to a TV interview. Abstract: The Hirsch Conjecture (1957) … Continue reading →

Posted in Convex polytopes | Tagged , | 2 Comments

Plans for polymath3

Posted on December 8, 2009 by Gil Kalai

Polymath3 is planned to study the polynomial Hirsch conjecture. In order not to conflict with Tim Gowers’s next polymath project which I suppose will start around January, I propose that we will start polymath3 in mid April 2010. I plan to write a … Continue reading →

Posted in Convex polytopes, Polymath3 | Tagged , | 4 Comments

The Polynomial Hirsch Conjecture: Discussion Thread, Continued

Posted on October 6, 2009 by Gil Kalai

Here is a  link for the just-posted paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle,  Sasha Razborov, and Thomas Rothvoss. And here is a link to the paper  by Sandeep Koranne and Anand Kulkarni “The d-step Conjecture is Almost true”  – … Continue reading →

Posted in Convex polytopes, Open discussion, Open problems | Tagged , | 16 Comments

The Polynomial Hirsch Conjecture: Discussion Thread

Posted on August 9, 2009 by Gil Kalai

This post is devoted to the polymath-proposal about the polynomial Hirsch conjecture. My intention is to start here a discussion thread on the problem and related problems. (Perhaps identifying further interesting related problems and research directions.) Earlier posts are: The polynomial Hirsch … Continue reading →

Posted in Convex polytopes, Open discussion, Open problems | Tagged , | 115 Comments