For integers \(1 < t < k < n\) the set system \(\mathcal F\) on \([n]\) has the \((k,t)\)-threshold property if every \(k\)-subset of \([n]\) contains at least \(t\) sets from \(\mathcal F\) while every \((k-1)\)-subset of \([n]\) contains less than \(t\) sets from \(\mathcal F.\) The minimal cardinality of such a set system is denoted by \(m(n,k,t).\) This papers determines \(m(n,k,t)\) exactly for large enough \(n.\) It also shows that \(m(n,k,2)=(1+o(1))T_{(k-1)}(n,k,2)\) where the last item on the RHS is the generalized Turán number.
Recommendations
Cites work
- A note on the probabilistic approach to Turan's problem
- An exact result for 3-graphs
- Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
- How to make a graph bipartite
- scientific article; zbMATH DE number 3843786 (Why is no real title available?)
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 3685495 (Why is no real title available?)
- scientific article; zbMATH DE number 3788645 (Why is no real title available?)
- scientific article; zbMATH DE number 736304 (Why is no real title available?)
- scientific article; zbMATH DE number 3224335 (Why is no real title available?)
- Lower bounds for Turán's problem
- Maximal consistent families of triples
- Non-uniform Turán-type problems
- On a two-sided Turán problem
- On frequent sets of Boolean matrices
- On hypergraphs with every four points spanning at most two triples
- On the connection between chromatic number, maximal clique and minimal degree of a graph
- Supersaturated graphs and hypergraphs
- Three-graphs without two triples whose symmetric difference is contained in a third
- Upper bounds for Turán numbers
This page was built for publication: On set systems with a threshold property
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q856857)
