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 d-dimensional polytopes with n facets. Our research so far was devoted to an abstract combinatorial setting. We studied an appealing conjecture by Nicolai Hahnle and considered an even more general abstraction proposed by Yury Volvovskiy. Comments towards this abstract conjecture are most welcome!

Here, I would like to mention a topological approach which follows a result that was discovered independently by Tamon Stephen and Hugh Thomas in their paper An Euler characteristic proof that 4-prismatoids have width at most 4,
and by Paco Santos in his paper Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids. This post is based on a discussion with Paco Santos at Oberwolfach.

Two maps on a two dimensional Sphere

Theorem: Given a red map and a blue map drawn in general position on S^2 there is an intersection point of two edges of different colors which is adjacent (in the refined map) to a red vertex and to a blue vertex.

Blue and black maps

There are two proofs for the theorem. The proof by Stephen and Thomas uses an Euler characteristic argument. The proof by Santos applies a connectivity argument. Both papers are short and elegant. Both papers point out that the result does not hold for maps on a torus.

Santos’ counterexample to the Hirsch conjecture is based on showing that a direct extension of this result to maps in three dimensions fails. (Even for two maps coming from fans based on polytopes.) Of course, first Paco found his counterexample and then the two-map theorem was found in response to his question  of whether one can find in dimension four counterexamples of the kind he presented in dimension five.

The theorem by Santos, Stephen, and Thomas is very elegant. The proofs are simple but far from obvious and it seems to me that the result will find interesting applications. Its elegance and depth reminded me of Anton Klyachko’s car crash theorem.

A topological question in high dimensions

Now we are ready to present a higher-dimensional analog:

Tentative Conjecture: Let M_1 be a red map and let  M_2 be a blue map drawn in general position on S^{n}, and let $M$ be their common refinement.  There is a vertex w of M a blue vertex v \in M_1, a red vertex u \in M_2 and two faces F,~G \in M such that 1) v,w \in F, 2) w,u \in G, and 3) \dim F + \dim G =n.

A simple (but perhaps not the most general) setting in which to ask this question is with regard to the red and blue maps  coming from red and blue polyhedral fans associated to red and blue convex polytopes. The common refinement will be the fan obtained by taking all intersections of cones, one from the first fan and one from the second.

(Perhaps when n=2k we can even guarantee that \dim F=\dim G=k.)

Why the tentative conjecture implies that the diameter is polynomial

An affirmative answer to this conjecture will lead to a bound of the form dn for the graph of d-polytopes with n facets.

Here is why:

– It is known that the diameter of every polytope with n facets and dimension d is bounded above by the “length” of a Dantzig figure with 2n-2d facets and n-d vertices.

Here a Dantzig figure is a simple polytope of dimension D with 2D facets and two complementary vertices. (i.e., two vertices such that each vertex lies in half of the facets, and they do not belong to any common facet).

The length of the Dantzig figure is the graph distance between these two vertices. This is the classical “d-step theorem” of Klee and Walkup, 1967.

– The length of a Dantzig figure of dimension d is the same as the minimum distance between blue and red vertices in a pair of two maps in the (d-2)-sphere, with d cells each.

– Our tentative conjecture implies, by dimension on d, that the minimum distance between blue and red vertices in a pair of maps in the d-sphere and with n cells is bounded above by (essentially) nd. (n cells means “cells of the blue map plus cells of the red map”, not “cells of the common refinement”).

The abstract setting and other approaches

More comments, ideas, and updates on the abstract setting are of course very welcome Also very welcome are other approaches to the polynomial Hirsch conjecture, and discussion of related problems.

An example showing that the theorem fail for blue and red maps on a torus.

A Beautiful Garden of Hypertrees

We had a series of posts (1,2,3,4) “from Helly to Cayley” on weighted enumeration of Q-acyclic simplicial complexes. The simplest case beyond  Cayley’s theorem were Q-acyclic complexes  with n vertices, {n \choose 2} edges, and {{n-1} \choose {2}} triangles. One example is the six-vertex triangulation of the real projective plane. But here, as in many other places, we are short of examples.

Nati Linial,  Roy Meshulam and Mishael Rosenthal wrote a paper with very surprising examples of Q-acyclic simplicial complexes called “sum complexes”. The basic idea is very simple: The vertices are \{1,2,\dots , n\}. Next you pick three numbers a,b and c and consider all the triples i,j,k so that i+j+k is either a or b or c. And let’s assume that n is a prime.

So how many triangles do we have? A fraction of 3/n of all possible triangles which is what we want ({{n-1} \choose {2}}).

If the three numbers form an arithmetic progression then the resulting simplicial complex is collapsible. In all other cases it is not collapsible. The proof that it is Q-acyclic uses a result of Chebotarëv on Fourier analysis. (So what does Fourier analysis have to do with computing homology? You will have to read the paper!) The paper considers the situation in all dimensions.

What about such combinatorial constructions for Q-homology spheres?

Helly’s Theorem, “Hypertrees”, and Strange Enumeration II: The Formula

In the first part of this post we discussed an appealing conjecture regaring an extension of Cayley’s counting trees formula. The number of d-dimensional “hypertrees” should somehow add up  to n^{{n-2} \choose {d}}. But it was not clear to us which complexes we want to count and how. This counting problem started from a Helly type conjecture proposed by Katchalski and Perles.
For d=2 n=6 the situation was confusing. We had 46608 complexes that were collapsible. Namely, for these complexes it is possible to delete all triangles one at a time by removing in each step a triangle T and an edge E which is contained only in T. Once all triangles are removed we are left with a spanning tree on our 6 vertices. (Five out of the 15 edges survive).  In addition, there were 12 simplicial complexes representing 6-vertex triangulations of the real projective plane. 
We will continue the discussion in this part, show how the conjecture can be saved and at what cost. We will also discuss the solution of the Perles-Katchalski conjecture –  a Helly’s type conjecture that we started with.   In the third part we will explain the proof and mention further related results and problems, discuss higher Laplacians and their spectrum, and mention a few related probabilistic problems.  
 
 

 We ended part one with the question “What can we do?”

8. How to make the conjecture work

With such a nice conjecture we should not take no for an answer. To make the conjecture work we need to count each of the twelve 6-vertex triangulations of the real projective plane, four times. Four is the square of the number of elements in H_1(RP^2). This is the difference in higher dimensions, a Q-acyclic complex need not be Z-acyclic. Homology groups can have non trivial torsion.  In our case H_{d-1}(K) can be a non trivial finite group.
Here is the theorem:   

\sum |H_{d-1}(K,{\bf Z})|^2 = n^{{n-2} \choose {d}},

where the sum is over all d-dimensional simplicial complexes K on n labelled vertices, with a complete (d-1)-dimensional skeleton, and which are Q-acyclic, namely all their (reduced) homology groups with rational coefficients vanish.  
Looking at the various proofs of Cayley’s formula (there are many many many beautiful proofs and more), which one (or more) would you expect to extend to the high dimensional case? We will answer this question in part III. Can you guess? Continue reading

Helly’s Theorem, “Hypertrees”, and Strange Enumeration I

1. Helly’s theorem and Cayley’s formula

Helly’s theorem asserts: For a family of n convex sets in R^d, n > d, if every d+1 sets in the family have a point in common then all members in the family have a point in common.

Cayley’s formula asserts: The number of  trees on n labelled vertices is n ^{n-2}.

In this post (in two parts) we will see how an extension of Helly’s theorem has led to high dimensional analogs of Cayley’s theorem. 

  

left: Helly’s theorem demonstrated in the Stanford Encyclopedia of Philosophy (!), right: a tree 

2. Background

This post is based on my lecture at Marburg. The conference there was a celebration of new doctoral theses Continue reading

A Small Debt Regarding Turan’s Problem

Turan’s problem asks for the minimum number of triangles on n vertices so that every 4 vertices span a triangle. (Or equivalently, for the maximum number of triangles on n vertices without a “tetrahedron”, namely without having four triangles on four vertices.)  When we discussed Turan’s problem, we stated a lemma without giving the proof. Here is the proof.

Lemma: A three uniform hypergraph G on n vertices, so that every four vertices span a triangle satisfies:

\dim H_1(K,F) \le n-2.

Here, K is the simplicial complex on the n vertices which has all possible edges and, in addition, the triangles in G. F can be any field of coefficients, below we assume that F=Z/2. (But very little changes are required for the general case.)

Proof:  A little background: The space of 1-dimensional cycles of the complete graph with n vertices is of dimension {n-1} \choose {2}. Start with the star T where vertex ‘1’ is adjacent to all other vertices. every edge e={i,j} not in T, determines a cycle c(e) supported by the triangle {1,i} {1,j} and {i,j}. It is easy to see that all these cycles are linearly independent in the space of cycles of the complete graph and span this space.

Now to the proof itself. Let G be a hypergraph with the property that every 4 vertices span a triangle and let K be the 2-dimensional simplicial complex obtained by adding the triangles in G to the complete graph. H_1(K) is still spanned by the cycles c(e) for all edges e={i,j} 1<i<j \le n. Let H be a maximal set of edges e so that all the corresponding c(e) are linearly independent in H_1(K). It suffices to prove:

Claim: H is a forest.

Continue reading