×

On minimal covering of the Boolean cube by centered antichains. (Russian) Zbl 0931.05020

A set of vectors of the Boolean \(n\)-cube \(B^n\) is called centered if all vectors of the set have at least one common unit coordinate or the set consists of a single zero vector. Two vectors \(\alpha\) and \(\beta\) in \(B^n\) are incomparable if neither \(\alpha \leq \beta\) nor \(\beta \leq \alpha\), where \(\alpha \leq \beta\) means \(\alpha _{i}\leq \beta _{i}\), \(\alpha =(\alpha_{1},\ldots,\alpha_{n}), \beta=(\beta_{1},\ldots,\beta_{n})\). A set of pairwise incomparable vectors of \(B^n\) is called an antichain. It is established that, for every \(n\geq 1\), the minimal number of centered antichains covering the Boolean \(n\)-cube is equal to \(n\lfloor \log_{2}n \rfloor + 2(n - 2^{\lfloor \log_{2}n \rfloor}) + 2\). The bound is exact. For every \(n\), a minimal covering is presented.

MSC:

05B40 Combinatorial aspects of packing and covering
06E30 Boolean functions
06A07 Combinatorics of partially ordered sets