Category Archives: Convex polytopes

The Polynomial Hirsch Conjecture: The Crux of the Matter.

 Consider t disjoint families of subsets of {1,2,…,n}, F_1, F_2, ..., F_t.
 
Suppose that (*) For every i<j<k, and every S \in F_i and T \in F_k, there is R\in F_j  which contains S\cap T

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 and delete m from all of them, you get another example of such families of sets, possibly with smaller value of t. (Those families which do not include any set containing m will vanish.)
 
Theorem: f(n)\le f(n-1)+2f(n/2).
 
Proof: Consider the largest s so that the union of all sets in F_1,...,F_s is at most n/2.   Clearly, s \le f(n/2).
Consider the largest r so that the union of all sets in F_{t-r+1},...,F_t is at most n/2.   Clearly, r\le f(n/2).
 
Now, by the definition of s and r, there is an element m shared by a set in the first s+1 families and a set in the last r+1 families. Therefore (by (*)), when we restrict our attention to the sets containing ‘m’ the families F_{s+1},...,F_{t-r} all survive. We get that t-r-s\le f(n-1). Q.E.D.

Continue reading

“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 d-dimensional polytope with n facets cannot have (combinatorial) diameter greater than n-d. That is, that any two vertices of the polytope can be connected to each other by a path of at most n-d edges. This paper presents the first counter-example to the conjecture. Our polytope has dimension 43 and 86 facets. It is obtained from a 5-dimensional polytope with 48 facets which violates a certain generalization of the d-step conjecture of Klee and Walkup.

This is certainly a major event.  Continue reading

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 convex hull is a k-dimensional face of P will have this property after the perturbation.

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 Seattle only once, in January 2002, when I visited to give a colloquium talk at UW. Although Victor Klee was already retired–he was 76 years old–he came to the Department of Mathematics to talk to me. We had a nice conversation during which he asked “Why don’t you try to disprove the Hirsch Conjecture”?

I have later found out that he asked the same question to many people, including all his students, but the question and the way it was posed made me feel special at that time. This talk is the answer to that question. I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the $d$-step theorem of Klee and Walkup.

Great news! Congratulations Paco!

Hirsch’s conjecture (1957) states that the  graph of a d-dimensional polytope with n facets  has diameter no more than nd. That is, any two vertices of the polytope may be connected to each other by a path of at most nd edges.

We had quite a few posts regarding the Hirsch conjecture and related problems.

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 few posts on the problem until then. We had a long and interesting discussion regarding the Hirsch conjecture followed by another interesting discussion. We can continue the discussion here.

One direction which I see as promising is to try to examine the known upper and lower bounds for the abstract problem.  Here is again a  link for the paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle,  Sasha Razborov, and Thomas Rothvoss.

I would also be happy to hear your thoughts about strong polynomial algorithms for linear programming either via randomised pivot rules for the simplex algorithm or by any other method.  It occured to me that I am not aware of any work trying to examine the possibility that there is no strongly polynomial algorithm for linear programming. Also I am not aware of any work which shows that strongly polynomial algorithm for LP is a consequence of some (however unlikely) computational assumption. (Is it a consequence of NP=P? of P=P-space?)

polymath3

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 theorists. Harrison was interested in comparing planar graphs to graphs embedded in other surfaces.

It will be nice to discuss this question further here (mathoverflow is not an ideal platform for discussions, but some interesting ones have emerged.) So let me offer my answer. Another interesting answer was offered by Joseph Malkevitch.

Three exceptional characteristics of planar graphs

Duality: Perhaps duality is the crucial property of planar graphs. There is a theorem asserting that the dual of a graphic matroid M is a graphic matroid if and only if M is the matroid of a planar graph. In this case, the dual of M is the matroid of the dual graph of G. (See this wikipedia article). This means that the circuits of a planar graph are in one to one correspondence with cuts of the dual graph.

One important manifestation of the uniqueness of planar graphs (which I believe is related to duality) is Kasteleyn’s formula for the number of perfect matchings and the connection with counting trees.

Robust geometric descriptions: Another conceptual difference is that (3-connected or maximal) planar graphs are graphs of convex 3-dimensional polytopes and thus have extra geometric properties that graphs on surfaces do not share. (This is Steinitz’s theorem.)

The geometric definition of planar graphs (unlike various generalizations) is very robust. A graph is planar if it can be drawn in the plane such that the edges are represented by Jordan curves and do not intersect in their interiors; the same class of planar graphs is what we get if we replace “Jordan curves” by “line intervals,” or if we replace “no intersection” by “even number of crossings”. The Koebe-Andreev-Thurston theorem allows us to represent every planar graph by the “touching graph” of nonoverlapping circles. Both (related) representations, via convex polytopes and by circle packing, can respect the group of automorphisms of the graph and its dual.

Simple inductive constructions. Another exceptional property of the class of planar graphs is that planar graphs can be constructed by simple inductive constructions. (In this respect they are similar to the class of trees, although the inductive constructions are not as simple as for trees.) This fails for most generalizations of planar graphs.

A related important property of planar graphs, maps, and triangulations (with labeled vertices) is that they can be enumerated very nicely. This is Tutte theory. (It has deep extensions to surfaces.)

It is often the case that results about planar graphs extend to other classes. As I mentioned, Tutte theory extends to triangulations of other surfaces. Another example is the fundamental Lipton-Tarjan separator theorem, which extends to all graphs with a forbidden minor.

Two interesting generalizations

Continue reading

The Polynomial Hirsch Conjecture: Discussion Thread, Continued

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”  – most of the discussion so far was in this direction.

We had a long and interesting discussion regarding the Hirsch conjecture and I would like to continue the discussion here.  

The way I regard the open collaborative efforts is as an open collective attempt to discuss and make progress on the problem (and to raise more problems), and also as a way to assist people who think or work (or will think or will work) on these problems on their own.

polymath3

Most of the discussion in the previous thread was not about the various problems suggested there but rather was about trying to prove the Hirsch Conjecture precisely! In particular, the approach of Sandeep Koranne and Anand Kulkarni which attempts to prove the conjecture using “flips” (closely related to Pachner moves, or bistaller operations) was extensively discussed.  Here is the link to another paper by Koranne and Kulkarni “Combinatorial Polytope Enumeration“. There is certainly more to be understood regarding flips, Pachner moves, the diameter, and related notions. For example, I was curious about for which Pachner moves  “vertex decomposibility” (a strong form of shellability known to imply the Hirsch bound) is preserved. We also briefly discussed metric aspects of the Hirsch conjecture and random polytopes.

For general background: Here is a  chapter that I wrote about graphs, skeleta and paths of polytopes. Some papers on polytopes on Gunter Ziegler’s homepage  describe very interesting and possibly relevant current research in this area. Here is a  link to Eddie Kim and Francisco Santos’s survey article on the Hirsch Conjecture. 

Here is a link from the open problem garden to the continuous analog of the Hirsch conjecture proposed by Antoine Deza, Tamas Terlaky, and  Yuriy Zinchenko.

Continue reading