## Section 2.5 Exercises

- List all of the antichains in \(2^{[n]}\) for each \(n\in\{1,2,3\}\text{.}\)
- In the proof of Lemma 2.1.17, show that \(\mathcal{C}_m'\) and \(\mathcal{C}_m''\) are symmetric chains in \(2^{[n]}\) and that every subset of \([n]\) belongs to exactly one of the collections \(\mathcal{C}_1',\dots,\mathcal{C}_N',\mathcal{C}_1'',\dots,\mathcal{C}_N''\text{.}\)
- In the proof of Lemma 2.1.17, it appears that the number of chains used in the partitioning of \(2^{[n]}\) is exactly twice as many as were used in the partitioning of \(2^{[n-1]}\text{.}\) By induction, this suggests that \(2^{[n]}\) can be covered by exactly \(2^{n-1}\) symmetric chains. However, from the proof of Theorem 2.1.6, we know that the number of chains in any symmetric chain decomposition is exactly \(\binom{n}{\lfloor n/2\rfloor}\text{,}\) which is certainly not equal to \(2^{n-1}\) in general. Explain why the number of chains in the decomposition of \(2^{[n]}\) found in the proof of Lemma 2.1.17 is sometimes less than twice the number of chains in the decomposition of \(2^{[n-1]}\text{.}\)
- Let \(\mathcal{C}_1,\dots,\mathcal{C}_N\) be a symmetric chain decomposition of \(2^{[n]}\) where \(N=\binom{n}{\lfloor n/2\rfloor}\text{.}\) For \(0\leq k\leq n/2\text{,}\) how many chains in the decomposition have length exactly \(n+1-2k\text{?}\)
- For \(r\geq2\) and \(n\geq1\text{,}\) let \(\mathcal{P}_r^n\) be the partially ordered sets defined in Exercise 26 from Section 1.6. For \(0\leq k\leq (r-1)n\text{,}\) let\begin{equation*} L_{r,k}:=\left\{(x_1,\dots,x_n)\in \mathcal{P}_r^n: \sum_{i=1}^n x_i=k\right\} \end{equation*}A
*chain*in \(\mathcal{P}_r^n\) is a set \(C\subseteq \mathcal{P}_r^n\) such that \(x\preceq y\) or \(y\preceq x\) for all \(x,y\in C\text{.}\) A*symmetric chain*is a chain \(C\) such that there exists \(0\leq k\leq (r-1)n/2\) such that \(C\) contains an element of \(L_i\) for all \(k\leq i\leq (r-1)n-k\text{.}\) Find and describe a partition of \(\mathcal{P}_r^k\) into symmetric chains. You don’t need to prove that it satisfies all of the properties. - Give an example of an antichain in \(\mathcal{P}_r^n\) of maximum size, where an
*antichain*in \(\mathcal{P}_r^n\) is a set \(A\subseteq \mathcal{P}_r^n\) such that \(x\npreceq y\) for any distinct \(x,y\in A\text{.}\) How do you know that there does not exist a larger antichain?

- For \(r\geq3\) and \(0\leq k\leq (r-1)n\text{,}\) let \(\mathcal{P}_r^n\) and \(L_{r,k}\) be as in Exercise 5 from this section. In this exercise, we focus on the case \(r=3\text{.}\) Prove that, for every \(1\leq k\leq 2n\text{,}\) there exists a function \(f_k:L_{3,k}\times L_{3,k-1}\to [0,\infty)\) satisfying the following two properties:\begin{equation*} \sum_{y\in L_{3,k-1}}f_k(x,y) = |L_{3,k-1}|\text{ for all } x\in L_{3,k}\text{,} \end{equation*}\begin{equation*} \sum_{x\in L_{k}}f_k(x,y) = |L_{3,k}|\text{ for all } y\in L_{3,k-1}\text{.} \end{equation*}
- A chain \(C\) in \(\mathcal{P}_r^n\) is
*maximal*if it contains an element of \(L_{r,k}\) for all \(0\leq k\leq (r-1)n\text{.}\) Prove that there exists a probability distribution on the set of maximal chains in \(\mathcal{P}_3^n\) with the property that, if \(C\) is chosen randomly according to this distribution, then, for all \(0\leq k\leq 2n\) and \(x\in L_{3,k}\text{,}\) it holds that \(\mathbb{P}(x\in C)=\frac{1}{|L_{3,k}|}\text{.}\) - State and prove a version of the LYM Inequality for \(\mathcal{P}_3^n\text{.}\)
- State and prove a version of the Local LYM Inequality for \(\mathcal{P}_3^n\text{.}\)

- Let \(0\leq r\leq n/2\) and let \(\mathcal{F}\subseteq 2^{[n]}\) be an intersecting antichain such that every set in \(\mathcal{F}\) has cardinality at most \(r\text{.}\) Prove that \(|\mathcal{F}|\leq \binom{n-1}{r-1}\text{.}\)
- Let \(A\) and \(B\) be disjoint finite sets. Consider a random permutation of \(A\cup B\text{.}\) What is the probability that all of the elements of \(A\) come before all of the elements of \(B\) in the permutation?
- Let \((A_1,B_1),\dots,(A_m,B_m)\) be a sequence of pairs of finite sets such that \(A_i\cap B_i=\emptyset\) and \(A_i\cap B_j\neq \emptyset\) whenever \(i\neq j\text{.}\) Prove that\begin{equation*} \sum_{i=1}^m\frac{1}{\binom{|A_i|+|B_i|}{|A_i|}}\leq 1\text{.} \end{equation*}
- Use the statement in the previous part of the question to prove the LYM Inequality.

- Let \(k\) be a fixed positive integer and let \(n\) be an integer which we view as tending to infinity. Let \(\mathcal{F}\subseteq 2^{[n]}\) be an antichain containing at least one set of cardinality at most \(k\text{,}\) at least one of cardinality at least \(n-k\) and none of cardinality strictly between \(k\) and \(n-k\text{.}\) Prove that \(|\mathcal{F}|=O(n^{k-1})\text{.}\)
- Say that \(\mathcal{F}\subseteq \binom{[n]}{k}\) is
*intersection-free*if there does not exist distinct \(A,B,C \in \mathcal{F}\) such that \(A\cap B\subseteq C\text{.}\) Prove that if \(\mathcal{F}\subseteq \binom{[n]}{k}\) is intersection-free, then \(|\mathcal{F}|\leq 1+\binom{k}{\lfloor k/2\rfloor}\text{.}\) - Let \(\mathcal{F}\subseteq 2^{[n]}\) such that \(|\mathcal{F}|=m\) and, for all distinct \(i,j\in [n]\text{,}\) there exists \(A\in\mathcal{F}\) containing \(i\) but not \(j\text{.}\) Prove that \(n\leq \binom{m}{\lfloor m/2\rfloor}\text{.}\)
- For each set \(A\subseteq [n]\text{,}\) define \(\mu(A):=(-1)^{|A|}\text{.}\) Say that a collection \(\mathcal{F}\subseteq 2^{[n]}\) is
*convex*if for any sets \(A,B,C\subseteq [n]\) such that \(A\subseteq C\subseteq B\text{,}\) if \(A,B\in\mathcal{F}\text{,}\) then \(C\in\mathcal{F}\text{.}\) Prove that, if \(\mathcal{F}\) is convex, then\begin{equation*} \left|\sum_{A\in\mathcal{F}}\mu(A)\right|\leq \binom{n}{\lfloor n/2\rfloor}\text{.} \end{equation*} - Let \(f(n)\) be the number of antichains in \(2^{[n]}\text{.}\)
- Prove that \(f(n)\geq 2^{\binom{n}{\lfloor n/2\rfloor}}\text{.}\)
- Prove that, for every \(\varepsilon>0\text{,}\) there exists \(N(\varepsilon)\in \mathbb{N}\) such that if \(n\geq N(\varepsilon)\text{,}\) then \(f(n)\leq 2^{\varepsilon 2^n}\text{.}\)
*Hint 1:*You may want to use \(\binom{n}{k}\leq \left(\frac{en}{k}\right)^k\text{.}\)*Hint 2:*Look up Stirling’s Approximation and apply it.

- Let \(k\leq n/2\) and suppose that \(\mathcal{A}\) is an antichain in \(2^{[n]}\) in which every element of \(\mathcal{A}\) has cardinality at most \(k\text{.}\) Prove that \(|\mathcal{A}|\leq \binom{n}{k}\text{.}\)
- For \(n\geq1\text{,}\) a
*rising antichain*is a collection \(\mathcal{A}\subseteq 2^{[n]}\) such that \(\mathcal{A}\) is an antichain and no two elements of \(\mathcal{A}\) have the same cardinality.- Show that, for every \(n\geq1\text{,}\) every rising antichain in \(2^{[n]}\) has cardinality at most \(n+1\) (Easy).
- Determine, for every \(n\geq1\text{,}\) the maximum possible size of a rising antichain in \(2^{[n]}\text{.}\)

- Prove that, if \(\mathcal{F}\subseteq 2^{[n]}\) does not contain a chain of cardinality \(k\text{,}\) then there exists a partition of \(\mathcal{F}\) into at most \(k-1\) antichains. (This is known as
*Mirsky’s Theorem*) - Using Exercise 16.a and the LYM Inequality, prove Corollary 2.2.4.

- Use the Local LYM Inequality to prove that, if \(\mathcal{F}\subseteq 2^{[n]}\) is a downset, then the average cardinality of an element in \(\mathcal{F}\) is at most \(n/2\text{.}\)
- Use the Local LYM Inequality to prove the LYM Inequality.
- Let \(w:\{0,1,\dots,n\}\to\mathbb{R}\) be any
*weight function*and, for \(\mathcal{A}\subseteq 2^{[n]}\text{,}\) let\begin{equation*} w(\mathcal{A}):=\sum_{A\in\mathcal{A}}w(|A|)\text{.} \end{equation*}Prove that, for any antichain \(\mathcal{A}\subseteq 2^{[n]}\text{,}\)\begin{equation*} w(\mathcal{A})\leq \max_{0\leq k\leq n}\binom{n}{k}w(k)\text{.} \end{equation*} - Suppose that \(\mathcal{F}\subseteq 2^{[n]}\) has the property that, for any \(A\in \mathcal{F}\text{,}\) there does not exist a pair of sets \(B,C\in\mathcal{F}\) such that \(B\subsetneq A\subsetneq C\text{.}\) Prove that \(|\mathcal{F}|\) is at most \(2\binom{n}{\left\lfloor n/2\right\rfloor}\text{.}\) For which values of \(n\) is this tight?
- Say that an antichain \(\mathcal{A}\subseteq 2^{[n]}\) is
*complementary*if for every \(A\in \mathcal{A}\text{,}\) the set \([n]\setminus A\) is also in \(\mathcal{A}\text{.}\) Show that the maximum cardinality of a complementary antichain is \(2\binom{n-1}{\lceil n/2\rceil}\) for every \(n\geq1\text{.}\) - For each \(k\) such that \(0\leq k \leq \binom{n}{\lfloor (n+2)/2\rfloor}\text{,}\) give an example of a collection \(\mathcal{A}\subseteq 2^{[n]}\) with \(|\mathcal{A}|=\binom{n}{\lfloor n/2\rfloor} + k\) such that the number of pairs \(A,B\in \mathcal{A}\) satisfying \(A\subsetneq B\) is equal to \(k \left\lfloor \frac{n+2}{2}\right\rfloor\text{.}\)
- Say that a collection \(\mathcal{F}\subseteq 2^{[n]}\) is
*\(k\)-chain saturated*if it does not contain a \(k\)-chain but, for any \(A\in 2^{[n]}\setminus \mathcal{F}\text{,}\) the collection \(\mathcal{F}\cup \{A\}\) does contain a \(k\)-chain. Prove that, if \(n\geq k-2\text{,}\) then there exists a \(k\)-chain saturated family \(\mathcal{F}\subseteq 2^{[n]}\) such that \(|\mathcal{F}|=2^{k-2}\text{.}\) - Write out \(\binom{[5]}{3}\) ordered by colex.
- What are the \(99\)th, \(100\)th and \(101\)st elements in the colex order on \(\binom{\mathbb{N}}{4}\text{?}\) What about lex order?
- Let \(\mathcal{A}\subseteq\binom{[9]}{3}\) with \(|\mathcal{A}|=28\text{.}\) How small can \(|\partial\mathcal{A}|\) be?
- The
*upper shadow*of a family \(\mathcal{F}\subseteq \binom{[n]}{k}\) is\begin{equation*} \partial^+\mathcal{F}:=\left\{A\subseteq [n]: |A|=k+1\text{ and } A\supseteq F\text{ for some } F\in\mathcal{F}\right\}\text{.} \end{equation*}State and prove a version of the Kruskal–Katona Theorem for the upper shadow. - Give an example of a finite set system \(\mathcal{F}\subseteq \binom{\mathbb{N}}{2}\) which is not isomorphic to the collection \(\mathcal{I}\) of the first \(|\mathcal{F}|\) sets of \(\binom{\mathbb{N}}{2}\) under colex order such that \(|\partial\mathcal{F}|=|\partial\mathcal{I}|\text{.}\)