Erdős Problem #20 — Exponential bound for families with no kk-set sunflower

About 31 years old · traced to

A family of sets AiA_i, i=1,2,…,i = 1, 2, \ldots, is called a strong Δ\Delta-system if all the intersections Ai∩AjA_i \cap A_j (i≠ji \neq j) are identical, i.e., if Ai∩Aj=⋂iAiA_i \cap A_j = \bigcap_i A_i. Rado and I [40, 41] investigated the following question: Denote by fs(n,k)f_s(n,k) the smallest integer for which every family of sets AiA_i (1≤i≤fs(n,k)1 \leq i \leq f_s(n,k)) with ∣Ai∣=n|A_i| = n for all ii contains kk sets which form a strong Δ\Delta-system. Rado and I conjectured

fs(n,3)<c3nf_s(n,3) < c_3^n

and no doubt also

fs(n,k)<ckn.f_s(n,k) < c_k^n.

I offer 1000 dollars for a proof or disproof of (11).

References

Additional references

P. Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas IME-USP 2 (1995), 165-186.

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.