On a two-sided Turán problem
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.
- Lower bounds for Turán's problem
- Arrow relations on families of finite sets
- Stability and exact Turán numbers for matroids
- Non-uniform Turán-type problems
- scientific article; zbMATH DE number 4045750 (Why is no real title available?)
- Schttes Tournament Problem and Intersecting Families of Sets
- On set systems with a threshold property
This page was built for publication: On a two-sided Turán problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422128)
