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

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 devoted to an abstract combinatorial setting. We studied an appealing conjecture by Nicolai Hahnle and considered an […]

Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?

Here are some links and posts related to some of the talks in IPAM’s workshop “Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?” I will be happy to add links to pdf’s of the presentations and to relevant papers. Descriptions and remarks on individual lectures are very welcome. In particular you are most welcome to post here […]

Polynomial Hirsch Conjecture 5: Abstractions and Counterexamples.

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 4th research thread was, in my opinion, fruitful. An interesting further abstraction was offered and […]

Polymath3: Polynomial Hirsch Conjecture 4

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 effectively in Polymath 1,4 and 5.  Maybe this part of the moderator duty can also be outsourced. […]

Polymath3 : Polynomial Hirsch Conjecture 3

Here is the third research thread for the polynomial Hirsch conjecture.  I hope that people will feel as comfortable as possible to offer ideas about the problem we discuss. Even more important, to think about the problem either in the directions suggested by others or on their own. Participants who follow the project and think about the issues […]

Polymath 3: The Polynomial Hirsch Conjecture 2

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: At this stage joining the project should be very easy. If you have an idea […]

Polymath 3: Polynomial Hirsch Conjecture

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 (*) For every , and every and , there is which contains . The basic […]

The Polynomial Hirsch Conjecture: The Crux of the Matter.

 Consider t disjoint families of subsets of {1,2,…,n}, .   Suppose that (*) For every , and every and , there is  which contains .  The basic question is: How large can t  be???   Let’s call the answer f(n).   Remark: If you restrict your attention  to sets in these families containing an element m […]

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

  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) stated that the graph of a -dimensional polytope with facets cannot have (combinatorial) diameter greater […]