Some best possible bounds concerning the traces of finite sets (Q1340130): Difference between revisions
From MaRDI portal
Latest revision as of 11:16, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some best possible bounds concerning the traces of finite sets |
scientific article |
Statements
Some best possible bounds concerning the traces of finite sets (English)
0 references
11 July 1995
0 references
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\).
0 references
bounds
0 references
traces of finite sets
0 references
arrow relation
0 references
Vapnik-Červonenkis theorem
0 references
Sauer theorem
0 references
weight function
0 references
0 references