On two intersecting set systems and k-continuous Boolean functions (Q1820783): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3941433 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5331500 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Interpolation of functions over a measure space and conjectures about memory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3708835 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Critical hypergraphs and interesting set-pair systems / rank | |||
Normal rank |
Latest revision as of 19:09, 17 June 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