\documentclass[10pt]{article}
\usepackage{times}
\usepackage{epsfig}
\usepackage{amssymb}
\usepackage{amsmath}

\setlength{\textheight}{8.875in}
\setlength{\textwidth}{6.875in}
\setlength{\columnsep}{0.3125in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parindent}{1pc}
\setlength{\oddsidemargin}{-.1875in}  % Centers text.
\setlength{\evensidemargin}{-.1875in}

\newcommand{\Section}[1]{\vspace{-8pt}\section{\hskip -1em.~~#1}\vspace{-3pt}}
\newcommand{\SubSection}[1]{\vspace{-3pt}\subsection{\hskip -1em.~~#1}
        \vspace{-3pt}}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{coro}{Corollary}
\newcommand{\bprf}{\par{}\smallskip\noindent{\bf Proof}:\ }
\newcommand{\eprf}{\hfill\rule{.2cm}{.2cm}}
\newcommand{\Z}{\mathbb{Z}}
\begin{document}


% Don't want date printed
\date{}

% Make title bold and 14 apt font (Latex default is non-bold, 16apt)
\title{\Large\bf 
Computer-Generated Symmetric Chain Decompositions for L(4,n) and L(3,n)}
% For single author (just remove % characters)
% For two authors (default example)
\author{
%\begin{tabular}[t]{c@{\extracolsep{8em}}c}
Xiangdong Wen
%\end{tabular}
}


\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Section{Introduction} \label{sec-intro}
Recall that the famous {\it Young's partition lattice}
$ L(m,n)$ consists of the
set of integer-vectors 
$$
(a_1,a_2,\cdots,a_m),\quad 0 \leq a_1 \leq a_2\leq \cdots \leq a_m \leq n,
$$
with the order relation
$$
\vec{a}\leq \vec{b} \quad {\rm if} \quad a_i \leq b_i \quad {\rm for} \quad i=1,2,\cdots,m.
$$
The {\bf rank} $r$ is defined by
$$
r(\vec{a})=\sum_{i=1}^{m}a_{i}.
$$
And recall that a chain $\vec{v_1}\leq \vec{v_2}\leq \cdots\leq \vec{v_k}$
in $L(m,n)$ is called  {\bf saturated} 
if it skips no ranks and {\bf symmetric} if
$r(\vec{v_1})+r(\vec{v_k})=mn.$
\bigskip \\
A {\bf Symmetric chain decomposition}(SCD) of a poset is a way of expressing 
it as a disjoint union of saturated symmetric chains.
\bigskip \\
One of major problems in order theory is the explicit
construction of SCDs for Young's Lattice for {\it all}
$m$ and $n$. In 1989, Kathy O'Hara (\cite{O'Hara}, 
see also \cite{Zeilberger}) has astounded the combinatorial
world by constructing SCDs for the `trivial extension' of $L(m,n)$,
in which all partitions of one rank are related to the next; but
the problem is remaining wide open for Young's lattice itself.
\bigskip \\
SCDs for  L(4,n) and L(3,n) have been constructed by West\cite{West} and
Lindstr\"om\cite{Lind}. In this paper
we explicitly provide {\bf complete} SCDs for L(4,n) and  L(3,n), 
which were found by the assistance of our computer. 
And far more interestingly, it is  proved {\it completely automatically}
without using any human help (except for writing the general Maple program).
While our construction for $L(4,n)$ is not equivalent to
West's construction, it is nevertheless of the similar format.
On the other hand, our construction for $L(3,n)$ is more
elegant than Lindstr\"om's, since it is not split into
even and odd cases.
\bigskip \\
We  hope the present approach would ultimately lead
to computer-generated or at least computer-assisted 
constructions of SCDs for $L(m,n)$, or at least for 
$L(5,n)$. Meanwhile we are unable to do the case of 
$L(5,n)$. We also hope the
present {\it methodology} will be useful for future attacks
on this challenging and tantalizing problem.\\

\Section{New SCDs for L(3,n) and L(4,n)}

\begin{thm}
The following tables give symmetric chain decompositions
for $L(3,n)$ and $L(4,n)$.
In tables below, $i,j$ and $k$ are generic non-negative
integers, and vertical dots represent that the only
component that is not the same gets decremented by $1$.
For example, $(n-i-3j, n-i-2j, n-j) \dots (i+j, n-i-2j, n-j)$
is a shorthand for the chain:
$$(n-i-3j-a, n-i-2j, n-j) , a=0 \dots n-2i-4j . $$


\begin{center}
\begin{tabular}{ccccccccccc}
\hline
  &$C_{ij}$& &\vline&& $D_{ij}$&   \\
  &$2i+4j\leq n$ &&\vline&&$2i+4j+3\leq n$&\\
\hline
( n-i-3j,&n-i-2j,&n-j ) &\vline& ( n-i-3j-1,&n-i-2j-1,&n-j-1 )\\
\vdots &&&\vline &&&\vdots &\\
( i+j,&n-i-2j,&n-j ) &\vline& ( n-i-3j-1,&n-i-2j-1,&n-i-j-1 ) \\
 &\vdots &&\vline &\vdots && &\\
( i+j,&i+2j,&n-j ) &\vline& ( j,&n-i-2j-1,&n-i-j-1 ) \\
 & &\vdots &\vline &&\vdots & &\\
( i+j,&i+2j,&i+3j ) &\vline& ( j,&i+2j+1,&n-i-j-1 ) \\
\vdots & & &\vline && &\vdots &\\
( j,&i+2j,&i+3j ) &\vline& ( j,&i+2j+1,&i+3j+2 ) \\
 \hline
 \end{tabular} \\
A complete SCD for L(3,n)
\end{center}

\begin{center}

\footnotesize{
\begin{tabular}{ccccccccccc}
\hline
  &$C_{ijk}$& &&\vline&& $D_{ijk}$& &  \\
  &$2i+2j+3k\leq n$ &&&\vline&&$2i+2j+3k+3\leq n$&&\\
\hline
( n-2k-2j-i,&n-2k-j-i,&n-k-j,&n-k ) &\vline& ( n-2k-2j-i-1,&n-2k-j-i-1,&n-k-j-1,&n-k )\\
\vdots &&&&\vline &&&\vdots &\\

( k+i,&n-2k-j-i,&n-k-j,&n-k ) &\vline& ( n-2k-2j-i-1,&n-2k-j-i-1,&n-k-i-j-1,&n-k ) \\
 &\vdots &&&\vline& &&&\vdots \\

( k+i,&k+j+i,&n-k-j,&n-k ) &\vline& ( n-2k-2j-i-1,&n-2k-j-i-1,&n-k-i-j-1,&n-k-i-1 ) \\
 & &\vdots &&\vline&\vdots& & &\\

( k+i,&k+j+i,&2k+j+i,&n-k ) &\vline& ( k,&n-2k-j-i-1,&n-k-i-j-1,&n-k-i-1 )\\
 & & &\vdots &\vline &&\vdots  &&\\

( k+i,&k+j+i,&2k+j+i,&2k+2j+i )  &\vline& ( k,&k+j,&n-k-i-j-1,&n-k-i-1 ) \\

\vdots & & &&\vline && &\vdots &\\

( k,&k+j+i,&2k+j+i,&2k+2j+i )  &\vline& ( k,&k+j,&2k+j+i+1,&n-k-i-1 ) \\

&\vdots & & &\vline &&& &\vdots \\

( k,&k+j,&2k+j+i,&2k+2j+i )  &\vline& ( k,&k+j,&2k+j+i+1,&2k+2j+i+2 ) \\

\hline
 \end{tabular}} \\
 A complete SCD for L(4,n)

\end{center}
\end{thm}
\bprf
The chains are clearly saturated and symmetric.
Thus we only need to prove that each
vector in $L(m,n)$ $(m=3,4)$ appears only once in the tables.
We introduce the commuting indeterminate
$x_1,x_2,\cdots, x_m$ and $t$, and define
the {\bf weight} for a vector $\vec{a}=(a_1,a_2,\cdots,a_m)$
in $L(m,n)$ as the following:
$$ {\mbox w}(\vec{a})=
(x_0t)^{n-a_m}(x_1t)^{a_m-a_{m-1}}
\cdots (x_{m-1}t)^{a_2-a_1}(x_mt)^{a_1}   $$
For a fixed $m$, it is easy to see that the total weight,
$$
\sum_{n=0}^{\infty}{\mbox w}(\vec{a}),\quad {\rm where } \quad  \vec{a}\in L(m,n),
$$
is a generating function
 $$G(t;x_1,x_2,\cdots,x_m)=\frac{1}{(1-x_0t)(1-x_1t)\cdots (1-x_mt)}.$$
Each term in the expanded power series
of $G(t;x_1,x_2,\cdots,x_m)$ has coefficient $1$ 
and corresponds to a
unique vector in $L(m,n)$. On the other hand, 
for each vector in $L(m,n)$, there
is a unique corresponding term in the power series of 
$G(t;x_1,x_2,\cdots,x_m)$. Therefore, to prove that each
vector in $L(m,n)$ $(m=3,4)$ appears only once in the SCDs
is the same as to prove that the total weights of the vectors
in the given chains are $G(t;x_1,x_2,x_3)$
and $G(t;x_1,x_2,x_3,x_4)$ respectively.
The part of summing over all the weights of the vectors
is done by computer.
\eprf 
\bigskip \\
This method of proof can be applied to any conjectured SCDs.
The difficult part is
to find such decompositions, here we need human-computer
interactions by using a modified greedy algorithm.
Once it is found, the verification part is purely automatic by 
using the Maple program {\tt Lmn}.
{\tt Lmn} can also be used to give completely automatic proofs
of the validity of Lindstr\"om's and West's constructions.
\bigskip \\
For general m,n, an explicit construction of SCDs of $L(m,n)$  is still an open problem.

\Section{Maple package}
The summation of all the weights of
the vectors in the given chains
is automatically done by computer.
The Maple package is available at
http://www.math.temple.edu/$\sim $wen/lattice/.
After downloading the file to the local disk, type \\
$>$read(``Lmn");\\
in the maple workspace. 
There is detailed on-line help on how to use the procedures in the package
{\tt Lmn}.
 Procedures to compute
 the total weights of the vectors in
 SCDs given by Lindstr\"om\cite{Lind}
and by West\cite{West} are also included in the package {\tt Lmn}.

\Section{Acknowledgment}

This work will be a part of the author's Ph.D. dissertation, written
under the direction of Professor Doron Zeilberger (Rutgers University).
I wish to thank Dr. Zeilberger for his generous support and encouragement.


\begin{thebibliography}{9}
\small  % Use 9 point text.

\bibitem{Lind}[Lindstr\"om]
Bernt Lindstr\"om,
``A partition of L(3,n) into saturated chains'',
{\em European J. Comb}, 61-63,1(1980).

\bibitem{O'Hara}[O'Hara]
Kathleen M. O'Hara,
``Unimodality of Gaussian coefficients: a constructive proof'',
{\em J. Combin. Theory Ser. A} 29-52, 53 (1990).

\bibitem{Proctor}[Proctor]
Robert Proctor,
``Solution of two difficult combinatorial problems with linear algebra'',
{\em American Mathematics Monthly,} 721-734,89(1982).

\bibitem{West}[West]
Douglas B. West,
``A Symmetric chain decomposition of L(4,n)'', 
{\em European J. Comb}, 379-383,1(1980).


\bibitem{Zeilberger}[Zeilberger]
Doron Zeilberger,
``Kathy O'Hara's Constructive proof of the Unimodality of the Gaussian 
Polynomials'',
{\em American Mathematical Monthly,} 590-602,96(1989).

\end{thebibliography}
  
{\bf Department of Mathematics, Temple University, Philadelphia,
PA 19122. wen@math.temple.edu}

\end{document}