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
    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

    Identifiers