The number of \(k\)-undivided families of subsets of an \(n\)-element set (\(k\)-undivided Boolean functions of \(n\) variables). II: The case when \(n\) is odd and \(k=2\). (Russian) Zbl 1077.05007

[For Part I see Diskretn. Anal. Issled. Oper., Ser. 1 10, 31–69 (2003; Zbl 1032.05006).]
Summary: Let \(S\) be a finite set that consists of \(n\) different elements and let \(k\) be a natural number, \(1\leq k\leq n\). 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 nonempty. 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 common component equal to 1. In the paper, an asymptotics is given for the size of a special subset of 2-undivided Boolean functions of \(n\) variables (2-undivided families of subsets of an \(n\)-element set) as \(n\to\infty\) and \(n\) is odd. The fact that almost all 2-undivided Boolean functions of \(n\) variables belong to the special class will be proven in the next paper.


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


Zbl 1032.05006