Partitioning the Boolean lattice into a minimal number of chains of relatively uniform size

DOI10.1016/S0195-6698(02)00133-6MaRDI QIDQ1867287zbMATH OpenFDO

Authors Tim Hsu, Mark J. Logan, Shahriar Shahriari, Christopher Towse

Publication date 2 April 2003

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0195-6698(02)00133-6

zbMATH Keywords

Boolean latticechain decompositionsFüredi's problemLYM propertynormalized matching property

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

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)\).

Recommendations

• Partitioning the Boolean lattice into chains of large minimum size
• scientific article; zbMATH DE number 1934409
• Improved bounds on the partitioning of the Boolean lattice into chains of equal size.
• On a conjecture of Füredi.
• Proof of a conjecture on partitions of a Boolean lattice

Cites work

• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 3065933 (Why is no real title available?)
• Matchings, cutsets, and chain partitions in graded posets
• Partitioning the Boolean lattice into chains of large minimum size
• Problems on chain partitions

Cited in

(14)

• Methods for nesting rank 3 normalized matching rank-unimodal posets
• Partitioning Boolean lattices into chains of subsets
• Partitioning the Boolean lattice into chains of large minimum size
• Partitioning the Boolean lattice into copies of a poset
• On a conjecture of Füredi.
• Decompositions of the Boolean lattice into rank-symmetric chains.
• scientific article; zbMATH DE number 3952833 (Why is no real title available?)
• scientific article; zbMATH DE number 3972869 (Why is no real title available?)
• scientific article; zbMATH DE number 1934409 (Why is no real title available?)
• scientific article; zbMATH DE number 749275 (Why is no real title available?)
• Improved bounds on the partitioning of the Boolean lattice into chains of equal size.
• Uniform chain decompositions and applications
• On nested chain decompositions of normalized matching posets of rank 3
• The generalized Füredi conjecture holds for finite linear lattices

This page was built for publication: Partitioning the Boolean lattice into a minimal number of chains of relatively uniform size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1867287)