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 28 from
Section 1.6. For
\(0\leq i\leq (r-1)n\text{,}\) let
\begin{equation*}
L_{r,i}:=\left\{(x_1,\dots,x_n)\in \mathcal{P}_r^n: \sum_{j=1}^n x_j=i\right\}.
\end{equation*}
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{.}\)
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{.}\)
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).
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)
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*}
for all \(A,B\in\mathcal{F}\text{.}\)
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[0,\infty)\) 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?
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.
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{.}\)
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.
