Lower bounds for Turán's problem (Q1065822)

For \(n\geq k\geq t\) let T(n,k,t) denote the maximum cardinality of a family of t-element subsets of an n element set X which does not contain all t- subsets of any k-subset of X. Turán determined T(n,k,2) for all \(n\geq k\) and raised the problem of determining or estimating T(n,k,t) for \(t\geq 3\). Using both constructive and probabilistic arguments, the authors show that for every fixed \(a\geq 1\), \(T(n,t+a,t)\geq (1-(a(a+4+o(1))\log t)/{t\choose a}{n\choose t}\) as \(t\to \infty\).