Partitioning the Boolean lattice into chains of large minimum size

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

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Let 2[n] denote the Boolean lattice of order n, that is, the poset of subsets of (1,…, n) ordered by inclusion. Recall that 2[n] may be partitioned into what we call the canonical symmetric chain decomposition (due to de Bruijn, Tengbergen, and Kruyswijk), or CSCD. Motivated by a question of Füredi, we show that there exists a function d(n) ∼ 1/2 n such that for any n ≥ 0, 2[n] may be partitioned into (n⌊n/2⌋) chains of size at least d(n). (For comparison, a positive answer to Füredi's question would imply that the same result holds for some d(n) ∼ π/2 n.) More precisely, we first show that for 0 ≤ j ≤ n, the union of the lowest j+1 elements from each of the chains in the CSCD of 2[n] forms a poset Tj (n) with the normalized matching property and log-concave rank numbers. We then use our results on Tj(n) to show that the nodes in the CSCD chains of size less than 2d(n) may be repartitioned into chains of large minimum size, as desired.

Original languageEnglish (US)
Pages (from-to)62-84
Number of pages23
JournalJournal of Combinatorial Theory. Series A
Volume97
Issue number1
DOIs
StatePublished - 2002
Externally publishedYes

Keywords

  • Boolean lattice
  • Chain decompositions
  • Füredi's problem
  • Griggs' conjecture
  • Normalized matching property

Fingerprint Dive into the research topics of 'Partitioning the Boolean lattice into chains of large minimum size'. Together they form a unique fingerprint.

Cite this