Tag Archives: Hirsch conjecture

The Polynomial Hirsch Conjecture – How to Improve the Upper Bounds.

Posted on July 30, 2009 by

I can see three main avenues toward making progress on the Polynomial Hirsch conjecture. One direction is trying to improve the upper bounds, for example,  by looking at the current proof and trying to see if it is wasteful and if so where … Continue reading →

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

The Polynomial Hirsch Conjecture, a Proposal for Polymath3 (Cont.)

Posted on July 28, 2009 by

The Abstract Polynomial Hirsch Conjecture A convex polytope is the convex hull of a finite set of points in a real vector space. A polytope can be described as the intersection of a finite number of closed halfspaces. Polytopes have … Continue reading →

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

The Polynomial Hirsch Conjecture: A proposal for Polymath3

Posted on July 17, 2009 by

This post is continued here.  Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture. The Hirsch conjecture: The graph of a d-polytope with n vertices  facets has diameter at most n-d. We devoted several … Continue reading →

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

A Diameter problem (7): The Best Known Bound

Posted on December 1, 2008 by

  Our Diameter problem for families of sets Consider a family of subsets of size d of the set N={1,2,…,n}. Associate to a graph as follows: The vertices of  are simply the sets in . Two vertices and are adjacent if . … Continue reading →

Posted in Combinatorics, Convex polytopes | Tagged , | 1 Comment

A Diameter Problem (6): Abstract Objective Functions

Posted on November 4, 2008 by

George Dantzig and Leonid Khachyan In this part we will not progress on the diameter problem that we discussed in the earlier posts but will rather describe a closely related problem for directed graphs associated with ordered families of sets. The role models for … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems | Tagged , | 7 Comments

A Diameter Problem (5)

Posted on September 16, 2008 by

6. First subexponential bounds.  Proposition 1: How to prove it: This is easy to prove: Given two sets and in our family , we first find a path of the form where, and . We let with and consider the family … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems | Tagged | 1 Comment

Diameter Problem (4)

Posted on September 9, 2008 by

Let us consider another strategy to deal with our diameter problem. Let us try to associate other graphs to our family of sets. Recall that we consider a family of subsets of size  of the set . Let us now associate  … Continue reading →

Posted in Combinatorics, Open problems, Convex polytopes | Tagged | 1 Comment

Diameter Problem (3)

Posted on September 7, 2008 by

3. What we will do in this post and and in future posts We will now try all sorts of ideas to give good upper bounds for the abstract diameter problem that we described. As we explained, such bounds apply … Continue reading →

Posted in Combinatorics, Open problems, Convex polytopes | Tagged , , | 1 Comment