Some best possible bounds concerning the traces of finite sets. II (Q1900526)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some best possible bounds concerning the traces of finite sets. II |
scientific article |
Statements
Some best possible bounds concerning the traces of finite sets. II (English)
0 references
10 March 1996
0 references
Let \(X\) be an \(n\)-element set and \({\mathcal F}\) be a family of subsets of \(X\). For the subset \(Y\subseteq X\) denote \({\mathcal F}_Y\) the trace of \(\mathcal F\) on \(Y\). For the positive integers \(m\), \(n\), \(r\), \(s\) the arrow relation \((m, n)\to (r, s)\) means that whenever \(|{\mathcal F}|\geq m\), one can find an \(s\)-element subset \(Y\subseteq X\) such that \(|{\mathcal F}_Y|\geq r\) holds. This paper proves the arrow relations \((m, n)\to (m- 10, n- 1)\) for \(m\leq 5n\) and \((m, n)\to (m- 13, n- 1)\) for \(m\leq \lceil 29n/5\rceil\), and these are best possible results. The proofs are based on a result of P. Frankl on complexes and a generalized Kruskal-Katona theorem. For the first part see the author and \textit{P. Frankl} [ibid. 10, No. 3, 283-292 (1994; Zbl 0817.05073)].
0 references
bounds
0 references
traces of finite sets
0 references
arrow relation
0 references
Kruskal-Katona theorem
0 references