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

Korshunov, A. D.

Diskretn. Anal. Issled. Oper., Ser. 1 12, No. 1, 12-70 (2005).

[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.

MSC:

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

Keywords:

two-valued function; asymptotic expression; Post class

Citations:

Zbl 1032.05006