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_{0} Ì ¼ Ì 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_{1} ³ ... ³ m_{l}) be a partition of 2^{n} 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_{1},...,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.
