The number of \(k\)-undivided families of subsets of an \(n\)-element set (\(k\)-undivided Boolean functions). I: The case when \(n\) is even and \(k=2\). (Russian) Zbl 1032.05006

Korshunov, A. D.

Diskretn. Anal. Issled. Oper., Ser. 1 10, No. 4, 31-69 (2003).

Summary: Let \(S\) be a finite set that consists of \(n\) different elements and \(k\geq 2\) be a natural number. A family \({\mathcal F}\) of subsets \(S_1,\dots,S_r\), \(r\geq k\), of the set \(S\) is called \(k\)-undivided if the intersection of any \(k\) sets of \({\mathcal F}\) is non-empty. Such families are equivalent to \(k\)-undivided Boolean functions of \(n\) variables, i.e. to functions \(f(x_1,\dots,x_n)\) such that any \(k\) vectors with \(f(x_1,\dots,x_n)=1\) have at least one component equal to 1. In the paper, an asymptotic for the size of a special subset of \(2\)-undivided Boolean functions of \(n\) variables, where \(n\) is even, is given. A proof of the fact that this asymptotic coincides with an asymptotic for the number of all \(2\)-undivided Boolean functions of \(n\) variables will be presented in the next paper.

MSC:

05A16	Asymptotic enumeration
03E05	Other combinatorial set theory
06E30	Boolean functions

Keywords:

two-valued function; asymptotic expression; Post class