On two intersecting set systems and k-continuous Boolean functions (Q1820783): Difference between revisions

Let m(a,b) be the minimum natural number satisfying that for any two set systems \({\mathcal A}\) and \({\mathcal B}\) with \(A\cap B\neq \emptyset\) and \(| A| \leq a\), \(| B| \leq b\) (whenever \(A\in {\mathcal A}\), \(B\in {\mathcal B})\) there exists an X, \(| X| =m(a,b)\), such that \(A\cap B\cap X\neq \emptyset\) when \(A\in {\mathcal A}\), \(B\in {\mathcal B}\). The author proves the following theorem: For a,b\(\geq 1\), \(\frac{1}{4}\left( \begin{matrix} a+b\\ a\end{matrix} \right)<m(a,b)<\left( \begin{matrix} a+b\\ a\end{matrix} \right)\). As a consequence, any k-continuous Boolean function can depend on at most \(\left( \begin{matrix} 2k\\ k\end{matrix} \right)\) variables.