Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The following problem came from some joint research with Kevin Ford and Regis de la Breteche. We believe a confirmation of the question presented at the end of this post will allow us to sharpen our results.


We are considering families $F$ of sets which satisfy three properties. First, each family $F$ is intersecting; that is, for all $A_1, A_2\in F$, we have that $A_1\cap A_2$ is non-empty. Second, each family is finite, and each set in $F$ is finite as well, with the maximum cardinality of sets $A\in F$ called the size of $F$. And third, each $F$ satisfies the following minimality condition: if $A\in F$ and $A'$ is a proper, non-empty subset of $A$, then the family of sets $F \cup {A'} \setminus {A}$ is not intersecting.

It can be shown quite quickly that if $F$ has size $n$, then $|F|\le n^n$.

It is easy to construct a great many such families. If one has a family $F$ of size $n$ and a set $B=\{ b_1, b_2 , \dots, b_{n+1} \}$ that does not intersect any set of $F$, then one can create a new family $F'$ that contains the set $B$ and new sets of the form $A\cup \{b_i \}$, $1\le i \le n+1$, where each $b_i$ and each set $A$ is part of at least one set of this type. One can start from the trivial family $F=\{ \{a\}\}$ and build up many ($n$-uniform) families in this way.

By appending each $b_i$ to as few sets as possible, one can obtain families of size $n$ with very few total sets (as few as $n+1$). By appending each $b_i$ to every set $A\in F$, one can obtain families of size $n$ with cardinality almost that of the maximal order $n^n$

Our question is, in bare form, this: suppose a family of size $n$ is very large, close to the maximal order $n^n$, then must there exist an element or subset that is extremely popular, in the sense that it is contained in many more sets than the average?

Put more concretely:

Is it true that given a family $F$ of size $n$, there exists a set $C$, with $|C|=k$ such that $$\left|\{ A \in F: C \subset A \} \right| \ge \frac{|F|}{n^{o(k)}} $$ as $n \to \infty$? If so, how good a bound can one obtain? Would $$\frac{|F|}{100^k}$$ work?

Our reason for believing this may be true comes from the appending construction mentioned above. If the appending procedure is applied several times, those elements/subsets belonging to the original $F$ will be very popular in the final family obtained.

share|improve this question
    
The construction you give seems to provide a family of size n with n^(n-2) as an upper bound to the number of elements once n > 5. Do you have examples of F of size n with at least n^(n-1) elements for n > 3? Gerhard "Ask Me About System Design" Paseman, 2011.08.31 –  Gerhard Paseman Sep 1 '11 at 6:53
    
In fact, your construction gives more like (e-1)n! ellements each of size n. Do you have any F of size n with cardinality greater than (e- 1)n! ? Gerhard! "Ask Me About System Design" Paseman, 2011.09.01 –  Gerhard Paseman Sep 1 '11 at 7:11
    
Gerhard, no, the large construction listed here is the largest that we have been able to detect (and it is a construction lifted from Erdos and Lovasz' paper in "Finite and Infinite Sets" if I recall correctly). –  Joseph Vandehey Sep 1 '11 at 12:05
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.