KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №16, Moscow, 2007
Authors: Korshunov A.D.
Lower bounds for the number of (k,r)-nonseparated families of subsets of an n-element set (of (k,r)-nonseparated Boolean functions). The case k≥3 and r≥1
Abstract:
A family F of subsets of an n-element set S (a Boolean function f(x ,…,x )) is called (k,r)-nonseparated if the intersection of any members from F contains at least r elements of S) any k tuples, on which f(x ,…,x ) equals to 1, contains at least r ones). Lower bounds for the number of (k,r)-nonseparated Boolean functions of n variables for fixed k≥3, r≥1 and n→ ∞ are established.
Keywords:
Boolean functions and finite sets, nonseparated Boolean functions and nonseparated finite sets, lower bounds
Publication language: russian,  pages: 12 (p. 31-42)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
Export link to publication in format:   RIS    BibTex