Gil Kalai has officially started the Polymath3 project (Polynomial Hirsch conjecture) with a research thread at his blog.

The original aim of this project is to prove the polynomial Hirsch conjecture, which is a conjecture in the combinatorial geometry of polytopes.  However, there is a reduction due to Eisenbrand, Hahnle, Razborov, and Rothvoss that would deduce this conjecture from a purely combinatorial conjecture, which can be stated as follows.

Combinatorial polynomial Hirsch conjecture. Let {\mathcal F}_1,\ldots,{\mathcal F}_t be non-empty collections of subsets of \{1,\ldots,n\} with the following properties:

  1. (Disjointness) {\mathcal F}_i \cap {\mathcal F}_j = \emptyset for every i \neq j.
  2. (Connectedness)  If 1 \leq i < j < k \leq t and A \in {\mathcal F}_i, B \in {\mathcal F}_ k, there exists C \in {\mathcal F}_j such that A \cap B \subset C.

Then t is of polynomial size in n (i.e. t = O(n^{O(1)})).

For instance, when n=3, one can obtain such a family with t=6, e.g.

{\mathcal F}_1 = \{ \emptyset\}, {\mathcal F}_2 = \{ \{1\}\}, {\mathcal F}_3 = \{\{1,2\}\}, {\mathcal F}_4 = \{\{1,2,3\}\},

{\mathcal F}_5 = \{\{2,3\}\}, {\mathcal F}_6 = \{\{3\}\};

one can show that this is the best possible value of t for this choice of n.  The best possible value of t for n=4 is still not worked out; it is between 8 and 11.

One appealing thing about this problem is that there is a simple elementary argument that gives the bound t \leq n^{\log_2 n + 1} for all n \geq 2; and so in some sense one is “only a logarithm away” from proving the conjecture.  Anyway, the project is just starting, and does not require any particularly specialised background, so anyone who may be interested in this problem one may want to take a look at the research thread.

About these ads