You have now partitioned these subsets into chains with sizes 4, 2 & 2. But could you partition the 1024 subsets of {1, ¼,10} into 16 chains of size 5 and 236 chains of size 4?

Let [n] = {1,¼,n} and let 2^[n] denote the poset of subsets of [n] ordered by inclusion. A collection of subsets A₀ Ì ¼ Ì A_k of [n] is called a chain of size k+1 in 2^[n]. In this talk we discuss a construction that partitions 2^[n] into a collection of chains such that the size of the shortest chain is approximately [ 1/2] Ön and the size of the longest chain is roughly Ö{nlogn}.

This result is motivated by conjectures of Griggs and Füredi on chain partitions of 2^[n]. Let m = (m₁ ³ ... ³ m_l) be a partition of 2ⁿ into positive parts. In 1988, Griggs made a conjecture that gives a necessary and sufficient condition for the existence of a partition of 2^[n] into chains of sizes m₁,...,m_l. Earlier, Füredi had considered a special case of the Griggs conjecture and asked if 2^[n] can be partitioned into (n || (ën/2 û)) chains such that the size of every chain is one of two consecutive integers. In such a (hypothetical) construction, the size of the shortest chain will be approximately Ö{p/2}Ön. In contrast, our construction gives a chain partition with the correct number of chains, and with minimal chain size roughly [ 1/2]Ön.