Consider t disjoint families of subsets of {1,2,…,n}, .

Suppose that **(*)** For every , and every and , there is which contains .

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:** .

**Proof:** Consider the largest s so that the union of all sets in is at most n/2. Clearly, .

Consider the largest r so that the union of all sets in is at most n/2. Clearly, .

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 all survive. We get that . **Q.E.D.**

**Remarks: **

1) The recurrence relation gives . The major task is to prove a polynomial upper bound for or to find examples showing that is superpolynomial in .

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 . The argument above gives the relation , which implies .

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

Steven TwentymanIs 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’???

Holly Rouse-Sweeneyyes

Pingback: Polymath5 « Euclidean Ramsey Theory

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

Holly Rouse-Sweeney….