On two intersecting set systems and k-continuous Boolean functions
type: Item
instance of: scholarly article
title: On two intersecting set systems and k-continuous Boolean functions
zbMATH Open document ID: 0615.05001
DOI: 10.1016/0166-218X(87)90074-6
author: Zsolt Tuza
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 3995684
zbMATH Keywords: finite set
zbMATH Keywords: intersecting system
zbMATH Keywords: hypergraph
zbMATH Keywords: Boolean function
MaRDI profile type: Publication
cites work: Q3941433
cites work: Q5331500
cites work: Interpolation of functions over a measure space and conjectures about memory
cites work: Q3708835
cites work: Critical hypergraphs and interesting set-pair systems
description: scientific article; zbMATH DE number 3995684