Below are diagrams for \(\mbf{2}^{4}\) and \(\mbf{2}^{5}\text{.}\) (Without any of the points labeled with corresponding sets.) In the space provided, draw \(\mbf{2}^{1}\text{,}\)\(\mbf{2}^{2}\text{,}\) and \(\mbf{2}^{3}\text{.}\) (Label the sets, too. You can just write “\(12\)” instead of “\(\{1,2\}\)”.) Label a few of the points in the diagrams provided for \(\mbf{2}^{4}\) and \(\mbf{2}^{5}\) to make sure you understand how to do it.
The unlabeled lattice of subsets of \(\set{1,2,3,4}\text{.}\) The points are displayed in five layers. The bottom layer has a single point. The second layer from the bottom contains four points. The third layer from the bottom contains six points. The fourth layer from the bottom contains four points. The top layer contains a single point.
The unlabeled lattice of subsets of \(\set{1,2,3,4,5}\text{.}\) The points are displayed in five layers. The bottom layer has a single point. The second layer from the bottom contains five points. The third and fourth layers from the bottom each contain 10 points. The fifth layer from the bottom contains five points. The top layer contains a single point.
It looks like the width of \(\mbf{2}^{n}\) is the largest binomial coefficient \(C(n,k)\text{,}\) and it appears this happens when \(k\) is around \(n/2\text{.}\)
To be able to verify our conjecture, let’s think about a seemingly unrelated question: counting maximal chains in \(\mbf{2}^{n}\text{.}\) How many maximal chains are there in \(\mbf{2}^{n}\text{?}\)
Here we have \(3!\) ways to add the elements \(1,3,4\) and then \(2!\) ways to add \(2\) and \(5\text{.}\) Thus, there are \(3!2!\) maximal chains through this set.
Here we have \(3!\) ways to add the elements \(1,3,4\) and then \((n-3)!\) ways to add the remaining \(n-3\) elements. Thus, there are \(3!(n-3)!\) maximal chains through this set.
Here we have \(k!\) ways to add the \(k\) elements that are in the set and then \((n-k)!\) ways to add the remaining \(n-k\) elements. Thus, there are \(k!(n-k)!\) maximal chains through this set.
Fix an antichain \(\mc{A}=\{S_{1},S_{2},\dots,S_{t}\}\) with \(|S_{i}|=s_{i}\text{.}\) How many maximal chains pass through some set in \(\mc{A}\text{?}\) Express your answer as a summation.
Can a maximal chain \(\mc{C}\) pass through two different sets \(S_{i},S_{j}\in\mc{A}\) with \(i\neq j\text{?}\) What does this tell you that the sum from the previous question must be less than or equal to?
As a result of the previous step, you should have an inequality with a summation on the small side and a factorial on the big side. Divide the factorial over (and into the summation) so that you have a summation less than or equal to \(1\text{.}\) Rewrite your summation so that it is a sum of reciprocals of binomial coefficients.
We will establish a formula for \(w=\width(\mbf{2}^{n})\) by showing that \(w\) is bounded above and below by the same quantity. Explain why \(w\geq C(n,k)\) for each possible value of \(k\text{.}\) What is the largest lower bound that you get for \(w\) in this way?
Since the \(k\)-element subsets of \([n]\) each form an antichain and there are \(C(n,k)\)\(k\)-element subsets of \([n]\text{,}\) we know that \(w\geq C(n,k)\) for all \(k\text{.}\) The largest possible bound is thus the largest binomial coefficient, which happens when \(k=\lceil n/2\rceil\text{.}\) (Because of the symmetry of binomial coefficients, when \(n\) is odd, we have the same value if \(k = \lfloor n/2\rfloor\text{.}\))
Let us now return to the inequality involving a summation and \(1\) that you obtained earlier. To find an upper bound for \(w\text{,}\) we assume that \(\mc{A}\) is a maximum antichain so that \(t = w=\width(\mbf{2}^{n})\text{.}\) Also assume that \(s_{i} = \lceil n/2\rceil\) for all \(i\text{.}\) We can do this since the inequality is true for any antichain. Explain how this lets you eliminate the summation from your inequality and then give an upper bound for \(\width(\mbf{2}^{n})\text{.}\)
which implies \(w\leq \binom{n}{\lceil n/2\rceil}\text{.}\) We now have matching upper and lower bounds for the width, since we know there is an antichain with \(\binom{n}{\lceil n/2\rceil}\) elements. Thus, this is the width.
