Some best possible bounds concerning the traces of finite sets
type: Item
instance of: scholarly article
title: Some best possible bounds concerning the traces of finite sets
zbMATH Open document ID: 0817.05073
DOI: 10.1007/BF02986678
author: V. Pereyra
published in: Graphs and Combinatorics
publication date: 1995-07-11T00:00:00Z
review text: Let \(X\) be an \(n\)-element set and \(\mathcal F\) a system of subsets of \(X\). For a subset \(Y\subset X\) let \({\mathcal F}_ Y\) be the trace of \(\mathcal F\) on \(Y\) (that is, \({\mathcal F}_ Y= \{F\cap Y: F\in {\mathcal F}\})\). Finally for 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\subset X\) such that \(|{\mathcal F}_ Y|\geq r\). For example, the celebrated Vapnik-Červonenkis theorem and the Sauer theorem state that \[ (m,n)\to (2^ s, s)\quad\text{whenever}\quad m> \sum_{0\leq i< s}{n\choose i}. \] This paper studies the \((m,n)\to (m- t,n-1)\) type arrow relations, gives new proofs for the cases \(t= 4,5,6\) using a weight function technique, and derives a new result stating \((m,n)\to (m-9,n- 1)\) for \(m\leq \lceil 65n/14\rceil\).
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 700945
zbMATH Keywords: bounds
zbMATH Keywords: traces of finite sets
zbMATH Keywords: arrow relation
zbMATH Keywords: Vapnik-Červonenkis theorem
zbMATH Keywords: Sauer theorem
zbMATH Keywords: weight function
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
cites work: Induced subsets
cites work: Q3880849
cites work: On the trace of finite sets
cites work: Q4198510
cites work: Arrow relations on families of finite sets
full work available at URL: https://doi.org/10.1007/bf02986678
OpenAlex ID: W1972790035
description: scientific article; zbMATH DE number 700945