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ย 31 from Sectionย 1.6. For \(0\leq i\leq (r-1)n\text{,}\) let
We call this the \(i\)th level of \(\mathcal{P}_r^n\text{.}\) For example, \(L_{r,0}=\{(0,0,\dots,0)\}\) and \(L_{r,(r-1)n}=\{(r-1,r-1,\dots,r-1)\}\text{.}\) 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_{r,i}\) for all \(k\leq i\leq (r-1)n-k\text{.}\) Find and describe a partition of \(\mathcal{P}_r^n\) into symmetric chains. As long as your construction is correct, 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{.}\)
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
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
Show that the bound in part (a) is best possible: for every \(m\geq1\text{,}\) construct a family \(\mathcal{F}\subseteq 2^{[n]}\) with \(|\mathcal{F}|=m\) and
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
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{.}\)
Let \(V\) be a normed vector space and let \(z_1,\dots,z_n\in V\) such that \(\|z_i\|\geq1\) for all \(1\leq i\leq n\text{.}\) Let \(k\leq n/2\text{.}\) Prove that, if \(\mathcal{F}\subseteq 2^{[n]}\) such that \(|A|\leq k\) for all \(A\in\mathcal{F}\) and \(\|z_A-z_B\|<1\) for any \(A,B\in\mathcal{F}\text{,}\) then \(|\mathcal{F}|\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).
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)
Determine the largest cardinality of a collection \(\mathcal{F}\subseteq 2^{[n]}\) for which there exists real numbers \(z_1,\dots,z_n\) such that \(|z_i|\geq 1\) for all \(1\leq i\leq n\) and
\begin{equation*}
\left|z_A-z_B\right|\lt m
\end{equation*}
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{.}\)
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{.}\)
Find the 137th, 138th and 139th elements in the colex order on \(\binom{\mathbb{N}}{4}\text{.}\) Then find the 137th, 138th and 139th elements in the lex order.
Give an example to show that the bound on the shadow given by the KruskalโKatona Theorem can be strictly better than the one given by the Local LYM Inequality.
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{.}\)
Note: Two set systems \(\mathcal{F},\mathcal{G}\subseteq 2^{\mathbb{N}}\) are isomorphic if there exists a bijection \(\varphi:\mathbb{N}\to\mathbb{N}\) such that, for every \(A\subseteq\mathbb{N}\text{,}\) we have \(\varphi(A)\in\mathcal{G}\) if and only if \(A\in\mathcal{F}\text{.}\) In other words, they are isomorphic if they are โthe sameโ up to re-labelling the natural numbers.
