# Category Archives: Convex polytopes

## Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding … Continue reading

## 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 … Continue reading

| Tagged , | 74 Comments

## 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 … Continue reading

## 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: … Continue reading

| Tagged , | 104 Comments

## 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 … Continue reading

| Tagged , | 120 Comments

## Faces of Simple 4 Polytopes

In the conference celebrating Klee and Grünbaum’s mathematics at Seattle Günter Ziegler proposed the following bold conjecture about 4 polytopes. Conjecture: A simple 4-polytope with facets has at most a linear number (in )  two dimensional faces which are not 4-gons! If the polytope … Continue reading

Posted in Convex polytopes | 3 Comments

## IPAM Workshop – Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?

Workshop at IPAM: January 18 – 21, 2011 Here is the link to the IPAM conference.

## 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).   … Continue reading