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.



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

  3. Pingback: Polymath 3: Polynomial Hirsch Conjecture « Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s