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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
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
links / mardi / namelinks / mardi / name
 

Latest revision as of 18: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
    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

    Identifiers