Some best possible bounds concerning the traces of finite sets (Q1340130): Difference between revisions

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\).