Partitioning Boolean lattices into antichains
type: Item
instance of: scholarly article
title: Partitioning Boolean lattices into antichains
zbMATH Open document ID: 1020.06002
DOI: 10.1016/S0012-365X(02)00448-X
author: Zbigniew Lonc
author: Muktar E. Elzobi
published in: Discrete Mathematics
publication date: 2003-03-16T00:00:00Z
review text: Given a finite poset \(P\) and a family \(F\) of finite posets, then \(\text{cov} (P;F)=m\) if this is the smallest integer such that \(P\) is covered by \(m\) not necessarily distinct elements of \(F\). If \(R\) is a set of restrictions, then \(\text{cov} (P;F;R)=m\) means that the restriction conditions \(R\) are also met. Thus, \(\text{cov} (P;F)\leq\text{cov} (P;F;R)\). Estimating \(\text{cov} (P;F;R)\) as closely as possible, if not computing it exactly, leads to numerous problems of interest. Thus, if \(P=B_n\), the Boolean lattice on \(n\) elements, and if \(F=C\) is the family of chains, then requiring the chains to have equal size \(c\) except for one of size \(c-1\), and the cover to be a partition, then the problem of existence (i.e., \(\text{cov} (P;F;R) <\infty)\) as well as determination becomes one of interest for example. In this paper \(P=B_n'\) is obtained from \(B_n\) by removing 0 and 1 (the maximum and minimal element) and \(F\) is the family of antichains \(A\). In terms of \(R\), \(f(n)\) is defined to be the smallest integer \(t\) such that \(B_n'\) can be partitioned into \(t\) antichains of the same size except for at most one antichain of a smaller size, i.e., \(f(n) =\text{cov}(B_{n;}';A;R)\) is an important special case for which various estimates are improved to \(f(n)\leq bn^2/ \log n\) for a constant \(b\), where \(b\) is almost determined precisely after some careful and complicated sieving of the evidence.
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 1882177
zbMATH Keywords: chain partition
zbMATH Keywords: antichain partition
zbMATH Keywords: Boolean lattice
zbMATH Keywords: cover
reviewed by: J. Neggers
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1882177