MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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.