Partitioning the Boolean lattice into a minimal number of chains of relatively uniform size
type: Item
instance of: scholarly article
title: Partitioning the Boolean lattice into a minimal number of chains of relatively uniform size
zbMATH Open document ID: 1031.06003
DOI: 10.1016/S0195-6698(02)00133-6
author: Tim Hsu
author: Mark J. Logan
author: Shahriar Shahriari
author: Christopher Towse
published in: European Journal of Combinatorics
publication date: 2003-04-02T00:00:00Z
review text: It is shown that for a given \(c\) and sufficiently large \(n\) there exist functions \(e(n)\sim\sqrt{n}/2\) and \(f(n)\sim c\sqrt{n\log n}\) such that the Boolean lattice can be partitioned into \({n\choose n/2}\) chains whose lengths are between \(e(n)\) and \(f(n)\). This result is a step forward towards the question of Füredi, who asked whether or not the Boolean lattice can be partitioned into \({n\choose n/2}\) chains whose lengths are either \(a\) or \(a+1\) for some \(a\). The result is also an extension of the previous result of the present authors, where the chain lengths satisfy only the low bound \(e(n)\).
reviewed by: Sergej L. Bezrukov
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 1891300
zbMATH Keywords: Boolean lattice
zbMATH Keywords: chain decompositions
zbMATH Keywords: Füredi's problem
zbMATH Keywords: normalized matching property
zbMATH Keywords: LYM property
MaRDI profile type: Publication
cites work: Q3741626
cites work: Q5805073
cites work: Q4338928
cites work: Problems on chain partitions
cites work: Matchings, cutsets, and chain partitions in graded posets
cites work: Partitioning the Boolean lattice into chains of large minimum size
description: scientific article; zbMATH DE number 1891300