On two intersecting set systems and k-continuous Boolean functions (Q1820783): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:47, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On two intersecting set systems and k-continuous Boolean functions |
scientific article |
Statements
On two intersecting set systems and k-continuous Boolean functions (English)
0 references
1987
0 references
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.
0 references
finite set
0 references
intersecting system
0 references
hypergraph
0 references
Boolean function
0 references