What we know and what we do not know about Turán numbers
type: Item
instance of: scholarly article
title: What we know and what we do not know about Turán numbers
zbMATH Open document ID: 0839.05050
DOI: 10.1007/BF01929486
author: Alexander Sidorenko
published in: Graphs and Combinatorics
publication date: 1996-06-18T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05D15
zbMATH DE Number: 784146
zbMATH Keywords: Turán number
zbMATH Keywords: covering number
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Q3313888
cites work: A note on the probabilistic approach to Turan's problem
cites work: On the covering of \(t\)-sets with \((t+1)\)-sets: \(C(9,5,4)\) and \(C(10,6,5)\)
cites work: Q3960735
cites work: On the combinatorial problems which I would most like to see solved
cites work: Method for construction of (3,4)-graphs
cites work: Minimal coverings of pairs by triples
cites work: Lower bounds for Turán's problem
cites work: Covering pairs by \(q^ 2+q+1\) sets
cites work: Q5682334
cites work: Q4083663
cites work: Remarques sur deux problèmes extrémaux. (Remarks on two extremal problems)
cites work: New constructions for covering designs
cites work: Q5512796
cites work: A class of constructions for Turan's (3,4)-problem
cites work: Q3915001
cites work: An upper bound for the transversal numbers of 4-uniform hypergraphs
cites work: Coverings of pairs by quintuples
cites work: On Turan hypergraphs
cites work: On the covering of pairs by quadruples. I
cites work: On the covering of pairs by quadruples. II
cites work: Q4065553
cites work: Q3889076
cites work: Q3216667
cites work: Covering triples by quadruples: an asymptotic solution
cites work: Coverings pairs by quintuples: The case v congruent to 3 (mod 4)
cites work: Q4026151
cites work: Q3773899
cites work: Q3829564
cites work: On a packing and covering problem
cites work: On coverings
cites work: Q4745841
cites work: Systems of sets possessing the T-property
cites work: Method of quadratic forms in the Turan combinatorial problem
cites work: Q3699700
cites work: Precise values of Turan numbers
cites work: Q3919732
cites work: Q4712027
cites work: Q4742805
cites work: Q3340874
cites work: Q3698806
cites work: Q3809813
cites work: Lower bounds for coverings of pairs by large blocks
cites work: Q3214957
description: scientific article; zbMATH DE number 784146