Erdős Problem #21 — Smallest intersecting nn-set family evading all (n−1)(n-1)-covers

About 45 years old · traced to

Problem of Lovász and myself, [32]. Let f(n)f(n) be the smallest integer with the following property: There is a family AkA_k, 1≦k≦f(n)1 \leqq k \leqq f(n) satisfying ∣Ak∣=n|A_k| = n, k=1,…,f(n)k = 1, \ldots, f(n), ∣Ak1∩Ak2∣≧1|A_{k_1} \cap A_{k_2}| \geqq 1 for every 1≦k1<k2≦f(n)1 \leqq k_1 < k_2 \leqq f(n), and for every ∣S∣=n−1|S| = n-1 there is an AkA_k with Ak∩S=∅A_k \cap S = \emptyset. In other words our family can not be represented by fewer than nn elements. We proved f(n)<n3/2+εf(n) < n^{3/2+\varepsilon}. An improvement of our method very likely will give f(n)<cnlog⁡nf(n) < cn \log n. I offer 500 dollars for a proof or disproof of f(n)≦Cnf(n) \leqq Cn. In fact we can not even prove or disprove f(n)<3nf(n) < 3n.

References

Additional references

P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25-42.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.