You are currently browsing the tag archive for the ‘polymath3’ tag.

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.

 Anonymous on The Collatz conjecture, Little… Lex Corvus on It ought to be common knowledg… Craig on The Collatz conjecture, Little… Colin Backhurst on 246A, Notes 0: the complex… Laurent C. on 246A, Notes 2: complex in… Daniele Gerosa on 245C, Notes 4: Sobolev sp… Anonymous on 246A, Notes 2: complex in… markmca on 246A, Notes 2: complex in… Jarred Barber on 246A, Notes 2: complex in… John Nahay on It ought to be common knowledg… Terence Tao on 254A, Notes 4: Some sieve… Anonymous on 246A, Notes 2: complex in… Maths student on Ultraproducts as a Bridge Betw… Anonymous on 246A, Notes 2: complex in… Anonymous on 246A, Notes 2: complex in…