Intersection statements for systems of sets (Q1369684): Difference between revisions

A collection of sets is called a \(\Delta\)-system if any two sets have the same intersection. Let \(f(k,r)\) be the least integer such that any collelction of \(f(k,r)\) \(k\)-element sets contains a \(\Delta\)-system consisting of \(r\) sets. \textit{P. Erdös} and \textit{R. Rado} [J. Lond. Math. Soc. 44, 467-479 (1969; Zbl 0172.29601)] proved that \((r-1)^k< f(k,r)< k!(r-1)^k\) and conjectured that \(f(k,r)<C^k\) for some constant \(C\). Erdös offered \$1000 for a proof or disproof of this for \(r=3\). The paper under review concerns a related problem. Let \(F(n,r)\) be the greatest integer such that there exists a collection of subsets of an \(n\)-element set which does not contain a \(\Delta\)-system consisting of \(r\) sets. \textit{P. Erdös} and \textit{E. Szemerédi} [J. Comb. Theory, Ser. A 24, 308-313 (1978; Zbl 0383.05002)] showed that \(F(n,3)<2^{n-\sqrt{n}/10}\) and \(F(n,r)>(1+c_r)^n\), where the constant \(c_r\to 1\) as \(r\to\infty\). The authors provide new lower bounds for \(F(n,r)\) which are constructive and improve the previous best probabilistic results. They also prove a new upper bound. Moreover, for certain \(n\) it is shown that \(F(n,3)\geq 1.551^{n-2}\).