On a two-sided Turán problem (Q1422128)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a two-sided Turán problem |
scientific article |
Statements
On a two-sided Turán problem (English)
0 references
5 February 2004
0 references
Summary: Given positive integers \(n,k,t\), with \(2 \leq k\leq n\), and \(t <2^k\), let \(m(n,k,t)\) be the minimum size of a family \({\mathcal F}\) of nonempty subsets of \([n]\) such that every \(k\)-set in \([n]\) contains at least \(t\) sets from \({\mathcal F}\), and every \((k-1)\)-set in \([n]\) contains at most \(t-1\) sets from \({\mathcal F}\). \textit{R. H. Sloan} et al. [Ann. Math. Artif. Intell. 24, 193-209 (1998; Zbl 0930.68128)] determined \(m(n, 3, 2)\) and \textit{F. Füredi} et al. [On set systems with a threshold property (submitted)] studied \(m(n, 4, t)\) for \(t=2, 3\). We consider \(m(n, 3, t)\) and \(m(n, 4, t)\) for all the remaining values of \(t\) and obtain their exact values except for \(k=4\) and \(t= 6, 7, 11, 12\). For example, we prove that \(m(n, 4, 5) = \binom n2 -17\) for \(n\geq 160\). The values of \(m(n, 4, t)\) for \(t=7,11,12\) are determined in terms of well-known (and open) Turán problems for graphs and hypergraphs. We also obtain bounds of \(m(n, 4, 6)\) that differ by absolute constants.
0 references