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.
Reviewer: F.I.Solov’eva (Novosibirsk)
MSC:
05B40 | Combinatorial aspects of packing and covering |
06E30 | Boolean functions |
06A07 | Combinatorics of partially ordered sets |