\documentclass[12pt]{article}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\textwidth6.3in
\textheight8.7in
\oddsidemargin0pt
\evensidemargin0pt
\headsep0pt
\headheight0pt
\topmargin0pt

\makeatletter
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}
\renewcommand{\ps@plain}{%
\renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics
  {\footbf 11(2)} (2004), \#R8\hfil\footrm\thepage}}
\makeatother
\pagestyle{plain}

\newcommand{\oF}{\overline{\mathcal F}}
\newcommand{\seq}{\pi}
\newcommand{\Seq}{\Pi}
\newcommand{\Perm}{Perm}
\newcommand{\diag}{\mbox{diag}}
\newcommand{\newton}{\mbox{Newton}}
\newcommand{\ee}{\textbf{e}}
\newcommand{\sgn}{\mbox{sgn\ }}
\newcommand{\const}{\mbox{const}}
\newcommand{\ti}{\tilde}
\newcommand{\color[2]}{}
\newcommand{\ind}{\mbox{ind}}
\newcommand{\bsl}{\backslash}
\newcommand{\bm}[1]{\mbox{\boldmath $#1$}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{question}[theorem]{Question}

\title
{On plethysm conjectures of Stanley and Foulkes: the $2 \times n$ case}

\author {Pavlo Pylyavskyy\\
\small Department of Mathematics\\
\small MIT, Massachusetts, USA\\
\small \texttt{pasha@mit.edu}\\
}
\date{\small
Submitted: Jul 5, 2004; Accepted: Oct 7, 2004; Published: Oct 18, 2004\\
\small Mathematics Subject Classifications: 05E10}
%\keywords{Plethysm conjecture}
%\address{Department of Mathematics, Massachusetts Institute of
%  Technology,
%Cambridge, MA 02141}
%\email{pasha@mit.edu}

\begin{document}

  \maketitle



\begin{abstract}
We prove Stanley's plethysm conjecture for the $2 \times n$ case, which composed with the work of Black and List provides another proof of Foulkes conjecture for the $2 \times n$ case. We also show that the way Stanley formulated his conjecture, it is false in general, and suggest an alternative formulation.
\end{abstract}



\section {Introduction}

%The wreath product of two symmetric groups $S_m w S_n = (\underbrace {S_m \times \cdots \times S_m}_{n \text{ times}}) \rtimes S_n$ is a subgroup of $S_{mn}$ in a natural way%. Consider a character $\pi_{m,n}$ of permutation action of $S_{mn}$ on cosets of $S_m w S_n$. It decomposes into sum $\sum_{\lambda} a_{\lambda}^{m,n} s_{\lambda}$ of irredu%cable characters of $S_{mn}$ indexed by partitions $\lambda$ of $mn$. A conjecture of Foulkes \cite{Foulk} says that the multiplicity $a_{\lambda}^{m,n}$ of the Schur functio%n $s_{\lambda}$ in this decomposition is less than or equal to its multiplicity $a_{\lambda}^{n,m}$ in $\pi_{n,m}$ for all partitions $\lambda$ of $nm$ when $m\geq n$.

Denote by $V$ a finite-dimensional complex vector space, and by $S^mV$ its $m$-th symmetric power. Foulkes in \cite{Foulk} conjectured that the $GL(V)$-module $S^n(S^mV)$ contains the $GL(V)$-module $S^m(S^nV)$ for $n \geq m$. For $m = 2, 3$ and $4$ the conjecture was proved; see \cite{Th}, \cite{DS}, \cite{B}. An extensive list of references can be found in \cite{V}.

In \cite{BL} Black and List showed that Foulkes conjecture follows from the following combinatorial statement. Denote $I_{m,n}$ to be the set of dissections of $\{1, \ldots, mn\}$ into sets of cardinality $m$. Let $s = \bigsqcup_{i=1}^n S_i$ and  $t = \bigsqcup_{i=1}^m T_i$ be elements of $I_{m,n}$ and $I_{n,m}$ respectively. Define matrix $M^{m,n} = (M_{t,s}^{m,n})$ by
$$
M_{t,s}^{m,n} =
\begin{cases}
1 & \text{if $|S_i \cap T_j|=1$ for any $1 \leq i \leq n, 1 \leq j \leq m$;}\\
0 & \text{otherwise.}
\end{cases}
$$

\begin{theorem}[Black, List 89]
If the rank of $M^{m,n}$ is equal to $|I_{n,m}|$ for $n \geq m > 1$, then Foulkes conjecture holds for all pairs of integers $(n,r)$ such that $1 \leq r \leq m$.
\end{theorem}

Let $\lambda$ be a partition of $N$. A {\it {tableau}} is a filling of a Young diagram of shape $\lambda$ with numbers from $1$ to $N$, and let $T_{\lambda}$ to be the set of such tableaux. Define two tableaux to be $h$-equivalent, denoted $\equiv_h$, if they can be obtained one from the other by permuting elements in rows and permuting rows of equal length. Define a {\it {horizontal tableau}} to be an element of $H_{\lambda} := T_{\lambda}/\equiv_h$. In other words, rows of a horizontal tableau form a partition of the set $\{1, \ldots, N\}$. Similarly, define $v$-equivalence $\equiv_v$ and the set $V_{\lambda} := T_{\lambda}/\equiv_v$ of {\it {vertical tableaux}} of shape $\lambda$. Consider a horizontal tableau $\Gamma$ with rows $r_1, \ldots, r_p$ and a vertical tableau $\Delta$ with columns $c_1, \ldots, c_q$. Call $\Gamma$ and $\Delta$ {\it {orthogonal}}, denoted $\Gamma \perp \Delta$, if the inequality $|r_i \cap c_j| \leq 1$ holds for all $i, j$ . Equivalently, $\Gamma$ and $\Delta$ are orthogonal if and only if there exists a tableau $\rho$ consistent with both $\Gamma$ and $\Delta$.

Define the matrix $K_{\lambda} = (K_{\lambda}^{\Gamma, \Delta})$ by
$$
K_{\lambda}^{\Gamma, \Delta} =
\begin{cases}
1 & \text{if $\Gamma \perp \Delta$;}\\
0 & \text{otherwise.}
\end{cases}
$$

The rows of $K_{\lambda}$ are naturally labelled by horizontal tableaux, while the columns are labelled by vertical tableaux. Let $\lambda'$ be the conjugate partition. In \cite{Stan}, Stanley formulated a conjecture, which can be equivalently stated as follows.
 
\begin{conjecture} \label{conj1}
If $\lambda \geq \lambda'$ in dominance order, i.e. $\lambda_1 + \cdots + \lambda_i \geq \lambda'_1 + \cdots + \lambda'_i$ for all $i$, then the rows of $K_{\lambda}$ are linearly independent.
\end{conjecture}

This conjecture is false. For the shape $\lambda$ shown in Figure \ref{lambda}, the inequality $\lambda \geq \lambda'$ holds. However, the matrix $K_{\lambda}$ has more rows than columns, thus the rows cannot be linearly independent. Indeed, $|H_{\lambda}| = \frac{12!}{6!2!2!1!1!2!2!}$, which is greater than $|V_{\lambda}| = \frac{12!}{5!3!1!1!1!1!4!}$. This counterexample was suggested by Richard Stanley as the smallest possible one. The following conjecture seems to be a reasonable alternative formulation, although Max Neunh\"offer has recently shown that in general approach of Black and List does not work, see \cite{N}.

\begin{figure}
\begin{center}
\input{lambda.pstex_t}
\end{center}
\caption{A counterexample for Stanley's conjecture.}\label{lambda}
\end{figure}

\begin{conjecture} \label{conj2}
$K_{\lambda}$ has full rank for all $\lambda$.
\end{conjecture}

Let $\bm {m \times n}$ denote the rectangular shape with $m$ rows and $n$ columns. For rectangular shapes, Stanley's conjecture  implies Foulkes conjecture since $K_{\bm {m \times n}} = M^{m,n}$. For hook shaped $\lambda$, the conjecture is known to be true; see \cite{Stan}. In Section 2 we present a proof of Stanley's conjecture for $\lambda = {\bm {2 \times n}}$.

The author would like to thank Prof. Richard Stanley for the inspiration and many helpful suggestions. The author is also grateful to Denis Chebikin for helping to make this paper readable.



\section{The Main Result}

%We begin with the following lemma.

%\begin{lemma}
%For a rectangular shape $\lambda = m \times n$ with $m$ columns and $n$ rows, $m \geq n$, we have inequality $|H_{\lambda}| \leq |V_{\lambda}|$.
%\end{lemma}

%\begin{proof}
%The statement translates to proving the inequality $\frac{(mn)!}{(m!)^{n-1}} \leq \frac{(mn)!}{(n!)^{m-1}}$, which is equivalent to $(m!)^{\frac{1}{m-1}} \geq (n!)^{\frac{1}{%n-1}}$. It is easy to check that for $m = n+1$ this holds, which implies the general case.
%\end{proof}

Our aim is to prove the following theorem.

\begin{theorem} \label{thm}
Conjecture \ref{conj2} is true for $\lambda = {\bm {2 \times n}}$.
\end{theorem}

Note that for rectangular shapes, Conjectures \ref{conj1} and \ref{conj2} are equivalent, because for $m \leq n$, the inequality $|H_{\bm {m \times n}}| \leq |V_{\bm {m \times n}}|$ holds. Therefore, proving that $K_{{\bm {2 \times n}}}$ has full rank is equivalent to proving that its rows are linearly independent. Suppose for contradiction that there is a nontrivial linear combination of rows of $K_{{\bm {2 \times n}}}$ equal to $0$. Let $\tau_{\Gamma}$ be the coefficient of the row corresponding to a horizontal tableau $\Gamma$ in this combination. Then for a column of $K_{{\bm {2 \times n}}}$ labelled by a vertical tableau $\Delta$, the linear combination $\sum_{\Gamma} K_{{\bm {2 \times n}}}^{\Gamma, \Delta} \tau_{\Gamma}$ equals $0$. Alternatively, this sum can be written as $\sum_{\Gamma \perp \Delta} \tau_{\Gamma} = 0$. Call a $0$-{\it {filter}} a condition on horizontal tableax such that sum of $\tau_{\Gamma}$ over all $\Gamma$ satisfying this condition is $0$. Thus, orthogonality to $\Delta$ is a $0$-filter. Our aim is to show that being $\Gamma$ is a $0$-filter for every horizontal tableau $\Gamma$. Indeed, this is just saying that all $\tau_{\Gamma}$ are equal to $0$, which contradicts the assumption above.


\begin{definition}
For $k<n$, a {\it {subtableau}} of shape ${\bm {2 \times k}}$ of a vertical tableau $\Delta$ of shape ${\bm {2 \times n}}$ is a subset of $k$ columns of $\Delta$. A {\it {partial tableau}} is a collection of $k$ columns which is a subtableau of at least one vertical tableau $\Delta$.
\end{definition}

In other words, a partial tableau is a vertical tableau of shape ${\bm {2 \times k}}$, filled with numbers from $\{1, \ldots, 2n\}$. We can now generalize the concept of orthogonality as follows. Call a horizontal tableau $\Gamma$ of shape ${\bm {2 \times n}}$ orthogonal to a partial tableau $\Delta'$ of shape ${\bm {2 \times k}}$, where $k < n$, if there exists vertical tableau $\Delta$ of shape ${\bm {2 \times n}}$ such that $\Gamma \perp \Delta$, and $\Delta'$ is a subtableau of $\Delta$. An example is presented in Figure \ref{fig2}. The reason for considering such a generalization is evident from the following theorem.

\begin{figure}
\begin{center}
\input{partial.pstex_t}
\end{center}
\caption{Partial tableau $\Delta'$ is a subtableau of $\Delta$. Since $\Gamma \perp \Delta$, also $\Gamma \perp \Delta'$.} \label{fig2}
\end{figure}


\begin{theorem}
Orthogonality to a certain partial tableau $\Delta'$ is a $0$-filter.
\end{theorem}

\begin{proof}
For a given partial tableau $\Delta'$ of shape ${\bm {2 \times k}}$, denote $$F(\Delta') = \{\Delta \in V_{{\bm {2 \times n}}} \mid \text{ $\Delta'$ is a subtableau of $\Delta$}\}.$$ Consider the sum $\sum_{\Delta \in F(\Delta')} \sum_{\Gamma \perp \Delta} \tau_{\Gamma}$. We claim that for each horizontal tableau $\Gamma$, $\tau_{\Gamma}$ enters this sum with the same coefficient. Indeed, the coefficient of a particular $\tau_{\Gamma}$ is the number of tableaux $\Delta$ containing $\Delta'$ and orthogonal to $\Gamma$. Such $\Delta$'s are in one-to-one correspondance with matchings between two sets of size $n-k$, as can be seen from the Figure \ref{fig3}. The number of such matchings is $(n-k)!$, which obviously does not depend on particular $\Gamma$. Therefore, $\frac{1}{(n-k)!} \sum_{\Delta \in F(\Delta')} \sum_{\Gamma \perp \Delta} \tau_{\Gamma} = \sum_{\Gamma \perp \Delta'} \tau_{\Gamma}$. Since each $\sum_{\Gamma \perp \Delta} \tau_{\Gamma}$ is zero by the assumption above, the sum $\sum_{\Gamma \perp \Delta'} \tau_{\Gamma}$ is also $0$, which means that orthogonality to $\Delta'$ is a $0$-filter.

\begin{figure}
\begin{center}
\input{match.pstex_t}
\end{center}
\caption{Each matching corresponds to exactly one possible tableau $\Delta \perp \Gamma$ containing $\Delta'$ as a subtableau.} \label{fig3}
\end{figure}
\end{proof}

We now continue the proof of Theorem \ref{thm}. Choose a particular horizontal tableau $\Gamma_0$, for example with one row filled with numbers $1, \ldots, n$ and the other row filled with the rest of the numbers. If we show that $\tau_{\Gamma_0} = 0$, then in a similar fashion (just by relabelling numbers) we can show that all $\tau_{\Gamma}$'s are $0$, which would be a contradiction with the assumption that the combination of rows of  $K_{{\bm {2 \times n}}}$ is nontrivial. For a given horizontal tableau $\Gamma$, let $a_{\Gamma}$ and  $b_{\Gamma}$ be the numbers of elements of $\{1, \ldots, n\}$ in the rows of $\Gamma$, so that $a_{\Gamma} +  b_{\Gamma} = n$. We do not distinguish between the rows of $\Gamma$, therefore we can assume that $a_{\Gamma} \geq b_{\Gamma}$. Observe that $\Gamma_0$ is the only horizontal tableau such that $(a_{\Gamma_0}, b_{\Gamma_0}) = (n, 0)$. Let $T_a$ be the collection of horizontal tableaux $\Gamma$ with $a_{\Gamma} = a$, and call elements of $T_a$ {\it {horizontal tableaux of type}} $a$. Then $\Gamma_0$ is the only horizontal tableau of type $n$.

\begin{theorem}
For $a \geq n/2$, being a horizontal tableau of type $a$ is a $0$-filter.
\end{theorem}

\begin{proof}
For $k \leq [n/2]$, consider the set $P_k$ of all possible partial tableaux of shape ${\bm {2 \times k}}$, filled with numbers from $\{1, \ldots, n\}$. Consider the sum $\sum_{\Delta' \in P_k} \sum_{\Gamma \perp \Delta'} \tau_{\Gamma}$. We claim that only $\tau_{\Gamma}$'s for $\Gamma$ of type at most $n - k$ appear in this sum. We also claim that the coefficient of $\tau_{\Gamma}$ in the sum depends only on the type of $\Gamma$.

The first statement is easy to verify. Let $\Gamma$ be orthogonal to some $\Delta' \in P_k$. Then each of the two rows of $\Gamma$ contains at least $k$ numbers from $\{1, \ldots, n\}$, which means it cannot have type larger than $n-k$. As for the second statement, we can calculate exactly the number of different $\Delta' \in P_k$ that are orthogonal to a given $\Gamma$ of type $a$. Indeed, first choose an unordered $k$-tuple among the $n-a$ elements of $\{1, \ldots, n\}$ in one row of $\Gamma$. Then match them with a ordered $k$-tuple taken from the $a$ elements of  $\{1, \ldots, n\}$ in the other row. Obviously, such a procedure gives all possible $\Delta'$, each exactly once. Therefore, the coefficient of $\tau_{\Gamma}$ which we are looking for is $c_a^{k} = \frac{(n-a)!a!}{k!(n-a-k)!(a-k)!}$.

We now proceed by induction. For the base case, take $k = [n/2]$. The only horizontal tableaux in the sum $\sum_{\Delta' \in P_k} \sum_{\Gamma \perp \Delta'} \tau_{\Gamma}$ are those of type $n - [n/2]$. Since they all have the same coefficient, and $\sum_{\Delta' \in P_k} \sum_{\Gamma \perp \Delta'} \tau_{\Gamma} = 0$ because each $\sum_{\Gamma \perp \Delta'} \tau_{\Gamma} = 0$, we conclude that $\sum_{\Gamma \in T_{n - [n/2]}} \tau_{\Gamma} = 0$. 

Given that being a type $a$ tableau is a $0$-filter for $n - [n/2] \leq a \leq a' < n$, let us show that being a type $a' + 1$ tableau is a $0$-filter. Indeed, $\sum_{\Delta' \in P_{n-a'-1}} \sum_{\Gamma \perp \Delta'} \tau_{\Gamma} = 0$ as before. This equality can be written as $\sum_{n- [n/2] \leq a \leq a'+1} c_a^{n-a'-1} \sum_{\Gamma \in T_a} \tau_{\Gamma} = 0$, where $c_a^{n-a'-1}$ is the coefficient calculated above. By the induction assumption, we know that for $n - [n/2] \leq a \leq a'$, the sum $\sum_{\Gamma \in T_a} \tau_{\Gamma}$ is $0$. Since $c_{a'+1}^{n-a'-1} \not = 0$, we conclude that $\sum_{\Gamma \in T_{a'+1}} \tau_{\Gamma} = 0$.
\end{proof}

A trivial observation to make is that for $a = n$ this theorem implies that $\tau_{\Gamma_0} = 0$, which leads to the desired contradiction. Therefore, rows of $K_{{\bm {2 \times n}}}$ are linearly independent, which proves Theorem \ref{thm}.















\begin {thebibliography}{L}

\bibitem {B}
E. Briand: {\it Polynomes multisymetriques}, Ph. D. dissertation, University of Rennes I, Rennes, France, 2002.

\bibitem {BL}
S. C. Black and R. J. List: A note on plethysm, {\it  European Journal of Combinatorics} {\bf 10} (1989), no. 1, 111--112.

\bibitem {DS}
S. C. Dent and J. Siemons: On a conjecture of Foulkes, {\it  Journal of Algebra} {\bf 226} (2000), 236-249.

\bibitem {Foulk}
H. O. Foulkes: Concomitants of the quintic and sextic up to degree four in the coefficients of the ground form, {\it Journal of London Mathematical Society} {\bf 25} (1950), 205--209.

\bibitem {N}
M. Neunh\"offer: Some calculations regarding Foulkes' conjecture, \hfill\phantom{K}
http://www.math.rwth-aachen.de/$\tilde{\ }$Max.Neunhoeffer/talks/goslar2004print.pdf

\bibitem {Stan}
R. Stanley:  Positivity problems and conjectures in algebraic combinatorics,
{\it Mathematics: Frontiers and Perspectives}, American Mathematical Society, Providence, RI, 2000, pp. 295-319. 

\bibitem {Th}
R. M. Thrall: On symmetrized Kronecker powers and the structure of the free Lie ring, {\it  American Journal of Mathematics} {\bf 64} (1942), 371-388.

\bibitem {V}
R. Vessenes: Generalized Foulkes' conjecture and tableaux construction, 
\small http://etd.caltech.edu/etd/available/etd-05192004-121256/unrestricted/Chapter1.pdf

\end {thebibliography}


\end {document}



.