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.

About these ads

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

  1. 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