## 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 T_{j} (n) with the normalized matching property and log-concave rank numbers. We then use our results on T_{j}(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 language | English (US) |
---|---|

Pages (from-to) | 62-84 |

Number of pages | 23 |

Journal | Journal of Combinatorial Theory. Series A |

Volume | 97 |

Issue number | 1 |

DOIs | |

State | Published - 2002 |

Externally published | Yes |

## Keywords

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