Some best possible bounds concerning the traces of finite sets. II
type: Item
instance of: scholarly article
title: Some best possible bounds concerning the traces of finite sets. II
zbMATH Open document ID: 0834.05059
DOI: 10.1007/BF01793017
author: Mika Watanabe
published in: Graphs and Combinatorics
publication date: 1996-03-10T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 811351
zbMATH Keywords: bounds
zbMATH Keywords: traces of finite sets
zbMATH Keywords: arrow relation
zbMATH Keywords: Kruskal-Katona theorem
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
cites work: Some best possible bounds concerning the traces of finite sets
cites work: Arrow relations on families of finite sets
cites work: On the trace of finite sets
full work available at URL: https://doi.org/10.1007/bf01793017
OpenAlex ID: W4246718195
Recommended article: Some best possible bounds concerning the traces of finite sets
Recommended article: Q3222197
Recommended article: On extremal problems concerning the traces of sets
Recommended article: Q4326640
Recommended article: Fréchet-Urysohn for finite sets, II
Recommended article: Embeddings and the trace of finite sets
Recommended article: A note on traces of set families
Recommended article: Bounds in the theory of finite covers
Recommended article: On Trace Sets of Restricted Continued Fraction Semigroups
Recommended article: The best bounds in a theorem of Russell Lyons
description: scientific article; zbMATH DE number 811351