What we know and what we do not know about Turán numbers (Q1895823): Difference between revisions

Three equivalent combinatorial problems are considered. The Turán number \(T(n, k, r)\) is the minimum size of a system of \(r\)-element subsets of an \(n\)-set \(X_n\) such that every \(k\)-element subset of \(X_n\) contains a member of the system; any such system is called a Turán \((n, k, r)\)-system. The covering number \(C(n, m, p)\) is the minimum number of \(m\)-subsets of \(X_n\) needed to cover all \(p\)-subsets. \(U(n, q, r)\) is the minimum number of subsets of size at least \(r\), for which any transversal contains at least \(k\) elements. It is observed that \(C(n, m, p)= T(n, n- p, n- m)\), \(U(n, q, r)= T(n, n- q+ 1,r)\). The limit \(\lim_{n\to \infty} {T(n, k, r)\over {n\choose r}}\) is known to exist, and denoted by \(t(k, r)\). Under sections headed Recursive Inequalities, Lower Bounds, Upper Bounds, The Case of Small \({n\over k-1}\), The Case \(r= 2\), The Case \(r= 3\), The Case \(r= 4\), The Case of Small \(n- k\) (Covering Numbers), the author describes the present status of the problem of determining or bounding these numbers; he includes seven conjectures concerning the numbers \(T(n, k, r)\), the limits \(t(k, r)\), and extremal configurations.