Category Archives: Convex polytopes

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

Posted in Convex polytopes, Open discussion, Open problems, Polymath3 | 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

Posted in Convex polytopes, Open discussion, Open problems, Polymath3 | 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. 

Posted in Combinatorics, Computer Science and Optimization, Conferences, Convex polytopes | Leave a comment

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

Posted in Combinatorics, Convex polytopes, Open problems, Polymath3 | 5 Comments

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

Posted in Convex polytopes | Tagged , | 2 Comments

Test Your Intuition (12): Perturbing a Polytope

Let P be a d-dimensional convex polytope. Can we always perturb the vertices of P moving them to points with rational coordinates without changing the combinatorial structure of P? In order words, you require that a set of vertices whose … Continue reading

Posted in Convex polytopes, Test your intuition | Tagged , | 4 Comments

Francisco Santos Disproves the Hirsch Conjecture

A title and an abstract for the conference “100 Years in Seattle: the mathematics of Klee and Grünbaum” drew a special attention: Title: “A counter-example to the Hirsch conjecture” Author: Francisco Santos, Universidad de Cantabria Abstract:  I have been in … Continue reading

Posted in Convex polytopes, Open problems, Polymath3 | 36 Comments

Plans for polymath3

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

Why are Planar Graphs so Exceptional

Harrison Brown asked the problem “Why are planar graphs  so exceptional” over mathoverflow, and I was happy to read it since it is a problem I have often thought about over the years, as I am sure have  many combinatorialsists and graph … Continue reading

Posted in Combinatorics, Convex polytopes | 2 Comments