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