\documentclass[12pt]{amsart}

\usepackage[arrow,matrix]{xy}
\usepackage{graphics}
\usepackage{a4wide}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{property}[theorem]{Property}

%\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}
\newtheorem{saturation condition}[theorem]{Saturation Condition}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

%    Absolute value notation
\newcommand{\abs}[1]{\lvert#1\rvert}

%    Blank box placeholder for figures (to avoid requiring any
%    particular graphics capabilities for printing this document).
\newcommand{\blankbox}[2]{%
  \parbox{\columnwidth}{\centering
%    Set fboxsep to 0 so that the actual size of the box will match the
%    given measurements more closely.
    \setlength{\fboxsep}{0pt}%
    \fbox{\raisebox{0pt}[#2]{\hspace{#1}}}%
  }%
}

%	AMS mathematical symbols 
% 	$\mathbb Z^d$, $\mathbb R^d$, $\mathbb C^d$

%\newcommand{\beq}{\begin{equation}}
%\newcommand{\eeq}{\end{equation}}
\renewcommand{\theequation}{\thesection.\arabic{equation}}

\newcommand{\color}[2][x]{} %deals with undefined mnacro in pstex_t files

\def\be{\begin{equation}}
\def\ee{\end{equation}}
\def\0{{\phantom{00}}}
\def\c{\cdot}
\def\+{\!\!+\!\!}
\def\-{\!\!-\!\!}
\def\1{{\bf 1}}
\def\x{{\bf x}}
\def\d{d}

\def\ps{{\it ps}\,}
\def\ch{{\rm ch}\,}
\def\dim{{\rm dim}\,}
\def\sgn{{\rm sgn}\ }
\def\dom{\succeq}
\def\sdom{\succ}
\def\ndom{\not\succeq}
\def\qed{$\hfill\square$\medskip}
\def\mod{{\rm mod}\,}
\def\ds{\displaystyle}
\def\ov{\overline}
\def\implies{\ \Longrightarrow\ }
\def\P{{\cal P}}

%\def\Ra{\Rightarrow}



%	Additional definitions for Young diagrams and tableaux
%\def\mystrut{\hbox{\vrule height10.6pt depth2pt width0pt}}
%\def\mybox{\hbox to 8.9pt}
%\def\bigbox{\hbox to 18.9pt}
%\def\mylongstrut{\hbox{\vrule height9.6pt depth2pt width0pt}}
%\def\bigstrut{\hbox{\vrule height9.6pt depth2pt width0pt}}
%\def\mywidebox{\hbox to 18.9pt}
\def\norulefill{\leaders\hrule height0pt\hfill}
\def\nr#1{\multispan{#1}\norulefill}
\def\hr#1{\multispan{#1}\hrulefill}
%\def\sc{\scriptstyle}
\let\sscc\sc
\def\sc{}

%	Some more definitions

%\def\c1{\ \bullet\ }


\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\C{{\mathbb C}}
\def\R{{\mathbb R}}
\def\cal{\mathcal}
\def\h{{\bf h}}
\def\g{{\bf g}}
\def\mult{{\rm mult}\,}



%	Additional definitions for Young diagrams and tableaux
\def\mystrut{\hbox{\vrule height9.0pt depth2pt width0pt}}
\def\mybox{\hbox to 9.0pt}
\def\norulefill{\leaders\hrule height0pt\hfill}
\def\nr#1{\multispan{#1}\norulefill}
\def\hr#1{\multispan{#1}\hrulefill}
\def\nostrut{\hbox{\vrule height9.0pt depth0pt width0pt}}


\begin{document}

\title[Stretched Littlewood--Richardson coefficients]
{The hive model and the polynomial nature of stretched 
Littlewood--Richardson coefficients}

%\dedicatory{Version: \today}


\author[Ronald C. King]{R.C.~King}
\address{School of Mathematics, University of Southampton,
         Southampton SO17 1BJ, U.K.}
\email{R.C.King@soton.ac.uk}

\author[Christophe  Tollu]{C.~Tollu}
\address{Laboratoire d'Informatique de Paris-Nord, CNRS UMR 7030,
  Universit\'e Paris 13, 93430 Villetaneuse, France}
\email{ct@lipn.univ-paris13.fr}

\author[Fr\'ed\'eric Toumazet]{F.~Toumazet}
\address{Laboratoire d'Informatique de Paris-Nord, CNRS UMR 7030,
  Universit\'e Paris 13, 93430 Villetaneuse, France}
\email{ft@lipn.univ-paris13.fr}





\begin{abstract}

The hive model is used to explore the properties of both
ordinary and stretched Littlewood--Richardson coefficients.
The latter are polynomials in the stretching parameter $t$. 
It is shown that these may factorise, and that they can then 
be expressed as products of certain primitive polynomials. 
It is further shown how to determine a sequence of linear factors 
$(t+m)$ of the primitive polynomials, as well as bounds on their 
degree which are conjectured to be exact.

\medskip

\noindent 
{\sscc R\'esum\'e}. Nous utilisons le mod\`ele des ruches pour \'etudier les
propri\'et\'es des  c{\oe}fficients de Littlewood--Richardson 
et de leurs dilatations. Ces derniers sont des polyn\^omes en le 
param\'etre de dilatation $t$. Nous montrons que
les uns et les autres peuvent se factoriser: ils 
s'\'ecrivent comme des produits de coefficients (respectivement polyn\^omes)
primitifs. 
En outre, nous montrons comment \'etablir une suite de
facteurs lin\'eaires $(t+m)$ des polyn\^omes primitifs, et proposons 
une borne sup\'erieure de leur degr\'e.

\end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 54A \rms (2006), Article~B54Ad\hfill}
\def\thepage{}
%
%

\section{Introduction}

Littlewood--Richardson coefficients, $c_{\lambda\mu}^\nu$, are interesting 
combinatorial objects~\cite{LR}. 
They are indexed by partitions $\lambda$, $\mu$ 
and $\nu$, and they count the number of Littlewood--Richardson
tableaux of skew shape $\nu/\lambda$ and weight $\mu$. 
They are therefore non-negative integers. Although it is a non-trivial
matter to determine whether or not $c_{\lambda\mu}^\nu$
is non-zero, it turns out that this is the case if and only if 
$|\lambda|+|\mu|=|\nu|$ and certain 
partial sums of the parts of $\lambda$, $\mu$ and $\nu$ 
satisfy what are known as Horn inequalities.  

Multiplying all the parts of the partitions $\lambda$, $\mu$ and $\nu$ by
a stretching parameter $t$, with $t$ a positive integer, gives new partitions
$t\lambda$, $t\mu$ and $t\nu$. The corresponding stretched 
Littlewood--Richardson coefficients are known to be polynomials
in the stretching parameter $t$~\cite{DW2,R}. Such an LR-polynomial
is defined by
\begin{equation}
\label{Eq-LRpol}
    P_{\lambda\mu}^{\nu}(t)=c_{t\lambda,t\mu}^{t\nu}, 
\end{equation}
and has a generating function of the form
\begin{equation}
\label{Eq-FG}
   F_{\lambda\mu}^{\nu}(z) = 
  \frac{G_{\lambda\mu}^{\nu}(z)}{(1-z)^{d+1}}
  = \sum_{t=0}^\infty c_{t\lambda,t\mu}^{t\nu}\ z^t 
\end{equation}
where $d$ is the degree of $P_{\lambda\mu}^{\nu}(t)$,
and $G_{\lambda\mu}^{\nu}$ is a polynomial in $z$ of degree
$g\leq d$.

For example, in the case $\lambda=(4,3,3,2,1)$, $\mu=(4,3,2,2,1)$ and 
$\nu=(7,4,4,4,3,2,1)$ one finds $c_{\lambda\mu}^\nu=13$ and
\begin{equation}
 P_{\lambda,\mu}^{\nu}(t)=
 \frac{1}{10080}(t+1)(t+2)(t+3)(t+4)(t+5)(5t+21)(t^2+2t+4),
\label{Eq-Pol-ex}
\end{equation}
with
\begin{equation}
\label{Eq-FG-ex}
 F_{\lambda\mu}^\nu(z)=\frac{1+4z+12z^2+3z^3}{(1-z)^9}.
\end{equation}

It is the intention 
here to try to shed some light on the nature of the LR-polynomials
and their generating functions. In particular we concentrate on the
possible factorisation of any particular LR-polynomial
as a product of simpler LR-polynomials, the degree $d$ of an
LR-polynomial, and the number of its linear factors $(t+m)$. We
do not explore two particular conjectures~\cite{KTT1}
to the effect
that the non-zero coefficients of the polynomial $P_{\lambda\mu}^\nu(t)$ 
are always positive rational numbers, while those
of $G_{\lambda\mu}^\nu(z)$ are all positive integers.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL RONALD C. KING, CHRISTOPHE TOLLU, AND FR\'ED\'ERIC TOUMAZET}{\SMALL STRETCHED LITTLEWOOD--RICHARDSON COEFFICIENTS}
%
%
 
Our approach is based largely on the use of a hive
model~\cite{BZ2,KT,B} which allows 
Littlewood--Richardson coefficients to be evaluated through the enumeration 
of integer points of certain rational polytopes. 
Before defining hives, puzzles and plans, that are the combinatorial 
constructs to be used in this context,
it is worth recalling some definitions and properties of 
Littlewood--Richardson coefficients and LR-polynomials. 

\section{Definitions and properties}
\label{sec:definitions}

Let $n$ be a fixed positive integer, let $\x=(x_1,x_2,\ldots,x_n)$ 
be a vector of indeterminates, and let 
$\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_n)$
be a partition of weight $|\lambda|$ and of length $\ell(\lambda)\leq n$.
Thus $\lambda_k\in\Z^+$ for $k=1,2,\ldots,n$, 
with $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_{\ell(\lambda)}>0$
and $\lambda_k=0$ for $k>\ell(\lambda)$. 

\begin{definition}
\label{Def-sf}\
For each partition $\lambda$ with $\ell(\lambda)\leq n$ there
corresponds a Schur function $s_\lambda(\x)$ defined by
\begin{equation}
   s_\lambda(\x) =
\frac{\left| x_i^{n+\lambda_j-j}\right|_{1\leq i,j\leq n}} 
{\left| x_i^{n-j}\right|_{1\leq i,j\leq n}} 
\label{Eq-sf}
\end{equation}
\end{definition}

Choosing $n$ sufficiently large, the Littlewood--Richardson 
coefficients may be defined by

\begin{definition}
\begin{equation}
      s_\lambda(\x)\ s_\mu(\x) 
    = \sum_\nu c_{\lambda\mu}^\nu\ s_\nu(\x).
\label{Eq-sf-LR}
\end{equation}
where the summation is over all partitions $\nu$.
\end{definition}

The expansion (\ref{Eq-sf-LR}) may be effected by 
means of the Littlewood--Richardson rule~\cite{LR} 
which states that
$c_{\lambda\mu}^\nu$ is the number of Littlewood--Richardson 
skew tableaux $T^{\nu/\lambda}$ of shape $\nu/\lambda$ and weight $\mu$ 
obtained by numbering the boxes of the skew Young diagram $F^{\nu/\lambda}$ 
with $\mu_i$ entries $i$ for $i=1,2,\ldots,n$ that are weakly increasing
across rows, strictly increasing down columns and satisfy the lattice 
permutation rule. This rule states that in reading the entries of 
$T^{\nu/\lambda}$ from right to left across each row in turn from top to 
bottom, then at every stage the number of $k$'s is greater than or equal 
to the number of $(k+1)$'s for all $k=1,2,\ldots,n-1$. For the sake of 
what is to follow, it is convenient to augment each
Littlewood--Richardson skew tableau $T^{\nu/\lambda}$, with 
a tableau obtained by numbering all the boxes of the
Young diagram $F^\lambda$ with entries $0$, as in~\cite{LR} p122,
thereby creating what we call an LR-tableau $D$ of shape $\nu$. 
The entries $0$ contribute nothing to the weight  of $D$, which
remains that of the portion $T^{\nu/\lambda}$.
By way of example, for $n=3$, $\lambda=(3,2,0)$, $\mu=(2,1,0)$
and $\nu=(4,3,1)$, there exist just two LR-tableaux:
\begin{equation}
{\vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\mybox{\hss$\sc#$\hss}\cr
  \hr{9}\cr
  &0&&0&&0&&1&\cr
  \hr{9}\cr
  &0&&0&&1&\cr
  \hr{7}\cr
  &2&\cr
  \hr{3}\cr
   }}}
\qquad\qquad
{\vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\mybox{\hss$\sc#$\hss}\cr
  \hr{9}\cr
  &0&&0&&0&&1&\cr
  \hr{9}\cr
  &0&&0&&2&\cr
  \hr{7}\cr
  &1&\cr
  \hr{3}\cr
   }}}
\label{Eq-LRdiags}
\end{equation}
Hence $c_{32,21}^{431}=2$. 

To specify the necessary and sufficient conditions on $\lambda$, $\mu$ 
and $\nu$ for $c_{\lambda\mu}^\nu$ to be non-zero it is convenient 
to introduce the notion of partial sums of the parts of a partition
and some other notational devices.

Let $n$ be a fixed positive integer and $N=\{1,2,\ldots,n\}$.  
Then for any positive integer $r\leq n$
and any subset $I=\{i_1,i_2,\ldots,i_r\}$ of $N$
of cardinality $\#I=r$, the partial sum indexed by $I$ of any partition
$\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_n)$ of length 
$\ell(\lambda)\leq n$ is defined to be
\begin{equation}
\ps(\lambda)_I =\lambda_{i_1}+\lambda_{i_2}+\cdots+\lambda_{i_r}\,.
\label{Eq-ps-I}
\end{equation}
In the special case for which $I=\{1,2,\ldots,i\}$ we write 
$\ps(\lambda)_i$ instead of $\ps(\lambda)_I$. Quite generally,
if $i_1<i_2<\cdots<i_r$, let $\tilde{I}=(i_r,\ldots,i_2,i_1)$. 
It follows that if $\delta_r=(r,r-1,\ldots,1)$ then 
$\alpha(I)=\tilde{I}-\delta_r$ is a partition of length 
$\ell(\alpha(I))\leq r$. 

With this notation, building on a connection
with the Horn conjecture~\cite{H} regarding eigenvalues 
of Hermitian matrices, the following theorem has been 
established by Klyachko~\cite{K}, Knutson and Tao~\cite{KT}
%Knutson, Tao and Woodward~\cite{KTW} 
and others. A 
comprehensive review of these developments has been
provided by Fulton~\cite{F}.

\begin{theorem}[Horn inequalities]
Let $\lambda$, $\mu$ and $\nu$ be partitions
of lengths $\ell(\lambda),\ell(\mu),\ell(\nu)\leq n$. Then 
$c_{\lambda\mu}^\nu>0$ if and only if $|\nu|=|\lambda|+|\mu|$ and 
for all $r=1,2,\ldots,n-1$
\begin{equation}
   \ps(\nu)_K \leq \ps(\lambda)_I+\ps(\mu)_J
\label{Eq-Horn}
\end{equation}
for all triples $(I,J,K)\in N_r^n$, 
where $N_r^n$ is the set of triples $(I,J,K)$, with
$I,J,K\subset N$ and $\#I=\#J=\#K=r$, 
such that if $\alpha(I)=\tilde{I}-\delta_r$, 
$\beta(J)=\tilde{J}-\delta_r$ and $\gamma(K)=\tilde{K}-\delta_r$
then $c_{\alpha(I)\beta(J)}^{\gamma(K)}>0$. Moreover, not
all of the Horn inequalities of type (\ref{Eq-Horn}) are
essential, only those for which $(I,J,K)\in R_r^n$, 
where $R_r^n$ is the subset of $N_r^n$ for which
$c_{\alpha(I)\beta(J)}^{\gamma(K)}=1$. 
\label{Theo-Horn}
\end{theorem}

Unfortunately, even for comparatively
small values of $r$ it is not a trivial matter to identify all partitions
$\alpha(I),\beta(J),\gamma(K)$, and hence $(I,J,K)$,
such that the Littlewood--Richardson coefficient 
$c_{\alpha(I)\beta(J)}^{\gamma(K)}=1$. 

%We will return to this problem 
%only after the hive model has been introduced. 

Turning to stretched Littlewood--Richardson coefficients, the  
fact that all the above partial sum conditions are linear and homogeneous
in the various parts of $\lambda$, $\mu$ and $\nu$ 
ensures the validity of the following:
\begin{theorem}[Saturation Condition]~\cite{KT,B,DW1}\ 
For all positive integers $t$
\begin{equation}
  c_{t\lambda,t\mu}^{t\nu} >0\ \Longleftrightarrow\ c_{\lambda\mu}^\nu > 0.
\label{Eq-Sat}
\end{equation}
\label{Theo-Sat}
\end{theorem} 

Furthermore, the following condition has been proved by a 
variety of means:
\begin{theorem}[Polynomial Condition]~\cite{DW2,R} 
For all partitions $\lambda$, $\mu$ and $\nu$ such that
$c_{\lambda\mu}^\nu>0$ there exists a polynomial $P_{\lambda\mu}^\nu(t)$ 
in $t$ such that 
$P_{\lambda\mu}^\nu(t)=c_{t\lambda,t\mu}^{t\nu}$ for all $t\in\N$.
\label{Theo-Pol}
\end{theorem}

In addition, the following conjecture has been established as a theorem:
\begin{theorem}[Fulton's Conjecture]~\cite{KTW} 
For all positive integers $t$
\begin{equation}
    c_{t\lambda,t\mu}^{t\nu}=1  \quad\Longleftrightarrow\quad  
    c_{\lambda\mu}^\nu=1.
\end{equation}
\label{Theo-Ful}
\end{theorem}

Thus, if $c_{\lambda\mu}^\nu=1$, the corresponding polynomial 
$P_{\lambda\mu}^\nu(t)=1$.

\section{The hive model}

The hive model arose out of the triangular arrays
of Berenstein and Zelevinsky used to
specify individual contributions to Littlewood--Richardson 
coefficients~\cite{BZ2}. The model was then taken up by
Knutson and Tao in a manner described in an exposition by Buch~\cite{B}.
 
An $n$-hive is an array of numbers $a_{ij}$ with 
$0\leq i,j,i+j\leq n$ placed at the vertices of an equilateral triangular
graph. 
Typically, for $n=4$ their arrangement is as shown below:


\begin{center}
\scalebox{0.8}{\input{h_aij.pstex_t}}
\end{center}


Such an $n$-hive is said to be an integer hive if all of its entries are
non-negative integers.
Neighbouring entries define three distinct types of rhombus, each with
its own constraint condition.

\begin{center}
\scalebox{0.8}{\input{h_r123.pstex_t}}\\
\end{center}

\noindent
In each case, with the labelling as shown, the hive condition takes
the form:
\begin{equation}
b+c \geq a+d
\label{HCvertex}
\end{equation} 
In what follows we make use of edge labels more often than vertex labels.
Each edge in the hive is labelled by means of the non-negative difference,
$\epsilon=q-p$, 
between the labels, $p$ and $q$, on the two vertices connected by this
edge, 
with $q$ always to the right of $p$. In all the above cases, with this 
convention,
we have $\alpha+\delta=\beta+\gamma$, and the hive conditions take the form:
\begin{equation}
\alpha\geq \gamma\ \  \mbox{  and  }\ \ \beta \geq \delta,
\label{HCedge}
\end{equation} 
where, of course, either one of the conditions $\alpha\geq\gamma$
or $\beta\geq\delta$ is sufficient to imply the other.

In order to enumerate contributions to Littlewood--Richardson 
coefficients, we require the following:
 
\begin{definition}
An LR-hive is an integer n-hive, for
some positive integer $n$, satisfying the hive conditions 
(\ref{HCvertex}), or equivalently (\ref{HCedge}),
for all its constituent rhombi of type R1, R2 and R3,
with border labels determined by partitions $\lambda$,
$\mu$ and $\nu$, for which $\ell(\lambda),\ell(\mu),\ell(\nu)\leq n$ 
and $|\lambda|+|\mu|=|\nu|$,
in such a way that $a_{00}=0$, $a_{0,i}=\ps(\lambda)_i$,
$a_{j,n-j}=|\lambda|+\ps(\mu)_j$ and $a_{k,0}=\ps(\nu)_k$, 
for $i,j,k=1,2,\ldots,n$.
\label{Def-LRhive}
\end{definition}
Schematically, we have


\begin{center}
\scalebox{0.8}{\input{h_lr_vert.pstex_t}}\\
\end{center}

Alternatively, in terms of edge labels we have:

\begin{center}
\scalebox{0.8}{\input{h_lr_edge.pstex_t}}\\
\end{center}

There exists a bijection between LR-tableaux $D$, 
of shape determined by $\nu/\lambda$ and of weight $\mu$ 
and LR-hives $H$, with border labels specified by $\lambda$, $\mu$ and
$\nu$. An illustration of this bijection is given below for a typical 
LR-tableau $D$ in the case $n=3$,
$\lambda=(3,2)$, $\mu=(2,1)$ and $\nu=(4,3,1)$.
In $D$, which has overall shape $\nu$, the portion of shape
$\lambda$ has been signified by entries $0$, while the other entries
correspond to the parts of the weight $\mu$ arranged in accordance with the 
Littlewood--Richardson rules. The first step is to form what might be called a 
generalised Gelfand--Tsetlin pattern $G$ by writing
down a list of partitions describing the shapes of
sub-tableaux of $D$ formed by restricting the entries to be no more than 
$k$ for $k=3,2,1,0$. Then one adds a diagonal of zeros and forms
cumulative row sums to arrive at an array $Z$. The lower right
triangular portion of $Z$ is then reoriented to give 
an LR-hive $H$, where for display purposes the hive edges have been omitted.

\begin{equation}
\begin{array}{cccc}
&D= 
{\vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\mybox{\hss$\sc#$\hss}\cr
  \hr{9}\cr
  &0&&0&&0&&1&\cr
  \hr{9}\cr
  &0&&0&&2&\cr
  \hr{7}\cr
  &1&\cr
  \hr{3}\cr
   }}}
&\ \Longleftrightarrow\
&G=
{\vcenter
 {\offinterlineskip
 \halign{&\nostrut#&\mybox{\hss$\sc#$\hss}\cr
  \nr{17}\cr
  &4&& &&3&& &&1&& && && &\cr
  \nr{17}\cr
  & &&4&& &&3&& &&1&& && &\cr
  \nr{17}\cr
  & && &&4&& &&2&& &&1&& &\cr
  \nr{17}\cr
  & && && &&3&& &&2&& &&0&\cr
  \nr{17}\cr
   }}}
\cr
\cr
\ \Longleftrightarrow\ 
&Z=
{\vcenter
 {\offinterlineskip
 \halign{&\nostrut#&\mybox{\hss$\sc#$\hss}\cr
  \nr{21}\cr
  &0&& &&4&& &&7&& &&8&& && && &\cr
  \nr{21}\cr
  & &&0&& &&4&& &&7&& &&8&& && &\cr
  \nr{21}\cr
  & && &&0&& &&4&& &&6&& &&7&& &\cr
  \nr{21}\cr
  & && && &&0&& &&3&& &&5&& &&5&\cr
  \nr{21}\cr
   }}}
&\ \Longleftrightarrow\ 
&H=
{\vcenter
 {\offinterlineskip
 \halign{&\nostrut#&\mybox{\hss$\sc#$\hss}\cr
  \nr{15}\cr
  & && && &&5&& && && &\cr
  \nr{15}\cr
  & && &&5&& &&7&& && &\cr
  \nr{15}\cr
  & &&3&& &&6&& &&8&& &\cr
  \nr{15}\cr
  &0&& &&4&& &&7&& &&8&\cr
  \nr{15}\cr
   }}}
\end{array}
\label{Eq-D-H}
\end{equation}

More detailed considerations of the maps illustrated in this 
example lead to:

\begin{proposition}~\cite{B} 
The Littlewood--Richardson coefficient $c_{\lambda\mu}^\nu$ 
is the number of LR-hives with border labels determined 
as in Definition~\ref{Def-LRhive} by 
$\lambda$, $\mu$ and $\nu$.
\label{Prop-LRhives}
\end{proposition}

The above sequence of maps is such that for all $(i,j)$ with 
$0\leq i,j,i+j\leq n$ the entries of the LR-hive $H$ are given by
\begin{equation}
a_{ij}=~~\hbox{$\#$ of entries $\leq i$ in first $(i+j)$ rows of $D$}\,.
\label{Eq-H-aij}
\end{equation}

As far as the boundary labels are concerned, it
should be noted, firstly, that $a_{0j}$ is the number of entries 
equal to $0$ in the first $j$ rows of $D$. 
That is to say, $a_{00}=0$ and $a_{0j}=\ps(\lambda)_j$ for $j=1,2,\ldots,n$.
Secondly, $a_{i0}$ is the number of entries less than or equal to
$i$ in the first $i$ rows of $D$. However, by virtue of their weakly 
increasing order across rows and the lattice permutation rule, all 
entries in the first $i$ rows of $D$ are no greater than $i$. It follows 
that $a_{i0}=\ps(\nu)_i$ for $i=1,2,\ldots,n$. 
Thirdly, $a_{i,n-i}$ is the total number of entries less than or equal to
$i$ in $D$. Thus $a_{0,n}=|\lambda|$ and $a_{i,n-i}=|\lambda|+\ps(\mu)_i$
for $i=1,2,\ldots,n$. Thus the boundary labels of the LR-hive $H$ are
given by the partial sums of the partitions $\lambda$, $\mu$ and
$\nu$, as required. 

A further consequence of (\ref{Eq-H-aij}) is that the hive decrements
$\Delta=b+c-a-d=\alpha-\gamma=\beta-\delta$ arising from the 
rhombi of type R1, R2 and R3 with $a$ in position$(i,j)$ are given by:
\begin{eqnarray}
{\rm R1}:\ \Delta
&=& \hbox{$\#$ of entries $(i+1)$ in first $(i+j)$ rows of $D$}\\
&&~-~\hbox{$\#$ of entries $(i+2)$ in first $(i+j+1)$ rows of $D$}\,;\cr
{\rm R2}:\ \Delta
&=& \hbox{$\#$ of entries $(i+1)$ in the $(i+j)$th row of $D$}\,;\\
{\rm R3}:\ \Delta
&=& \hbox{$\#$ of entries $\leq i$ in $(i+j+1)$th row of $D$}\\ 
&&~-~\hbox{$\#$ of entries $\leq(i+1)$ in $(i+j+2)$th row of $D$}\,.
\nonumber
\label{Eq-dec}
\end{eqnarray}
Since for each $k=1,2,\ldots,n$ the number of entries $k$ in each row of 
$D$ is non-negative, we have $\Delta\geq0$ for each rhombus of type R2. The fact that 
the non-zero entries in $D$ are weakly increasing across rows and strictly 
increasing down columns then ensures that $\Delta\geq0$ for each rhombus of
type R3. Finally, in the case of each rhombus of type R1, the hive condition 
$\Delta\geq0$ is implied directly by the lattice permutation rule. It follows that each
$H$ obtained from any LR-tableau $D$ is indeed an LR-hive.

Conversely, the inverse of the above maps from any LR-hive $H$ always 
yields an LR-tableau $D$. The positions of the $0$'s are determined by the
border labels $a_{0,j}=\ps(\lambda)_j$. Then the R2 hive condition $\Delta\geq0$ 
is just the condition that the number of entries of each type in each row of $D$ is
a non-negative integer. If these entries are arranged in weakly increasing order 
across the rows of $D$, then the R3 hive condition $\Delta\geq0$ implies that,
apart from the possibility of consecutive $0$s, the entries are strictly increasing 
down columns.  The fact that the R1 hive condition $\Delta\geq0$ is precisely the
lattice permutation rule, then ensures that each $D$ obtained from an 
LR-hive $H$ is an LR-tableau. 

Thus the maps described above are bijective, and Proposition~\ref{Prop-LRhives}
follows.
\qed

As an example of the application of this Proposition, if $n=3$, $\lambda=(3,2,0)$,
$\mu=(2,1,0)$ and $\nu=(4,3,1)$ then the corresponding LR-hives take the form
\begin{equation}
{\vcenter
 {\offinterlineskip
 \halign{&\nostrut#&\mybox{\hss$\sc#$\hss}\cr
  \nr{15}\cr
  & && && &&5&& && && &\cr
  \nr{15}\cr
  & && &&5&& &&7&& && &\cr
  \nr{15}\cr
  & &&3&& &&a&& &&8&& &\cr
  \nr{15}\cr
  &0&& &&4&& &&7&& &&8&\cr
  \nr{15}\cr
   }}}
\label{Eq-LR-Hive-Ex}
\end{equation}
The LR-hive conditions for all the constituent rhombi then 
imply that $6\leq a\leq7$. Thus there are just two LR-hives with the
given boundary labels, namely those with $a=7$ and $a=6$. 
Thus $c_{32,21}^{431}=2$ in accordance with the result established earlier 
by enumeration of the LR-tableaux of (\ref{Eq-LRdiags}).

It might be pointed out here, that when expressed in terms of edge labels, 
the hive conditions 
(\ref{HCedge}) for all constituent rhombi of types R1, R2 and R3 
imply that in every LR-hive the edge labels along any line
parallel to the north-west, north-east and southern boundaries 
of the hive are weakly decreasing in the north-east, south-west and
easterly directions, respectively. 
This can be seen from the following 5-vertex sub-diagrams. 

\begin{center}
\scalebox{0.7}{\input{h_5v3.pstex_t}}
\end{center}

\noindent
The edge conditions on the overlapping pairs of rhombi (R1,R2),
(R1,R3) and (R2,R3) in the above diagrams give in each case 
$\alpha\geq\beta$ and $\beta\geq\gamma$, so that $\alpha\geq\gamma$
as claimed. This is of course consistent with the fact that edges of 
the three north-west, north-east and southern boundaries of each 
LR-hive are specified by partitions $\lambda$, $\mu$ and $\nu$, 
respectively.




\section{Factorisation}
\label{sec:factorisation}

It was noted in the work of Berenstein and Zelevinsky~\cite{BZ1}
that some Kostka coefficients may factorise. Although rather easy to 
prove using semistandard tableaux, this factorisation property 
may also be established through the use of K-hives~\cite{KTT2}. 
Analogous methods may be used to show that some Littlewood--Richardson 
coefficients may also factorise. 
Following the use of similar terminology in the case of Kostka 
coefficients~\cite{KTT2}, we propose the following
\begin{definition}
\label{Def-primitive}
Let $\lambda$, $\mu$ and $\nu$ be partitions such that $|\nu|=|\lambda|+|\mu|$,
$\ell(\lambda),\ell(\mu),\ell(\nu)\leq n$ and $c_{\lambda\mu}^\nu>0$. 
Then the Littlewood--Richardson coefficient $c_{\lambda\mu}^\nu$ 
is said to be {\it primitive} if $\ps(\nu)_K<\ps(\lambda)_I+\ps(\mu)_J$ 
for all $(I,J,K)\in R_r^n$ and all $r=1,2,\ldots,n-1$.
Conversely, $c_{\lambda\mu}^\nu$ is not primitive if there exists any 
$(I,J,K)\in R_r^n$ with $1\leq r<n$ such that
$\ps(\nu)_K=\ps(\lambda)_I+\ps(\mu)_J$.
\end{definition}

With this definition, we conjecture that if $c_{\lambda\mu}^\nu$ is 
positive but not primitive, then $c_{\lambda\mu}^\nu$ factorises. 
In order to specify the manner in which such a non-primitive 
Littlewood--Richardson coefficient factorises it is convenient to 
introduce some further notation.
As usual, let $n$ be a fixed positive integer and let $N=\{1,2,\ldots,n\}$.
Then for any $I=\{i_1,i_2,\ldots,i_r\}\subseteq N$,
with $i_1<i_2<\cdots<i_r$ and $1\leq r\leq n$, let ${\overline I}=N\backslash I$
be the complement of $I$ in $N$. In addition, for any partition or weight 
$\kappa=(\kappa_1,\kappa_2,\ldots,\kappa_n)$
let $\kappa_I=(\kappa_{i_1},\kappa_{i_2},\ldots,\kappa_{i_r})$.
With this notation we make the following:
\begin{conjecture}
\label{Conj-LRfact}
Let $\lambda$, $\mu$ and $\nu$ be partitions of lengths 
$\ell(\lambda),\ell(\mu),\ell(\nu)\leq n$. If $c_{\lambda\mu}^\nu>0$ 
and there exists proper subsets $I,J,K$ of $N$ with 
$(I,J,K)\in R_r^n$ such that
$\ps(\nu)_K=\ps(\lambda)_I+\ps(\mu)_J$ then 
\begin{equation}
    c_{\lambda\mu}^\nu
    =c_{\lambda_I\mu_J}^{\nu_K}\ 
     c_{\lambda_{\overline I}\mu_{\overline J}}^{\nu_{\overline K}}.
\label{Eq-LRfact}
\end{equation}
\end{conjecture} 

This means that if any one of Horn's essential inequalities 
(\ref{Eq-Horn}) is an equality for $1\leq r<n$ then 
$c_{\lambda\mu}^\nu$ factorises. 
Repeated use of the above conjecture would allow any non-vanishing
Littlewood--Richardson coefficient to be written as a product of primitive 
Littlewood--Richardson coefficients. Furthermore, since the partial sum
conditions are preserved under scaling by any positive number $t$,
we have the following:
\begin{conjecture}
\label{Cor-LRfact}
Let $\lambda$, $\mu$ and $\nu$ be partitions of lengths 
$\ell(\lambda),\ell(\mu),\ell(\nu)\leq n$. If $c_{\lambda\mu}^\nu>0$ and 
there exists proper subsets $I,J,K$ of $N$ with 
$(I,J,K)\in R_r^n$ such that
$\ps(\nu)_K=\ps(\lambda)_I+\ps(\mu)_J$ then 
\begin{equation}
    P_{\lambda\mu}^\nu(t)
    =P_{\lambda_I\mu_J}^{\nu_K}(t)\ 
   P_{\lambda_{\overline I}\mu_{\overline J}}^{\nu_{\overline K}}(t).
\label{Eq-LRpolfact}
\end{equation}
\end{conjecture} 

The origin of these conjectures can be exposed 
through a study of the properties
of certain puzzles introduced by Knutson {\it et al.}~\cite{KTW}.
These are triangular diagrams on a hive lattice consisting of 
three elementary pieces: a dark triangle, a light triangle
and a shaded rhombus with its edges either dark or light according as 
they are to the right or left, respectively of an acute angle
of the rhombus, when viewed from its interior:

\begin{center}
\scalebox{0.7}{\input{h_lr_pieces.pstex_t}}
\end{center}

The puzzle is to put these together, oriented
in any manner, so as to form a hive shape with all the edges 
matching. For example, one such puzzle takes the form
shown below:

\begin{center}
\scalebox{0.6}{\input{h_lr_puzzle.pstex_t}}
\end{center}

As pointed out by Danilov and Koshevoy~\cite{DK}, such a puzzle can
be simplified, without loss of information, to give a labyrinth
or hive plan by deleting all interior edges
of the three types of region: corridors in the form
of shaded parallelograms consisting of rhombi of just one type,
either R1, or R2 or R3, and dark rooms and light rooms that are convex 
polygons consisting solely of just dark-edged triangles and just 
light-edged triangles, respectively. 

\begin{center}
\scalebox{0.6}{\input{h_lr_plan.pstex_t}}
\end{center}

It is a remarkable fact~\cite{KTW} 
that for each positive integer
$r<n$ and triple $(I,J,K)\in R_r^n$, there exists
a unique puzzle, and correspondingly a unique hive plan
of the above type. 
In this hive plan the dark edges on the 
boundary are those specified by $I$, $J$ and $K$.  
In connection with the above Conjecture~\ref{Conj-LRfact}, 
the thick edges on the boundary of each LR-hive
are then labelled by the parts of $\lambda_I$, $\mu_J$ and $\nu_K$, and 
the thin edges by the parts of $\lambda_{\overline I}$, $\mu_{\overline J}$ and
$\nu_{\overline K}$.

In the example illustrated, for which $n=5$, $r=3$, $I=\{1,2,4\}$, $J=\{2,3,4\}$,
$K=\{2,3,5\}$, we have $\alpha(I)=(1,0,0)$, $\beta(J)=(1,1,1)$ and 
$\gamma(K)=(2,1,1)$. The fact that $(I,J,K)\in R_3^5$ then follows
from the observation that $c_{1,111}^{211}=1$. Superposing the
corresponding hive plan on the LR-hives with boundaries 
specified by $\lambda$, $\mu$ and $\nu$ then gives

\begin{center}
\scalebox{0.6}{\input{h_lr_fact.pstex_t}}
\end{center}

The validity of Conjecture~\ref{Conj-LRfact} would imply that if 
\begin{equation}
     \nu_2+\nu_3+\nu_5=\lambda_1+\lambda_2+\lambda_4+\mu_2+\mu_3+\mu_4.
\label{Eq-Horn-ex}   
\end{equation} 
then  $c_{\lambda\mu}^\nu$ must factorise as follows
\begin{equation}
      c_{\lambda\mu}^\nu= 
c_{(\lambda_1,\lambda_2,\lambda_4),(\mu_2,\mu_3,\mu_4)}^{(\nu_2,\nu_3,\nu_5)}
\
c_{(\lambda_3,\lambda_5),(\mu_1,\mu_5)}^{(\nu_1,\nu_4)}
\label{Eq-Fact-ex}
\end{equation} 

To see how this comes about one just deletes the corridors from the initial
LR-hive and glues together all the dark rooms, labelled $0$,
and all the light rooms, labelled $1$, to create two smaller LR-hives, 
as shown below:

\begin{center}
\scalebox{0.6}{\input{h_lr_factors.pstex_t}}
\end{center}

To prove the validity of such a factorisation, one has to show 
that the Horn equality (\ref{Eq-Horn-ex}) leads to a bijection between 
all the large LR-hives and all pairs of small LR-hives obtained by 
the deletion and glueing processes. 
As a first step one observes that the application of the LR-hive 
conditions to any puzzle leads directly to a Horn inequality. 

To continue with our example, interior edge labels may be 
introduced as shown below.

\begin{center}
\scalebox{0.6}{\input{h_lr_fact_labels.pstex_t}}
\end{center}

The successive application of the LR-hive conditions to each shaded 
sub-rhombus of the above puzzle gives in the case of dark edge inequalities:
\begin{eqnarray}
&&\nu_2+\nu_3+\nu_5 \leq (\nu_2+\nu_3)+\gamma_4 
= (\alpha_1+\alpha_2+\beta_1+\beta_2)+\gamma_4\\
&&\leq \lambda_1+\alpha_2+\beta_1+\beta_2+\gamma_4 
\leq \lambda_1+\lambda_2+\beta_1+\beta_2+\gamma_4\cr
&&\leq \lambda_1+\lambda_2+\beta_3+\beta_2+\gamma_4 
\leq \lambda_1+\lambda_2+(\beta_3+\beta_4+\gamma_4)\cr
&&= \lambda_1+\lambda_2+(\alpha_4+\mu_2+\mu_3+\mu_4) 
\leq \lambda_1+\lambda_2+\lambda_4+\mu_2+\mu_3+\mu_4\,,
\nonumber
\label{Eq-puzzle-ineq-dark}
\end{eqnarray}
where the intermediate equalities are just expressions of the fact 
that sums of any combination of positive edge lengths between any two 
fixed points are always the same. 
The result, as claimed quite generally, is a Horn inequality. 
In fact~\cite{KTW} all Horn inequalities, both essential
and inessential, may be derived in this way 
from puzzles. 

The same procedure applied to light edge inequalities gives
\begin{eqnarray}
&&\nu_1+\nu_4 \geq \gamma_1+\nu_4 
= \gamma_1+(\alpha_5+\beta_5)\\
&&\geq \gamma_1+\alpha_3+\beta_5 
\geq (\gamma_1+\alpha_3)+\mu_5=(\lambda_3+\gamma_2)+\mu_5\cr
&&\geq \lambda_3+\gamma_3+\mu_5= 
\lambda_3+(\lambda_5+\mu_1)+\mu_5\,. 
\nonumber
\label{Eq-puzzle-ineq-light}
\end{eqnarray}
This is the complement of the Horn inequality (4.5) %(\ref{Eq-puzzle-ineq-dark})
with respect to the identity $|\nu|=|\lambda|+|\mu|$.

Clearly, if any Horn inequality is saturated, that is to say becomes an equality,
then {\it all} of the individual inequalities arising in its derivation 
are also saturated, as well as the individual inequalities in its complement.
In our example, this means that if the condition (\ref{Eq-Horn-ex}) 
is satisfied then we must have $\nu_5=\gamma_4$, $\alpha_1=\lambda_1$, 
$\alpha_2=\lambda_2$, 
$\beta_1=\beta_3$, $\beta_2=\beta_4$ and $\alpha_4=\lambda_4$, 
from (4.5),%(\ref{Eq-puzzle-ineq-dark}), 
and $\nu_1=\gamma_1$, $\alpha_5=\alpha_3$, $\beta_5=\mu_5$ 
and $\gamma_2=\gamma_3$, 
from (4.6).%(\ref{Eq-puzzle-ineq-light}). 
The degrees of freedom 
are thereby greatly reduced, as shown in the following diagram:

\begin{center}
\scalebox{0.6}{\input{h_lr_fact_labels_equal.pstex_t}}
\end{center}

In this example, it is not difficult to see that the corridors, 
that is the shaded parallelograms, 
are completely redundant, and that the enumeration of all possible large LR-hives 
is accomplished by enumerating pairs of small LR-hives corresponding to the diagrams:

\begin{center}
\scalebox{0.6}{\input{h_lr_factors_labels.pstex_t}}
\end{center}
 
\noindent
This proves the factorisation of not only the corresponding Littlewood--Richardson 
coefficients, but also the corresponding LR-polynomials, since simultaneous 
stretching of the partitions, $\lambda$, $\mu$ and $\nu$, always preserves the 
saturation of the Horn inequality.  

An explicit illustration of the above factorisation is provided by the case 
$\lambda=(9,7,6,2,0)$, $\mu=(13,5,3,1,0)$ and $\nu=(14,12,11,5,4)$
for which $\lambda_I=(9,7,2)$, $\mu_J=(5,3,1)$ and $\nu_K=(12,11,4)$ with 
$\lambda_{\overline I}=(6,0)$, $\mu_{\overline J}=(13,0)$ and $\nu_{\overline K}=(14,5)$.
In this case
\begin{equation}
c_{9762,13\,531}^{14\,12\,11\,54}
=c_{972,531}^{12\,11\,4}\ c_{6,13}^{14\,5} = 2\cdot1 = 2,
\label{Eq-c-fact}
\end{equation}
while 
\begin{equation}
P_{9762,13\,531}^{14\,12\,11\,54}(t)
=P_{972,531}^{12\,11\,4}(t)\ P_{6,13}^{14\,5}(t) = (t+1)\cdot1 = t+1.
\label{Eq-P-fact}
\end{equation}

More generally, to complete the proof of the Conjecture~\ref{Conj-LRfact} 
it is necessary to show that the corridors $R_n$ of an LR-hive, $H_n$, are redundant;
that the removal of $R_n$ yields dark rooms and light rooms
that constitute LR-hives $H_r$ and $H_{n-r}$, respectively; and that any LR-hives
$H_r$ and $H_{n-r}$ that are first subdivided and then joined by corridors $R_n$ 
constitute some LR-hive $H_n$. 

The redundancy of the corridors is rather easily established by showing that the 
corresponding Horn equality is sufficient to ensure that all their 
interior edge labels are fixed by those on their boundary.
It is then not difficult to show that the LR hive conditions for $H_n$ imply the
validity of the LR hive conditions for any rhombus of either $H_r$ or $H_{n-r}$
that is split by a corridor in $H_n$. To complete the proof it is necessary 
to show, conversely, that the LR hive conditions of $H_r$ and $H_{n-r}$
are sufficient to imply the LR hive conditions of $H_n$ for
all rhombi that are split by a redundant corridor. It is believed that this
may be accomplished, under the hypotheses of the Conjecture, by a generalisation
of the arguments used elsewhere~\cite{KTT2} in proving factorisation of
some Kostka coefficients. However, in the present context, it should be 
noted that the required result is not true in the case of all rhombi of $H_n$ that
are split by a redundant corridor arising from a puzzle associated with 
the saturation of an inessential Horn inequality.
This is connected with the fact that in such cases the puzzle 
itself is not unique~\cite{KTW}.
It is for this reason that the Conjecture~\ref{Conj-LRfact}
applies only to the saturation of an essential Horn inequality, for which the
corresponding puzzle is known to be unique~\cite{KTW}, and the corresponding
Littlewood--Richardson coefficient is not primitive. 

\section{Degrees of stretched polynomials}

Even given a certain amount of factorisation that reduces
the evaluation of stretched Littlewood--Richardson polynomials 
to that of calculating these LR-polynomials in the primitive case,
their evaluation may be combinatorially formidable. In any given case 
a knowledge of the degree of the polynomial would be extremely
advantageous. Here we establish an upper bound on this degree by means
of the following rather innocuous looking observation.

Taking $\alpha=\gamma$ in each of the 5-vertex diagrams encountered
earlier, gives 

\begin{center}
\scalebox{0.6}{\input{h_5v3equal.pstex_t}}
\end{center}

\noindent
In each case the rhombus constraints give $\alpha\geq\beta\geq\alpha$
so that we must have $\beta=\alpha$. This result can be displayed
more simply by suppressing all the labels on the vertices of the hives
and inserting an edge between pairs of vertices whose labels differ
by the same integer $\alpha$.  This gives the diagrams:

\begin{center}
\scalebox{0.6}{\input{h_5v3skel.pstex_t}}
\end{center}

\noindent
where in each case the equality of neighbouring differences $\alpha$ 
in a linear sequence of three vertices forces an identical difference
$\alpha$ between two vertices in the neighbouring line. 

Applying these notions to our LR-hives 
with boundaries of length $n$ and with border labels
determined by $\lambda$, $\mu$ and $\nu$, it follows from the above
that any equalities of successive parts of these partitions propagate 
as equalities of differences in hive entries within each LR-hive. 
To be more precise let all the $\lambda$-boundary edges be labelled
by the parts of $\lambda$. If any sequence of parts of
$\lambda$ share the same value, say $\alpha$, 
then we can identify an equilateral 
sub-hive having the sequence of equally labelled edges as 
one boundary, with its other boundaries parallel to the 
$\mu$ and $\nu$-boundaries of the original hive. 
Within this sub-hive all the vertices 
along lines parallel to the $\lambda$-boundary are to be 
connected by edges indicating that in any LR-hive the differences 
in values between neighbouring entries along these lines are all $\alpha$.
This process is to be repeated first for all sequences of equal edge
labels along the $\lambda$-boundary, and then for all 
sequences of equal edge labels along the $\mu$ and $\nu$ boundaries.  

In some cases it will be found that some sequence of equal edge labels,
say $\alpha$ parallel to the $\lambda$-boundary, will intersect some 
sequence of equal edge labels, say $\beta$ parallel to the $\mu$-boundary. 
In such a case, by virtue of the condition $\alpha+\beta=\gamma$ that applies 
to each of the triangles 
\begin{center}
\scalebox{0.6}{\input{h_lr_triangle.pstex_t}}
\end{center}
there must exist sequences of equal edge labels $\gamma=\alpha+\beta$
parallel to the $\nu$-boundary. Depending on the lengths of the intersecting
$\alpha$ and $\beta$ sequences, either a triangular or a quadrilateral region
will be formed in which each edge label is either $\alpha$, $\beta$ or $\gamma$.
By virtue of the previous arguments, any sequence of equal edge labels $\gamma$
on the boundary of such a region will give rise to a further triangular
region traversed by equal edge labels $\gamma$. This is exemplified by:
\begin{center}
\scalebox{0.6}{\input{h_lr_skel_abc.pstex_t}}
\end{center}
Clearly, different orientations of such regions may occur and there may be
several such intersections with which one has to contend. However, the process 
of equal edge identification will terminate. Finally, when this has happened,
one connects with edges all neighbouring vertices on all three 
boundaries of the hive. In this way we arrive at a 
skeletal graph $G_{n;\lambda\mu\nu}$ of the hive. 

%For example, for $n=6$, $\lambda=(4,3,3,1,0,0)$,
%$\mu=(4,2,1,1,1,0)$ and $\nu=(6,5,4,2,2,1)$
%we have

In the case of the example quoted in the Introduction,
we have $n=7$, $\lambda=(4,3,3,2,1,0,0)$,
$\mu=(4,3,2,2,1,0,0)$ and $\nu=(7,4,4,4,3,2,1)$, and 
the corresponding skeletal graph $G_{n;\lambda\mu\nu}$ 
takes the form:

\begin{center}
\scalebox{0.6}{\input{h_lr_skel_ex14.pstex_t}}%NTB example 14
\end{center}

The importance of such skeletal graphs is that they
indicate constraints on LR-hive entries that are 
implied by the specification of the boundary
labels. These constraints on the interior vertex labels
reduce the total number of degrees of freedom of such
labels. This leads to the following: 
\begin{proposition}
\label{Prop-LR-degree}
Let $\lambda$, $\mu$ and $\nu$ be partitions such that
$c_{\lambda\mu}^\nu>0$. 
Let $\deg(P(t))$ be the degree of 
the corresponding stretched LR-polynomial 
$P(t)=c_{t\lambda,t\mu}^{t\nu}$.
Let $\d(G_{n;\lambda\mu\nu})$ be the number of connected 
interior components of the graph $G_{n;\lambda\mu\nu}$ that
are not connected to the boundary.
Then 
\begin{equation}
      \deg(P(t))\leq \d(G_{n;\lambda\mu\nu}).
\label{Eq-LR-degree}
\end{equation}
\end{proposition}

\begin{proof}
The application of the stretching parameter $t$ leaves
$G_{n;\lambda\mu\nu}$ unaltered, so that the number
of degrees of freedom in assigning entries to the stretched
LR-hives is still $d(G_{n;\lambda\mu\nu})$. For each 
interior connected component that is not connected to the boundary we
can select any one convenient vertex. The value $a_{ij}$
of each such selected interior vertex label may 
or may not be fixed by the hive constraints. 
However, it will be subject to linear inequalities 
of the form $p\leq a_{ij}\leq q$ arising from 
the hive conditions. As the boundary vertex and edge labels are 
scaled by $t$, then all the parameters specifying these linear 
inequalities are also scaled by $t$ to give $tp\leq a_{ij}\leq tq$.
Hence, in enumerating all possible
LR-hives in the stretched case, the freedom in
assigning $a_{ij}$ gives rise
to a contribution to $P_{\lambda\mu}(t)$ that is
at most linear in $t$. It follows that the degree
of this polynomial is at most $d(G_{n;\lambda\mu\nu})$.
\end{proof}
 
Unfortunately, the intersection of sequences of equal edges that arise
from equal parts in $\lambda$, $\mu$ and $\nu$ and the resulting 
new interior sequences of equal edges make it difficult to arrive 
at an explicit formula for $\d(G_{n;\lambda\mu\nu})$.

In the above example for $n=7$ with $\lambda=(4,3,3,2,1,0,0)$,
$\mu=(4,3,2,2,1,0,0)$ and $\nu=(7,4,4,4,3,2,1)$ we have 
$\d(G_{n;\lambda\mu\nu})=8$. The corresponding
LR-polynomial $P_{\lambda\mu}^\nu(t)$ is given 
explicitly in (\ref{Eq-Pol-ex}), and can be seen to have 
degree $8$. Thus, in the case of this example, the 
above bound (\ref{Eq-LR-degree}) on the polynomial degree is saturated.

Similarly, in the case $n=6$ and $\lambda=(7,6,5,4,0,0)$,
$\mu=(7,7,7,4,0,0)$ and $\nu=(12,8,8,7,6,4,2)$, the graph 
$G_{n;\lambda\mu\nu}$ takes the form:

\begin{center}
\scalebox{0.6}{\input{h_lr_skel_ex13.pstex_t}}%NTB example 13
\end{center}

As can be seen, there are 5 connected interior components of the above graph
that are not connected to the boundary.
It follows that $\d(G_{n;\lambda\mu\nu})=5$. 
It can be checked that in the case of this example
$c_{\lambda\mu}^\nu=12$ and~\cite{NTB}:
\begin{equation}
P_{\lambda\mu}^\nu(t)=\frac{1}{30}(t+1)(t+2)(t+3)(3t^2+7t+5)\,.
\label{Eq-Pol-ex13}
\end{equation}
Thus once again we have $\deg(P_{\lambda\mu}^\nu(t))=d(G_{n;\lambda\mu\nu})$.

On the other hand, in the case $n=5$ and $\lambda=(9,7,3,0,0)$,
$\mu=(9,9,3,2,0)$ and $\nu=(10,9,9,8,6)$, the graph $G_{n;\lambda\mu\nu}$
takes the form:

\begin{center}
\scalebox{0.6}{\input{h_lr_skel_ex1.pstex_t}}%NTB example 1
\end{center}

This time there are 3 connected interior components that are not connected
to the boundary. Hence $\d(G_{n;\lambda\mu\nu})=3$. 
However, in this case it is found that $c_{\lambda\mu}^\nu=2$ 
and $P_{\lambda\mu}^\nu(t)=t+1$. 
Hence $\deg(P_{\lambda\mu}^\nu(t))<d(G_{n;\lambda\mu\nu})$.
However, this case is not primitive. The corresponding hives
factorise:

\begin{center}
\scalebox{0.6}{\input{h_lr_factors_ex1.pstex_t}}
\end{center}

\noindent
leading to a corresponding factorisation of the LR-polynomial:
\begin{equation}
P_{97300,99320}^{10\,9986}(t)
=P_{970,920}^{10\,98}(t)\ P_{3,3}^6(t)\ P_{0,9}^9(t)=(t+1)\cdot1\cdot1=t+1.
\label{Eq-3factors}
\end{equation}

Encouraged by these results, and many other examples, we conjecture
that in the primitive case the bound in Proposition~\ref{Prop-LR-degree}
is saturated, and that this is true only in such cases. That is we have:

\begin{conjecture}
If $c_{\lambda\mu}^\nu$ is primitive and
$P_{\lambda\mu}^\nu(t)=c_{t\lambda,t\mu}^{t\nu}$
then
\be
  \deg(P(t))=d(G_{n;\lambda\mu\nu}),
\ee
and conversely, if $\deg(P_{\lambda\mu}^\nu(t))<d(G_{n;\lambda\mu\nu})$
then $c_{\lambda\mu}^\nu$ is not-primitive. 
\label{Saturated}
\end{conjecture}

\section{Linear factors}

It will have been noted that in our illustrative examples 
(\ref{Eq-Pol-ex}) and (\ref{Eq-Pol-ex13}) the
stretched Littlewood--Richardson polynomials $P_{\lambda\mu}^\nu(t)$
contain factors $(t+m)$ for some sequence of values $m=1,2,\ldots,M$
for some positive integer $M$. This is no accident since
$P_{\lambda\mu}^\nu(t)$ is nothing other than an Ehrhart quasi-polynomial
$i({\cal P},t)$ of a rational complex polytope ${\cal P}$ defined by 
the set of linear inequalities corresponding to the LR-hive conditions.
This quasi-polynomial is actually a polynomial~\cite{DW2,R}, 
but whether this is the case or not, the reciprocity
theorem for Ehrhart quasi-polynomials~\cite{S} states that 
$i({\cal P},t)$ is defined for all integers $t$ and that for $t=-m$
with $m$ a positive integer 
$i({\cal P},-m)=(-1)^d\,\ov{i}({\cal P},m)$, where $d$ is the dimension
of the polytope ${\cal P}$, and $\ov{i}({\cal P},m)$ is the number of 
integer points inside $m{\cal P}$. This number of integer points may
be zero, thereby giving rise to a zero of $P(t)=i({\cal P},t)$ at 
$t=-m$. Moreover, if this number is zero for $m=M$ and non-zero
for $m=M+1$ it follows from its geometric interpretation that
it is zero for $m=1,2,\ldots,M$ and non-zero for all $m>M$. In such
a case $P_{\lambda\mu}^\nu(t)$
 necessarily contains $(t+1)(t+2)\cdots(t+M)$ as a 
factor. 

In this section we describe one particular approach to the
determination of $M$, based on a conjecture regarding the
continuation of $P_{\lambda\mu}^\nu(t)$ to negative integer
values $t=-m$. For $t$ a positive integer, we certainly have 
\be
s_{t\lambda}(x_1,x_2,\ldots,x_n)
      =\frac{\left| x_i^{t\lambda_j+n-j}\right|}
        {\left| x_i^{n-j}\right|}.
\label{S-tdet}
\ee
This may be readily extended to the case $t=-m$ with 
$m$ a positive integer, to give 
\be
s_{-m\lambda}(x_1,x_2,\ldots,x_n)
      =\frac{\left| x_i^{-m\lambda_j+n-j}\right|}
        {\left| x_i^{n-j}\right|}
      =\frac{\left| x_i^{-m\lambda_{n-k+1}-n+k}\right|}
        {\left| x_i^{-n+k}\right|}, 
\label{S-mdet}
\ee
where first $x_i^{n-1}$ has been extracted as a common
factor from the $i$th row of each determinant for $i=1,2,\ldots,n$
and cancelled from numerator and denominator, and then
$j$ replaced by $k=n-j+1$ with an appropriate reversal of order
of the columns in both determinants. 
If we now set $\ov{x}_i=x_i^{-1}$ for $i=1,2,\ldots,n$, 
this gives 
\be
s_{-m\lambda}(x_1,x_2,\ldots,x_n)
    =\frac{\left| \ov{x}_i^{m\lambda_{n-k+1}+n-k}\right|}
        {\left|\ov{x}_i^{n-k}\right|}
 =s_{m\lambda_n,\ldots,m\lambda_2,m\lambda_1}
 (\ov{x}_1,\ov{x}_2,\ldots,\ov{x}_n).
\label{s-mlambda}
\ee
To simplify the notation, for any partition 
$\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_n)$
let $\tilde\lambda=(\lambda_n,\ldots,\lambda_2,\lambda_1)$
be the vector obtained by reversing the order of its parts.
Then reverting to the indeterminates $\x=(x_1,x_2,\ldots,x_n)$
we have:
\be
s_{m\tilde{\lambda}}(\x)=
s_{m\lambda_n,\ldots,m\lambda_2,m\lambda_1}(x_1,x_2,\ldots,x_n)
=\frac{\left| x_i^{m\lambda_{n-k+1}+n-k}\right|}
        {\left|x_i^{n-k}\right|}.
\label{S-m}
\ee
This allows us to make the following definition, which amounts 
to an extension of stretched Littlewood--Richardson coefficients to the
domain of a negative stretching parameter $t=-m$:

\begin{definition}
For any $\lambda$, $\mu$ and $\nu$ such that $c_{\lambda\mu}^\nu>0$,
let $c_{-m\lambda,-m\mu}^{-m\nu}
=c_{m\tilde{\lambda},m\tilde{\mu}}^{m\tilde{\nu}}$,
for any positive integer $m$,
where
\begin{equation}
  s_{m\tilde{\lambda}}(\x)\ s_{m\tilde{\mu}}(\x)
  =\sum_{\nu} c_{m\tilde{\lambda},m\tilde{\mu}}^{m\tilde{\nu}}\
     s_{m\tilde{\nu}}(\x).
\label{Eq-sfprod-m}
\end{equation}
\label{Def-c-neg}
\end{definition}

It transpires that in the following we need to refine the notion
of primitivity. If $c_{\lambda\mu}^\nu>0$ is not only primitive
but satisfies the stronger constraint that {\it all} the Horn
inequalities, both essential and inessential, are strict inequalities, then
$c_{\lambda\mu}^\nu$ is said to be {\it simple}.

With this definition, the consideration of numerous examples,
suggests the validity of the following:

\begin{conjecture}
\label{Conj-LR-neg}
Let $c_{\lambda\mu}^\nu>0$ be simple and let
the corresponding LR-polynomial be $P_{\lambda\mu}^\nu(t)$.
Then the value of this LR-polynomial at negative integer
values $t=-m$ coincides with the corresponding negatively stretched
Littlewood--Richardson coefficients, that is to say
\begin{equation}
   P_{\lambda\mu}^\nu(-m)=c_{-m\lambda,-m\mu}^{-m\nu}.
\label{Eq-LR-neg}
\end{equation}
\end{conjecture}

To exploit this it is necessary that Schur functions such as 
$s_{m\tilde{\lambda}}(\x)$, as defined by (\ref{S-m}),
be standardised. This may be carried out 
by reordering the columns of the numerator determinant. 
However there are two quite different possible outcomes:
either $s_{m\tilde{\lambda}}(\x)=0$ or 
$s_{m\tilde{\lambda}}(\x)=\eta_\rho\,s_{\rho}(\x)$
for some partition $\rho$ with $\eta_\rho=\pm1$. 
Similar results apply to $s_{m\tilde{\mu}}(\x)$
and $s_{m\tilde{\nu}}(\x)$. The validity of the
above conjecture would then imply that
\be
  P_{\lambda\mu}^\nu(-m)= \eta_{\lambda\mu}^\nu
    c_{\rho\sigma}^\tau
\label{Eq-PmC}
\ee
where $\eta_{\lambda\mu}^\nu=0$ if any one of 
$s_{m\tilde{\lambda}}(\x)$, $s_{m\tilde{\mu}}(\x)$
or $s_{m\tilde{\nu}}(\x)$ is identically zero,
and is $\pm1$ in all other cases, while
$\rho$, $\sigma$ and $\tau$ are defined by
the identities $s_{m\tilde{\lambda}}(\x)=\eta_\rho\,s_{\rho}(\x)$, 
$s_{m\tilde{\mu}}(\x)=\eta_\sigma\,s_{\sigma}(\x)$ and
$s_{m\tilde{\nu}}(\x)=\eta_\tau\,s_{\tau}(\x)$.

It follows that we can expect two types of zero of $P_{\lambda\mu}^\nu(t)$
for $t=-m$: type (i) associated with $\eta_{\lambda\mu}^\nu=0$ and
type (ii) associated with the vanishing of $c_{\rho\sigma}^\tau$.

To see this in an example consider the case $n=7$, $\lambda=(4,3,3,2,1)$,
$\mu=(4,3,2,2,1)$ and $\nu=(7,4,4,4,3,2,1)$ for which
$c_{\lambda\mu}^\nu$ is simple, and 
$P(t)=P_{\lambda\mu}^\nu(t)$ has already been given in (\ref{Eq-Pol-ex}). 
Here we find that $s_{m\tilde\lambda}(\x)=0$ for $m=1,2$,
$s_{m\tilde\mu}(\x)=0$ for $m=1,2$ and
$s_{m\tilde\nu}(\x)=0$ for $m=1,2,3$. This accounts for the 
three zeros associated with the factors $(t+1)$, $(t+2)$
and $(t+3)$. For all $m\geq4$ we have 
$s_{m\tilde\lambda}(\x)=s_{\rho}(\x)$, 
$s_{m\tilde\mu}(\x)=s_{\sigma}(\x)$ and 
$s_{m\tilde\nu}(\x)=s_{\tau}(\x)$ for some partitions 
$\rho$, $\sigma$ and $\tau$.
It then remains to be seen whether or not $c_{\rho\sigma}^\tau=0$.

Starting with $m=4$ it is found that $\rho=(10,9,9,8,6,5,5)$,
$\sigma=(10,8,7,7,6,5,5)$ and $\tau=(22,14,14,14,14,12,10)$.
Since $\rho_1+\sigma_1=20<22=\tau_1$ it follows that
$c_{\rho\sigma}^\tau=0$. This accounts for a factor of 
$(t+4)$ in $P(t)$.
Similarly with $m=5$ it is found that $\rho=(14,12,12,10,7,5,5)$,
$\sigma=(14,12,9,9,7,5,5)$ and $\tau=(29,18,18,18,17,14,11)$.
This time since $\rho_1+\sigma_1=28<29=\tau_1$ it again
follows that
$c_{\rho\sigma}^\tau=0$, thereby accounting for a factor of 
$(t+5)$ in $P(t)$.
On the other hand for $m=6$ it is found that $\rho=(18,15,15,12,8,5,5)$,
$\sigma=(18,14,11,11,8,5,5)$ and $\tau=(36,22,22,22,20,16,12)$.
This time it is found that 
$c_{\rho\sigma}^\tau=3$. This implies that there is no factor
$(t+6)$ in $P(t)$. Indeed it is easy to check from (\ref{Eq-Pol-ex})
that $P(-6)=3$. In the same way we can derive the fact that
$P(-7)=39$ and $P(-8)=247$, in perfect agreement 
with (\ref{Eq-Pol-ex}).

Although Conjecture~\ref{Conj-LR-neg} cannot be extended as it
stands to cover all primitive cases, both simple and non-simple,
numerous examples lead us to

\begin{conjecture}
If $c_{\lambda\mu}^\nu>0$ is primitive, then the LR-polynomial 
$P_{\lambda\mu}^\nu(t)=c_{t\lambda,t\mu}^{t\nu}$ 
contains a factor $(t+m)$ if and only if either 
$\eta_{\lambda\mu}^\nu=0$ or $c_{\rho\sigma}^\tau=0$.
\label{Conj-LRzeros}
\end{conjecture} 

It can be shown that for sufficiently large $m$ both
$\eta_{\lambda\mu}^\nu$ and $c_{\rho\sigma}^\tau$
in (\ref{Eq-PmC}) are positive, provided that the original 
$c_{\lambda\mu}^\nu$ is primitive. Moreover, it
can be shown in such a case that if 
$\eta_{\lambda\mu}^\nu c_{\rho\sigma}^\tau=0$
for some positive integer $m$, then the same is true for
all smaller positive integers. This means that it is
possible to identify $M$ such that the right hand side
of (\ref{Eq-PmC}) is zero for all $m\leq M$ and non-zero
for all $m>M$. This is entirely consistent with the
remarks made at the beginning of this section regarding 
the zeros of Ehrhart quasi-polynomials. 

As a final conjecture we offer

\begin{conjecture}
Let $\lambda$, $\mu$ and $\nu$ be partitions such that
$c_{\lambda\mu}^\nu>0$. Then $c_{\lambda\mu}^\nu$
is primitive if and only if 
$c_{-m\lambda,-m\mu}^{-m\nu}$ is non-zero
for some positive integer $m$.
\label{Prop-strictHorn}
\end{conjecture}


\begin{thebibliography}{999999}


\bibitem[BZ1]{BZ1}
A.D. Berenstein and A.V. Zelevinsky,
{\it When is the multiplicity of a weight equal to 1?},
Funct. Anal. Appl. {\bf 24} (1990), 259--269.

\bibitem[BZ2]{BZ2}
A.D. Berenstein and A.V. Zelevinsky,
{\it Triple multiplicities for $sl(r+1)$ and the spectrum
of the exterior algebra of the adjoint representation},
J. Alg. Comb. {\bf 1} (1992), 7--22.

\bibitem[B]{B}
A.S. Buch,
{\it The saturation conjecture (after A. Knutson and T. Tao). With
an appendix by W. Fulton},
Enseign. Math. {\bf 46} (2000), 43--60.

\bibitem[DK]{DK}
V.I. Danilov and G.A. Koshevoy,
{\it Diskretnaya vognutost' i ermitovy matritsy},
Trudy Math. Inst. Steklova {\bf 241} (2003), 68--90,
in Russian. Title translation: 
{\it Discrete convexity and Hermitian matrices}.

 
\bibitem[DW1]{DW1}
H. Derksen and J. Weyman,
{\it Semi-invariants of quivers and saturation for
Littlewood--Richardson coefficients},
J. Amer. Math. Soc. {\bf 13} (2000), 467--479.

\bibitem[DW2]{DW2}
H. Derksen and J. Weyman,
{\it On the Littlewood--Richardson polynomials},
J. Algebra. {\bf 255} (2002), 247--257.

\bibitem[H]{H}
A. Horn,
{\it Eigenvalues of sums of Hermitian matrices},
Pacific J. Math. {\bf 12} (1962), 225--241.

\bibitem[F]{F}
W. Fulton,
{\it Eigenvalues, invariant factors, highest weights, and Schubert calculus},
Bull. Amer. Math. Soc. {\bf 37} (2000), 209--249.

\bibitem[KTT1]{KTT1}
R.C. King, C. Tollu and F. Toumazet,
{\it Stretched Littlewood--Richardson and Kostka coefficients},
CRM Proceedings and Lecture Notes, Vol. 34, 
Amer. Math. Soc, 2004, pp.~99--112.

\bibitem[KTT2]{KTT2}
R.C. King, C. Tollu and F. Toumazet,
{\it The hive model and the factorisation of Kostka coefficients},
Proc. FPSAC'05, 2005.

\bibitem[K]{K}
A.A.Klyachko,
{\it Stable bundles, representation theory and Hermitian operators},
Selecta Math. New Ser. {\bf 4} (1998), 419--445.

\bibitem[KT]{KT}
A. Knutson and T. Tao,
{\it The honeycomb model of $GL_n(\C)$ tensor products. I: Proof 
of the saturation conjecture},
J. Amer. Math. Soc. {\bf 12} (1999), 1055--1090.

\bibitem[KTW]{KTW}
A. Knutson, T. Tao and C. Woodward,
{\it The honeycomb model of $GL_n(\C)$ tensor products. II: Puzzles
determine facets of the Littlewood--Richardson cone},
J. Amer. Math. Soc. {\bf 17} (2004), 19--48.

\bibitem[LR]{LR}
D.E. Littlewood and A. Richardson,
{\it Group characters and algebra},
Phil. Trans. Roy. Soc. London A {\bf 233} (1934), 99--141.

\bibitem[NTB]{NTB}
J. Nzeutchap, F. Toumazet and F. Butelle,
{\it Kostka numbers and Littlewood--Richardson coefficients:
distributed computation},
in {\it Proceedings of the Brian Wybourne Commemorative Meeting},
Eds: R.C.King, J. Karwowski and M. Bylicki, to appear.

\bibitem[R]{R}
E. Rassart,
{\it A polynomial property of Littlewood--Richardson coefficients},
J Comb. Theo. Ser. A {\bf 107} (2004), 161--179.

\bibitem[S]{S}
R.P. Stanley,
{\it Enumerative Combinatorics}, Vol. I,
Cambridge University Press, Cambridge, 1999.

\end{thebibliography}

\end{document}

