\documentclass{amsart}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref,graphicx,color}

\usepackage{a4wide}
\usepackage{soul}

\begin{document}

{\centerline{{\bf{Math 8669 Homework \#1, Spring 2016}}}}
\vskip20pt\noindent
1. Give examples of a finite ranked poset $P$ such that
\vskip2pt\noindent (a) $P$ has the matching property but is not Sperner.
\vskip2pt\noindent (b) $P$ is rank unimodal but not Sperner.
\vskip2pt\noindent (c) $P$ is Sperner but not rank unimodal.
\vskip2pt\noindent (d) $P$ is Sperner and rank unimodal, but 
does not have the matching property. 
\vskip10pt\noindent
2. Prove that if $P$ is Sperner, and $P_{max}$ is a maximum level, 
then the bipartite graphs 
$$
P_{max-1}\cup P_{max}\quad {\text{ and }} P_{max+1}\cup P_{max}
$$
both have complete matchings.
\vskip10pt\noindent
3. Characterize all maximum sized antichains in the Boolean algebra $B_N.$ 
\vskip10pt\noindent
4. What is the Greene-Kleitman partition for the Boolean algebra $B_N?$
\vskip10pt\noindent
5. Can one prove log-concavity of the coefficients of the polynomial 
$\left[\begin{matrix} n\\k\end{matrix} \right]_q$ using reality of the zeros?
\vskip10pt\noindent
6. Prove that $B_n(q)$ is Sperner by verifying that it is 
rank unimodal and has the matching property.
\vskip10pt\noindent
7. Here is another way to verify that $P=B_N(q)$ has the matching property. 
For $0\le k\le N$ let $W_k$ be the $\Bbb{R}$ vector space whose 
basis is given by elements at level $k$ of $B_N(q)$, so 
$dim(W_k)=\left[\begin{matrix} N\\k\end{matrix} \right]_q.$ 
Let $D_k:W_k\to W_{k-1}$ and $U_k:W_k\to W_{k+1},$ $0\le k\le N,$ 
be the natural down and up linear transformations using the edges of $B_N(q).$
\vskip2pt\noindent
(a) What is $D_{k+1}U_k-U_{k-1}D_k$ as a linear transformation on $W_k$?
\vskip2pt\noindent
(b) Show if $2k<n$, the map $U_k$ is 1-1, and find $rank(U_k)$.
\vskip2pt\noindent
(c) Show that the matrix of $U_k$ has a non-singular 
$\left[\begin{matrix} N\\k\end{matrix} \right]_q\times 
\left[\begin{matrix} N\\k\end{matrix} \right]_q$ submatrix, and conclude 
that a complete matching from $P_k$ to $P_{k+1}$ exists.
\vskip10pt\noindent
8. Let $\lambda_n=(n-1,n-2,\cdots,1)$ be the ``staircase" partition. 
Let $P_n=[\varnothing, \lambda_n]$ be the interval in Young's lattice, namely 
the set of all partitions $\mu$ whose Ferrers diagram fit inside $\lambda_n$, under containment of Ferrers diagrams.
\vskip2pt\noindent
(a) Show that $|P_n|= C_n=\frac{1}{n+1}\binom{2n}{n}$, 
the $n^{th}$ Catalan number.
\vskip2pt\noindent
(b) If $R_n(q)$ is the rank generating function of $P_n,$ find a version of 
$C_n=\sum_{k=1}^{n} C_{k-1}C_{n-k}, n\ge 1,$ for $R_n(q).$
\vskip2pt\noindent
(c) Is $P_n$ rank symmetric, rank unimodal*, or Sperner*?
\vskip2pt\noindent
(d) True or False?
$$
\begin{aligned}
\sum_{n=0}^\infty R_n(1/q)q^{\binom{n}{2}} t^n=&
\sum_{n=0}^\infty \frac{(-t)^n q^{n^2}}{(1-q)(1-q^2)\cdots (1-q^n)}/
\sum_{n=0}^\infty \frac{(-t)^n q^{n^2-n}}{(1-q)(1-q^2)\cdots (1-q^n)}\\
=&\ 
\cfrac{1}{1-\cfrac{x}{1-\cfrac{xq}{1-\cfrac{xq^2}{1-\cfrac{xq^3}{\ddots}}}}}
\end{aligned}
$$ 
\vskip10pt\noindent
9. Let $P_n=NC(n)$ the poset of non-crossing set partitions under 
refinement of blocks. Recall that $|P_n|=C_n=\frac{1}{n+1}\binom{2n}{n}$, 
the $n^{th}$ Catalan number, and the $k^{th}$ level numbers are the Narayana numbers
$N_{n,k}=\frac{1}{k+1}\binom{n-1}{k}\binom{n}{k}$, $0\le k\le n-1.$
\vskip2pt\noindent
(a) Verify that $P_n$ is a rank symmetric, rank unimodal poset.
\vskip2pt\noindent
(b) Verify that $P_1,P_2,P_3,P_4$ have symmetric chain decompositions by 
exhibiting one such decomposition on each Hasse diagram.
\vskip2pt\noindent
(c) Prove that $P_n$ has a symmetric chain decomposition.
\vskip10pt\noindent
10. The inequality that we used for log-concavity 
$$
e_k(x_1,\cdots,x_n)^2\ge e_{k-1}(x_1,\cdots,x_n) e_{k+1}(x_1,\cdots,x_n), 
\quad 0\le k\le n-1, \quad x_i> 0
$$
is a weaker version of the {\it{Newton inequalities}}
$$
\left(\frac{e_k(x_1,\cdots,x_n)}{\binom{n}{k}}\right)^2
\ge \left(\frac{e_{k-1}(x_1,\cdots,x_n)}{\binom{n}{k-1}}\right)
\left(\frac{ e_{k+1}(x_1,\cdots,x_n)}{\binom{n}{k+1}}\right), 
\quad 0\le k\le n-1, \quad x_i> 0.
$$
\vskip2pt\noindent
(a) Take $k=1$ and $n=3$ and show that the Newton inequalities do not 
follow from termwise polynomial positivity.
\vskip2pt\noindent
(b) Prove the Newton inequalities by induction on $n$, fixing $k$. 
First verify the case $n=k+1$ by showing a certain quadratic form is 
positive semidefinite. Then do the inductive case by assuming
$0<x_1<x_2<\cdots<x_n$ and letting
$$
P(t)=\prod_{i=1}^n (t+x_i), \quad P'(t)=n\prod_{i=1}^{n-1}(t+x_i')
$$
where $x_i<x_i'<x_{i+1}.$ Use 
$$
(n)e_k(x_1',x_2',\cdots,x_{n-1}')=(n-k)e_k(x_1,\cdots,x_n),
\quad 0\le k\le n-1
$$ 
in the induction.
\vskip10pt\noindent
11. Let $P$ be finite ranked poset and suppose that 
$G\le Aut(P)$. Define a 
poset $P/G$ whose elements are the orbits $O$ of $G$ on $P$, with
order relation $O_1 \le O_2$ iff there exists $x\in O_1$, $y\in O_2$, 
with $x\le y$ in $P$. True or False: If $P$ is Sperner, 
then $P/G$ is Sperner.
\vskip10pt\noindent
12. In this problem you will prove the unimodality of the $q$-binomial coefficient by finding an explicit formula, called the {\it{KOH identity.}} 
\vskip3pt\noindent
First some notation.
For an integer partition $\lambda$, let $|\lambda|$ be the sum of the 
parts of $\lambda.$ Let $\lambda'$ be the conjugate of $\lambda,$ and let 
$m_i(\lambda)$ be the multiplicity of the part $i$ in $\lambda$. For example, if 
$\lambda=544422111$, then $|\lambda|=24,$ $\lambda'=96441$, and $m_4(\lambda)=3.$
Finally, let 
$$
n(\lambda)=\sum_{i} (i-1)\lambda_i=\sum_{j} \binom{\lambda_j'}{2}.
$$

It is
\begin{equation}
\left[\begin{matrix} N+k\\k\end{matrix} \right]_q=
\sum_{\lambda, |\lambda|=k} q^{2n(\lambda)} 
\prod_{i=1}^\infty \left[\begin{matrix} (N+2)i-2
\sum_{j=1}^i \lambda_j'+m_i(\lambda)\\m_i(\lambda)\end{matrix} \right]_q.
\tag{KOH}
\end{equation}
\vskip2pt\noindent
(a) Write out (KOH) for $k=3$ and explain why it recursively proves that 
$\left[\begin{matrix} M\\3\end{matrix} \right]_q$ is a unimodal polynomial in $q$.
\vskip2pt\noindent
(b) Repeat (a) for a general $k$ by showing that the individual terms in (KOH) are ``centered" correctly.

 \end{document}


