\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 6}{Due May 2, 2025}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\F}{\mathcal{F}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\two}{\underline{2}}
\newcommand{\twosupn}{\two^n}
%\newcommand{\RR}{\mathbb{R}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}
\item {}[12.1.19] \emph{Another proof of Dilworth's Theorem.}  The poset on the right below arises from that on the left by deleting the central covering pair.  All other comparabilities remain.
\begin{center}
~\hfill
\begin{tikzpicture}[scale=0.5]
	\foreach \n/\x/\y in {X/-1/0, Y/2/1, A/1/-1, B/1/0, C/0/1, D/0/2}
	{{
		\node[vertex] at (\x, \y) (\n) {} ;
	}}
	
	\draw (A) -- (B) -- (C) -- (D) (X) -- (C) (B) -- (Y) ;
\end{tikzpicture}
\hfill
\begin{tikzpicture}[scale=0.5]
	\foreach \n/\x/\y in {X/-1/0, Y/2/1, A/1/-1, B/1/0, C/0/1, D/0/2}
	{{
		\node[vertex] at (\x, \y) (\n) {} ;
	}}

	\draw (A) -- (B) (C) -- (D) (X) -- (C) (B) -- (Y) ;
	\draw (A) -- (C) (B) -- (D) ;
\end{tikzpicture}
\hfill ~
\end{center}
\begin{enumerate}
	\item Suppose that $x$ covers $y$ and $z$ in $P$.  Let $Q$ and $R$ be the posets obtained by deleting $(y,x)$ and $(z,x)$, respectively, from the set of relations in $P$.  Prove that $\min\{w(Q),w(R)\} = w(P)$.  (Hint: take maximum antichains in $Q$ and $R$, and consider the maximal elements and minimal elements in the union of these antichains as a subposet of $P$.)
	\item Use part (a) to prove Dilworth's Theorem.  (Harzheim [1983])
\end{enumerate}


\item {}[12.2.11] A \emph{semiantichain} in $P\times Q$ is a subset having $(u,v) < (u',v')$ for two elements of $S$ only if $u<u'$ and $v<v'$.  A product poset has the \emph{$2$-part Sperner property} when some single rank is a largest semiantichain.
\begin{enumerate}
	\item Prove that the product of two symmetric chain orders is $2$-part Sperner.
	\item Use part (a) to show that for any $2$-coloring of the elements of $[n]$, the largest subposet of $\twosupn$ having no related pair with monochromatic difference consists of a largest rank.
\end{enumerate}

\item {}[12.2.16] A \emph{universal subset list} on an alphabet $S$ is a word having every subset of $S$ as a consecutive substring.  For example, $1231$ is such a list on $[3]$.  Listing all $2^n$ subsets consecutively yields a universal subset list on $[n]$ with length $n2^{n-1}$, since the average size is $n/2$.
\begin{enumerate}
	\item For even $n$, use symmetric chain decompositions of two copies of $\two^{n/2}$ to construct a universal subset list on $[n]$ with length asymptotically at most $(4/\pi)2^n$.  (Hint: Use Stirling's formula to approximate $\binom{k}{\floor{k/2}}$.)
	\item Prove that a universal subset list on $[n]$ has size at least $c 2^n/\sqrt{n}$ for some positive constant $c$.
\end{enumerate}
Comment: using that the average size of a chain in a symmetric chain decomposition of $\two^k$ is $2^k/\binom{k}{\floor{k/2}}$ or $O(\sqrt{k})$, and hence the average size of a top element is $k/2 + O(\sqrt{k})$, improves the bound in part (a) by a factor of two.

\item {}[12.2.21] Two chain partitions are \emph{orthogonal} if no two elements appear in the same chain in both partitions.
\begin{enumerate}
	\item Define $\D$ from the bracketing decomposition $\C$ of $\twosupn$ by changing each set to its complement and reversing the order of chains.  Prove that for $n\ge 4$, a slight change in $\D$ yields a chain partition orthogonal to $\C$.
	\item Construct two orthogonal Dilworth decompositions of for each of $\two^2$ and $\two^3$, and construct three pairwise orthogonal Dilworth decompositions of $\two^4$.
	\item Prove that $\twosupn$ has at most $\ceil{(n+1)/2}$ pairwise orthogonal Dilworth decompositions.
\end{enumerate}

\item {} [12.2.17] \emph{The Littlewood-Offord Problem.}  Let $a_1,\ldots,a_n$ be vectors in $\R^d$, each having length at least $1$.  Let $R_1,\ldots,R_k$ be regions in $\R^d$, each having diameter less than $1$ (i.e. contained in the interior of a sphere of diameter $1$), and let $R$ be their union.  Let $d_k(n) = \sum_{i=r}^s \binom{n}{i}$, where $r=\floor{(n-k+1)/2}$ and $s=\floor{(n+k-1)/2}$ (this counts the $k$ middle ranks in $\twosupn$).
\begin{enumerate}
	\item Prove that $d_k(n) = d_{k+1}(n-1)+d_{k-1}(n-1)$.
	\item Prove that the number of $\{0,1\}$-vectors $x$ such that $\sum x_ia_i \in R$ is at most $d_k(n)$.  (Hint: to apply part (a) in an inductive proof, one must group these vectors $x$ into sets corresponding to two problems of the same type with $n-1$ vectors, one having $k+1$ regions and one having $k-1$ regions.)
\end{enumerate}
 
\item {}[12.2.27] Let $\Pi_n$ denote the poset of partitions of $[n]$, with $\sigma \le \tau$ if $\sigma$ is a union of partitions of the blocks of $\tau$.  Partitions with $k$ blocks have rank $n-k$, so $N_{n-k}(\Pi_n)=S(n,k)$ (the Sterling number).  For even $n$, let $A$ be the set of partitions of $[n]$ into two blocks of size $n/2$.  Use $A$ and its shadow to prove that $\Pi_n$ with $n$ even is not an LYM order when $n\ge 20$.  (Comment: Rota asked whether $\Pi_n$ always has the Sperner property; Canfield [1978] showed that it doesn't.  Shearer [1979] and Jichang--Kleitman [1984] reduced the least $n$ such that $\Pi_n$ is not Sperner to $4\times 10^9$ and then to $3.4\times 10^6$.

\end{enumerate}
\end{document}
