×

Lower bounds for a number of \((k,r)\)-undivided families of subsets of an \(n\)-element set (\((k,r)\)-undivided Boolean functions). (Russian) Zbl 1228.05016

A family of subsets \({\mathcal F}= \{S_1,\dots, S_n\}\) of an \(n\)-set \(S\) is called \((k, r)\)-nonseparated (where \(k\geq 2\), \(1\leq r\leq n\)) if the intersection of any \(v\) members of \({\mathcal F}\), \(v\leq k\), contains at least elements. The number of \((k,r)\)-nonseparated families of subsets of an \(n\)-set equals the number of \((k,r)\)-nonseparated Boolean functions of \(n\) variables. Here a Boolean function \(f(x_1,\dots, x_n)\) is said to be \((k,r)\)-nonseparated if for any \(v\) vectors, \(v\leq k\), for which \(f(x_1,\dots, x_n)= 1\), there are at least \(r\) common components equal to \(1\). Lower bounds are given for the number of \((k,r)\)-nonseparated Boolean functions of \(n\) variables for arbitrary fixed \(k \geq 3\), \(r \geq 1\) and \(n \to \infty\).

MSC:

05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite