×

zbMATH — the first resource for mathematics

The number of \(k\)-undivided families of subsets of an \(n\)-element set (\(k\)-undivided Boolean functions of \(n\)-variables). III. The case when \(n\) is arbitrary and \(k\geq 3\). (Russian) Zbl 1249.05015
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 asymptotics is given for the number of \(k\)-undivided Boolean functions of \(n\) variables as \(n \to \infty\) and \(k\geq 3\) is fixed.
For Part I see [ibid., Ser. 1 10, No. 4, 31–69 (2003; Zbl 1032.05006)].
For Part II see [ibid., Ser. 1 12, No. 1, 12–70 (2005; Zbl 1077.05007)].

MSC:
05A16 Asymptotic enumeration
03E05 Other combinatorial set theory
06E30 Boolean functions
PDF BibTeX XML Cite