# 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, 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???

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.

Remarks:

1) The recurrence relation gives $f(n)\le n^{\log n+1}$. The major task is to prove a polynomial upper bound for $f(n)$ or to find examples showing that $f(n)$ is superpolynomial in $n$.

2) The abstract setting is taken from the paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle,  Sasha Razborov, and Thomas Rothvoss. We can consider families of d-subsets of {1,2,…, n}, and denote the maximum cardinality t by $f(d,n)$. The argument above gives the relation $f(d,n) \le 2f(d,n/2)+f(d-1,n-1)$, which implies $f(d,n)\le n{{\log n+d}\choose{\log n}}$$\le n^{\log d+1}$.

3) $f(d,n)$ (and thus also $f(n)$) are upper bounds for the diameter of graphs of d-polytopes with n facets.

## 5 thoughts on “The Polynomial Hirsch Conjecture: The Crux of the Matter.”

1. Steven Twentyman

Is there any possibility that all mathematical formulas, concepts, proofs can only get solved ate some single point in the history of mankind: be it past, present or future? Would it require a cross germination of genes in the totality of humanity to combine into a new structure to fully make us understand what is happening in all branches of mathematics???

Would it have to be a ‘physical’ process: a genetic freak in a single human being to join all the dots together. Could this super special person be ‘you’???

2. Pingback: Polymath5 « Euclidean Ramsey Theory