Is there an integer \(C\) such that among \(C^n\) sets with \(n\) elements, there are always \(k\) whose mutual intersection is the same as each pairwise intersection?
~Equivalently~
Denote by \(f_k(n)\) the smallest integer so that if \( \left|A_i\right|=n, 1 \leq i \leq f_k(n) \) then there are \(k\) \(A_i\)'s which have pairwise the same intersection. Then $$f_k(n)< c_k^n$$ where \(c_k\) depends only on k.
Note: The prize is not for the general case, but for the case when \(k=3\).
| Author | Date Published | Prize | Paid By |
| Paul Erdős, Richard Rado [1] | 1960 | $1,000 | Paul Erdős |
In 1996, Kostochka [2] showed that $$f_3(n)< n!\left( \frac{c\log\log(n)}{\log(n)}\right)^n$$
Related Problems:
[1] Erdős, Paul; Rado, R. (1960), "Intersection theorems for systems of sets", Journal of the London Mathematical Society, Second Series, 35 (1): 85–90, doi:10.1112/jlms/s1-35.1.85, ISSN 0024-6107, MR 0111692
[2] A. V. Kostochka, A bound of the cardinality of families not containing \(∆\)-systems, The Mathematics of Paul Erdős (R. L. Graham and J. Neˇsetˇril, eds.), 229–235, Springer-Verlag, Berlin, 1996.
Sunflower Conjecture;