\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\y{{\bf y}}
\def\z{{\bf z}}
\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\R{R\!\!\!R}
\def\Z{Z\!\!\!Z}
\def\Ra{\Rightarrow}
\def\wgt{{\rm wgt}\,}


%	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}

%	Some more definitions

%\def\c1{\ \bullet\ }

\def\Z{{\mathbb Z}}
\def\C{{\mathbb C}}
\def\R{{\mathbb R}}
\def\cal{\mathcal}

\begin{document}

\title[The hive model and the factorisation of Kostka coefficients]
{The hive model and the \\ factorisation of Kostka coefficients} 
%\thanks{Research of TAW partially supported by the
%        Australian Research Council (ARC)}
%\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@maths.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
Kostka coefficients and stretched Kostka coefficient polynomials.
It is shown that both of these may factorise, and 
that they can then be expressed as products of certain primitive 
coefficients and polynomials, respectively. It is further shown
how to determine a sequence of linear factors $(t+m)$ of the
primitive polynomials, where $t$ is the stretching parameter, 
as well as a bound on their degree in the form of a simple
formula which is conjectured to be exact.

\medskip

\noindent 
{\sc R\'esum\'e}. Nous utilisons le mod\`ele des ruches pour \'etudier les
propri\'et\'es des c{\oe}fficients  de Kostka et des polyn\^omes
associ\'es aux c{\oe}fficients de Kostka dilat\'es. Nous montrons que
les uns et les autres peuvent se factoriser : ils 
s'\'ecrivent comme des produits de c{\oe}fficients (respectivement polyn\^omes)
primitifs. En outre, nous montrons comment \'etablir une suite de
facteurs lin\'eaires $(t+m)$ des polyn\^omes primitifs ($t$ est le
param\`etre de dilatation), et proposons une formule simple donnant 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~B54Ah\hfill}
\def\thepage{}
%
%

\section{Introduction}

There is no doubt that Kostka coefficients, $K_{\lambda\mu}$ are
interesting combinatorial objects. 
They are indexed by pairs of partitions $\lambda$ and
$\mu$, and are non-zero if and only if these partitions have the same weight
and $\lambda$ precedes $\mu$ with respect to the dominance partial order on 
partitions~\cite{JK}. 
They count the number of semistandard Young tableaux of shape
determined by $\lambda$ and of weight determined by $\mu$, see for 
example~\cite{L,M,S2}. 
They also count Gelfand-Tsetlin patterns, as described for example
in~\cite{GT,S2}. These patterns are in bijective correspondence
with semistandard Young tableaux and also with certain K-hives, introduced
comparatively recently~\cite{KTT1} as a variation on the hives used to
calculate Littlewood-Richardson coefficients~\cite{KT,KTW,B}.
These K-hives are triangular arrays of non-negative integers with
borders 
of length $n$ labelled by the parts of the partitions $0$, $\lambda$ and $\mu$,
where $0=(0,0,\ldots,0)$. Counting such K-hives gives $K_{\lambda\mu}$. 

Multiplying all the parts of the partitions $\lambda$ and $\mu$ by
a stretching parameter $t$, with $t$ a positive integer, gives new partitions
$t\lambda$ and $t\mu$. Since the weights of $t\lambda$ and $t\mu$
are simply those of $\lambda$ and $\mu$ multiplied by $t$, and this scaling
preserves dominance partial ordering, it follows that $K_{t\lambda,t\mu}$
is non-zero if and only if $K_{\lambda\mu}$ is non-zero. 

By way of a non-trivial example, for $n=9$, $\lambda=(9,5,2,2,2,2,1)$
and 
$\mu=(5,5,5,3,1,1,1,\break1,1)$ it
is found quite typically that
\be
    K_{t\lambda,t\mu}=\frac{1}{24}(t+1)^2(t+2)(5t+2)(t^2+3t+6)
\label{Eq-Ex1}
\ee

These functions $K_{t\lambda,t\mu}$ are necessarily quasi-polynomials
in $t$ since they enumerate integer points of rational polytopes subject
to a scaling by $t$~\cite{E,S1}. However, contrary
to initial expectations~\cite{BK}, these rational polytopes may,
and indeed sometimes do, 
possess non-integral vertices~\cite{KTT1,DeLM}. Despite
this, it has been proved~\cite{KR,K1,BGR} that $P_{\lambda\mu}(t)=K_{t\lambda,t\mu}$
is always a polynomial in $t$.
      
A study of such K-polynomials has revealed a number of interesting 
features that are illustrated in the above example. 
In particular, it appears that the coefficients in the expansion of
$P_{\lambda\mu}(t)$ 
are all positive rational numbers. This remains a conjecture~\cite{KTT1}. 

Secondly, $P_{\lambda\mu}(t)$ often contains a sequence of factors $(t+m)$
for $m=1,2,\ldots,M$, with $M$ some non-negative integer. 
In the above example $M=2$. More generally, both the value of $M$
and the degree, $d$ of the K-polynomial appear to be difficult to predict
from a knowledge of $n$, $\lambda$ and $\mu$. 
Although the hive model does give an immediate bound, $d\leq(n-1)(n-2)/2$,
on the degree, it can be seen in the above $n=9$ example 
that we have $d=6$, so that the bound is far from being saturated.

It is also found that under certain circumstances there exists
a factorisation of the form
\be
      P_{\lambda\mu}(t)= P_{\sigma\zeta}(t)\ P_{\tau\eta}(t)
\label{Eq-Pfact}
\ee 
for some $\sigma$, $\tau$, $\zeta$ and $\eta$ such that 
$\lambda=(\sigma,\tau)$ and $\mu=(\zeta,\eta)$, where the notation
is intended to signify that the list of parts of $\lambda$ are simply those
of $\sigma$ followed by those of $\tau$, and similarly for $\mu$.
In the above example we have 
$P_{9522221,555311111}(t)= P_{9522,5553}(t)\ P_{221,11111}(t)$ with
\be
P_{9522,5553}(t)     %=P_{73,3331}(t)
=\frac{1}{2}(t+1)(5t+2)
\ \mbox{ and }\ 
P_{221,11111}(t)=\frac{1}{12}(t+1)(t+2)(t^2+3t+6).
\label{Eq-Ex2}
\ee

%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 
THE HIVE MODEL AND THE FACTORISATION OF KOSTKA COEFFICIENTS}
%
%

In this presentation, our intention is to exploit the hive model
to study the properties of stretched Kostka coefficient
polynomials. We first derive combinatorially the precise conditions
under which such K-polynomials factorise as products of
certain primitive K-polynomials. In the case of any primitive
K-polynomial we then show how to determine the precise range of values,
$1\leq m\leq M$, such that the K-polynomial contains a factor $(t+m)$.
This is done by giving an interpretation of $P_{\lambda\mu}(t)$
for negative integer values of $t$. Finally, we obtain a formula
for an explicit bound on the degree $d$ of a primitive K-polynomial
which we conjecture is always saturated. 

Our analysis covers
not only the Kostka coefficients $K_{\lambda\mu}$ and the
K-polynomials $P_{\lambda\mu}(t)$ in which $\mu$ is 
a partition, but also $K_{\lambda\beta}$ and $P_{\lambda\beta}(t)$
in which $\beta$ is, more generally, a weight. The combinatorial
proof of the factorisation theorem in this case is presented in
an Appendix.

  
\section{Kostka coefficients}

Let $n$ be a fixed positive integer. For any 
$\alpha=(\alpha_1,\ldots,\alpha_n)\in \mathbb{Z}^n$ let 
$| \alpha | = \alpha_1+\cdots+ \alpha_n$ be the weight of $\alpha$,
let $\#\alpha=n$ be the number of components of $\alpha$ 
and let the symmetric group $S_n$ act naturally on the components of 
$\alpha$.
Let
$\lambda=(\lambda_1,\ldots,\lambda_n)$ be
a partition of length $\ell(\lambda)\leq n$ and weight $|\lambda|$
with $\lambda_1\geq\cdots\geq\lambda_n\geq 0$.
Then $|\lambda|=\lambda_1+\cdots+\lambda_n$ with $\lambda_i>0$ for 
$i\leq \ell(\lambda)$ and $\lambda_i=0$ for $i>\ell(\lambda)$.
It is sometimes convenient to write $\lambda$ in terms
of its distinct parts, that is to set
$\lambda=(\kappa_1^{v_1},\ldots,\kappa_m^{v_m})$ 
with $\kappa_1>\cdots >\kappa_m\geq 0$ and 
$v_j>0$ for $j=1,\ldots,m$. Then 
$|\lambda|=v_1\kappa_1 +\cdots+ v_m\kappa_m$ 
with $v_1 +\cdots+ v_m=n$, and $\ell(\lambda)=n$ if $\kappa_m>0$ and 
$\ell(\lambda)=n-v_m$ if $\kappa_m=0$.


\begin{definition}
Let $\mathbf{x} = (x_1,\ldots,x_n)$. Then to each partition $\lambda$
with $\ell(\lambda)\leq n$ there corresponds 
a Schur function $s_{\lambda}(\mathbf{x})$ defined by 
\be
s_{\lambda}(\mathbf{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{S-def}
\ee
\end{definition}

Since $s_{\lambda}(\mathbf{x})$ is a ratio of two alternants, it is a
symmetric polynomial in the components $x_1,\ldots,x_n$ of $\mathbf{x}$. 
Indeed, the Schur functions
$\{s_{\lambda}(\mathbf{x})\,|\,\ell(\lambda)\leq n\}$ constitute a 
linear basis of the algebra of symmetric polynomials in the set of
variables $\{x_1,\ldots,x_n\}$. 


\begin{definition}
The expansion of each Schur function in terms of monomials takes the form
\be
s_{\lambda}(\mathbf{x}) =
\sum_{\beta}K_{\lambda\beta}\mathbf{x}^{\beta},
\label{K-def}
\ee
where the summation is over all $\beta=(\beta_1,\ldots,\beta_n)$ and 
$\mathbf{x}^{\beta}= x_1^{\beta_1}\cdots x_n^{\beta_n}$. 
The coefficients $K_{\lambda\beta}$ are known as 
Kostka coefficients.
\end{definition}

The Schur functions defined by (\ref{S-def}) also have 
a combinatorial interpretation from which it is possible
to evaluate the Kostka coefficients.

Each partition $\lambda$ with $\ell(\lambda)\leq n$ specifies 
a corresponding Young diagram $F^{\lambda}$ of shape $\lambda$. 
This consists of 
$|\lambda|$ boxes arranged in $\ell(\lambda)$ left-adjusted rows 
of lengths $\lambda_1,\lambda_2,\ldots,\lambda_{\ell(\lambda)}$.
Furthermore, there exists a set, ${\cal T}^\lambda(n)$,
of semistandard tableaux $T$. Each such $T$ is a numbering
of the boxes of $F^\lambda$ with entries from $\{1,2,\ldots,n\}$
such that they are weakly increasing across rows and strictly 
increasing down columns. Any such $T\in {\cal T}^\lambda(n)$ is said to have 
weight $\wgt(T)=(\#1{\rm's}\in T,\#2{\rm's}\in T,\ldots,\#n{\rm's}\in T)$
where $\#k{\rm's}\in T$ is the number of entries $k$ in $T$ for
$k=1,2,\ldots,n$. 

Typically, for $n=3$ and $\lambda=(3,2,0)$ we have
\[
F^{32}\ =\quad
{\vcenter{\offinterlineskip
\halign{&\mystrut\vrule#&\mybox{\hss$\scriptstyle#$\hss}\cr
\hr{7}\cr
& && && &\cr
\hr{7}\cr
& && &\cr
\hr{5}\cr
}}}
\qquad
{\cal T}^{32}(3)\ni T\ =\quad
{\vcenter{\offinterlineskip
\halign{&\mystrut\vrule#&\mybox{\hss$\scriptstyle#$\hss}\cr
\hr{7}\cr
&1 &&1 &&3 &\cr
\hr{7}\cr
&2 &&3 &\cr
\hr{5}\cr
}}}
\label{FT}
\]
with $\wgt(T)=(2,1,2)$.

It can be shown from the definition (\ref{S-def}) that
\be
   s_\lambda(\mathbf{x})=\sum_{T\in{\cal T}^\lambda(n)}\
      x^{\wgt(T)}.
\label{Eq-sxT}
\ee
It then follows that we have:
\begin{property}~(see for example \cite[p.~191]{L}, 
\cite[p.~101]{M}.)~~
$K_{\lambda\beta}$ is the number of distinctly labelled semistandard 
tableaux $T\in{\cal T}^\lambda(n)$ of shape $F^\lambda$ and weight
$\wgt(T)=\beta$, that is to say with $\beta_k$ entries $k$ for 
$k=1,2,\ldots,n$.
\label{Prop-K}
\end{property}

The fact that $s_\lambda(\mathbf{x})$ is symmetric implies that
the coefficients $K_{\lambda\beta}$ are insensitive to 
the permutations of the components of $\beta$, that is they
possess:

\begin{property}
For all $w\in S_n$ we have
$K_{\lambda,w(\beta)}=K_{\lambda\beta}$,
and there must exist a partition $\mu$ such that
$w(\beta)=\mu$ for some $w\in S_n$, in which case 
$K_{\lambda\beta}=K_{\lambda\mu}$.
\label{Prop-Kw}
\end{property}

To specify those partitions $\lambda$ and weights $\beta$ for which 
$K_{\lambda\beta}$ is non-zero it is convenient to introduce the
notion of partial sums of the parts of partitions and weights, and 
the dominance partial order.

\begin{definition}
For any partition $\nu=(\nu_1,\nu_2,\ldots,\nu_n)$ and 
any weight $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)$, their 
partial sums are defined by
\be
ps(\nu)_i = \nu_1+\nu_2+\cdots+\nu_i \ \ 
\mbox{and} \ \
ps(\alpha)_i = \alpha_1+\alpha_2+\cdots+\alpha_i \ \ 
\mbox{for all}\ i=1,2,\ldots,n.
\ee
More generally, for any subset $I=\{i_1,i_2,\ldots,i_r\}$
of $N=\{1,2,\ldots,n\}$ of cardinality $\#I=r$ with $1\leq r\leq n$ let
\be
ps(\nu)_I =\nu_{i_1}+\nu_{i_2}+\cdots+\nu_{i_r}\ \
\mbox{and} \ \
ps(\alpha)_I = \alpha_{i_1}+\alpha_{i_2}+\cdots+\alpha_{i_r}.
\ee
\label{Def-ps}
\end{definition}

\begin{definition}
Given partitions $\lambda$ and $\mu$ of lengths 
$\ell(\lambda),\ell(\mu)\leq n$, then 
$\lambda$ is said to dominate $\mu$, and we write
$\lambda\succeq\mu$, or more precisely $\lambda\succeq_n\mu$,
if
\be
ps(\lambda)_i \geq ps(\mu)_i \ \ \mbox{  for all  }\ i=1,2,\ldots,n
\mbox{  and  } |\lambda|=|\mu|.
\ee
Moreover, $\lambda$ is said to strongly dominate $\mu$, and we 
write $\lambda\succ\mu$, or more precisely $\lambda\succ_n\mu$, 
if
\be
ps(\lambda)_i > ps(\mu)_i \ \ \mbox{  for all  }\ i=1,2,\ldots,n-1
\ \ \mbox{  and  }\ |\lambda|=|\mu|.
\ee
\label{Def-dom}
\end{definition}

We now have the following important condition for the
non-vanishing of Kostka coefficients:

\begin{theorem}\ Let $\lambda$ and 
$\mu$ be partitions of lengths $\ell(\lambda),\ell(\mu)\leq n$,
and let $N=\{1,2,\break\ldots,n\}$. Then 
\be
K_{\lambda\mu}>0 \ \Longleftrightarrow\ \lambda \succeq_n \mu 
\label{Klamu}
\ee
More generally, let $\lambda$ be a partition of length $\ell(\lambda)\leq n$
and let $\beta$ be a weight with $\#\beta=n$. Then
\be
K_{\lambda\beta}>0 \ \Longleftrightarrow\ |\lambda|=|\beta| 
\ \ \mbox{  and  }\ \ ps(\lambda)_i \geq ps(\beta)_I
\ \ \mbox{  for all  }\ I\subseteq N 
\ \mbox{  with  }\ i=\#I>0.    
\label{Klabeta}
\ee
\label{Theo-JK}
\end{theorem}

The first set of conditions (\ref{Klamu}) is well-known 
(see for example~\cite[p.~44]{JK}), and the second set of conditions
(\ref{Klabeta})
is a simple corollary following from the fact that if $\mu=w(\beta)$ for some 
$w\in S_n$ then
$ps(\mu)_i = ps(\beta)_I$ for some $I\subseteq N$ with $i=\#I$,
and $ps(\mu)_i\geq ps(\beta)_J$ for all $J\subseteq N$ with $i=\#J$. 

\section{The hive model}

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 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.

Although, for completeness, we have included hive conditions
for all three types of rhombus that appear in a general hive,
it is only the type R1 and R2 hive conditions that apply to what 
we call K-hives. For such K-hives the type R3 hive conditions
will, in general, be violated.
 

\begin{definition}
A K-hive is an integer hive satisfying the hive conditions 
(\ref{HCvertex}), or equivalently (\ref{HCedge})
for all its constituent rhombi of type R1 and R2 (but not R3),
with border labels determined by the zero partition or weight 
$0=(0,0,\ldots,0)$ with $\#0=n$,
a partition $\lambda$ with $\ell(\lambda)\leq n$ 
and a weight $\beta$ with $\#\beta=n$,
satisfying the constraint $|\lambda|=|\beta|$,
in such a way that $a_{0i}=0$ for $i=0,1,\ldots,n$, 
$a_{j,n-j}=ps(\lambda)_j=\lambda_1+\lambda_2+\cdots+\lambda_j$ 
for $j=1,2,\ldots,n$,
$a_{k,0}=ps(\beta)_k=\beta_1+\beta_2+\cdots+\beta_k$ 
for $k=1,2,\ldots,n$.
\label{Def-Khive}
\end{definition}
Schematically, we have
\begin{center}
\scalebox{0.75}{\input{h_lb1.pstex_t}}
\end{center}
Alternatively, in terms of edge labels we have:
\begin{center}
\scalebox{0.75}{\input{h_lb2.pstex_t}}
\end{center}

With this definition, we then have:
\begin{proposition} \cite{KTT1}
The Kostka coefficient $K_{\lambda\beta}$ 
is the number of K-hives with border labels determined as above by 
$\lambda$ and $\beta$.
\label{Prop-Khives}
\end{proposition}

\begin{proof}
Thanks to Property~\ref{Prop-K}, it is only necessary to establish 
a bijection between the set of all semistandard tableaux 
$T\in{\cal T}^\lambda(n)$ of weight $\wgt(T)=\beta$
and the set of all K-hives with boundary specified as in
Definition~\ref{Def-Khive}. This bijection comes about through the
existence of a sequence of maps exemplified as shown below.
\begin{eqnarray*}
&&
T\ =\ \
{\vcenter{\offinterlineskip
\halign{&\mystrut\vrule#&\mybox{\hss$\scriptstyle#$\hss}\cr
\hr{7}\cr
&1 &&1 &&3 &\cr
\hr{7}\cr
&2 &&3 &\cr
\hr{5}\cr
}}}
\quad\iff\quad
G\ =\ 
\begin{array}{ccccccccc}
        &3 &  &2 &  &0 &  &  & \cr
        &  &2 &  &1 &  &  &  & \cr
        &  &  &2 &  &  &  &  & \cr
\end{array}
\cr
&&
\begin{array}{ccccccccc}
        &  &  &  &  &  &  &  & \cr
        &  &  &  &  &  &  &  & \cr
\end{array}
\cr
&&\quad\iff\quad
Z\ =\
\begin{array}{ccccccccc}
        &0 &  &3 &  &5 &  &5 & \cr
        &  &0 &  &2 &  &3 &  & \cr
        &  &  &0 &  &2 &  &  & \cr
        &  &  &  &0 &  &  &  & \cr
\end{array}
\quad\iff\quad
H\ =\,
\begin{array}{ccccccccc}
        &  &  &  &0 &  &  &  & \cr
        &  &  &0 &  &3 &  &  & \cr
        &  &0 &  &2 &  &5 &  & \cr
        &0 &  &2 &  &3 &  &5 & \cr
\end{array}
\label{Eq-bij}
\end{eqnarray*}
\bigskip

Each step from the semistandard tableau $T$ to the $K$-hive $H$
is a bijection. $G$ is just the Gelfand-Tsetlin pattern corresponding
to $T$ whose top row is the partition specifying the shape of $T$,
and whose successive rows thereafter are the partitions specifying 
the shape of the sub-diagrams obtained from $T$ by deleting all boxes 
containing the entries $n$, then $n-1$, and so on. The array $Z$ is
then formed by adding a diagonal of $0$'s and forming the cumulative
rows sums of the entries in $G$. Finally, $H$ is just a re-orientation
of $Z$, and corresponds to a $K$-hive, with all edges removed
for the sake of clarity. 

The upshot, quite generally, is that for all $(i,j)$ 
with $0\leq i,j,i+j\leq n$ the entries of the $K$-hive $H$ are given
by
\be
a_{ij}=\hbox{$\#$ of entries $\leq(i+j)$ in first $i$ rows of $T$}\,.
\label{Eq-avalues}
\ee
The fact that $a_{0j}=0$ follows immediately. Since the entries of $T$
are strictly increasing down each column, it follows that no entry $i$
may lie below the $i$th row, and thus (\ref{Eq-avalues}) implies
that $a_{i0}=\ps(\beta)_i$ with 
$\beta_i=\wgt(T)_i=\#i{\rm's}\in T$, as required. Similarly, since
all entries of $T$ are no larger than $n$, it follows that 
(\ref{Eq-avalues}) implies that $a_{i,n-i}=\ps(\lambda)_i$
where $\lambda$ is the shape of $T$.

Again using (\ref{Eq-avalues}), the hive decrements
$\Delta =b+c-a-d=\alpha-\gamma=\beta-\delta$ arising from
rhombi of type R1 and R2 with $a$ in the position $(i,j)$ 
are given by:
\begin{eqnarray*}
&R1:& \Delta=
\hbox{$\#$ of entries $\leq(i+j)$ in row $i+1$
$-$ $\#$ of entries $\leq(i+j+1)$ in row $i+2$}\,;
\\ 
&R2:& \Delta=
\hbox{$\#$ of entries equal to $(i+j)$ in row $i+1$}\,.
\end{eqnarray*} 
The fact that numbers of entries $k$ in each row $r$ of $T$ are
non-negative, ensures that $\Delta\geq0$ in the R2 case, 
while the fact that they are weakly increasing across rows
and strictly increasing down columns ensures that $\Delta\geq0$
in the R1 case. Thus if $T$ is semistandard, then the map to $H$
yields a $K$-hive. 

Conversely, the map from any $K$-hive $H$ to a tableau $T$ always yields a 
semistandard tableau, as can be seen by reversing the above arguments.
The fact that $\Delta\geq0$ in the R2 case ensures that each
row of $T$ contains non-negative numbers of each distinct entry. 
If these are arranged in weakly decreasing order across each row, then
the fact that $\Delta\geq0$ in the R1 case implies that
all the entries in row $i+1$ immediately above the $k$'s in row $i+2$
are less than $k$, that is the entries are strictly increasing down 
columns.

Thus the maps described above are bijective, and the 
Proposition~\ref{Prop-Khives} follows.
\end{proof}

As an example of the application of this Proposition,
if $n=3$, $\lambda=(3,2,0)$ and $\beta=(2,1,2)$ then
the corresponding K-hives take the form:
\begin{equation}
\begin{array}{ccccccccc}
        &  &  &  &0 &  &  &  & \cr
        &  &  &0 &  &3 &  &  & \cr
        &  &0 &  &a &  &5 &  & \cr
        &0 &  &2&  &3 &  &5 & \cr
\end{array}
\label{Ex-Khive}
\end{equation}
where once again for the sake of clarity all the hive edges have been omitted.
Since the only integer values of $a$ satisfying the hive conditions 
(\ref{HCvertex}) for all the constituent rhombi of 
type R1 and R2 are $a=3$ and
$a=2$, it follows that $K_{32,212}=2$. The corresponding semistandard
tableaux are, of course, given by:
\begin{equation}
{\vcenter{\offinterlineskip
\halign{&\mystrut\vrule#&\mybox{\hss$\scriptstyle#$\hss}\cr
\hr{7}\cr
&1 &&1 &&2 &\cr
\hr{7}\cr
&3 &&3 &\cr
\hr{5}\cr
}}}
\qquad\qquad
{\vcenter{\offinterlineskip
\halign{&\mystrut\vrule#&\mybox{\hss$\scriptstyle#$\hss}\cr
\hr{7}\cr
&1 &&1 &&3 &\cr
\hr{7}\cr
&2 &&3 &\cr
\hr{5}\cr
}}}
\label{Eq-ex-st}
\end{equation}

It might be pointed out that 
when expressed in terms of edge labels, the hive conditions (\ref{HCedge}) 
for all constituent rhombi of types R1 and R2 imply
that in every K-hive the edge labels along any line
parallel to the right-hand edge of the hive are weakly
decreasing from top left to bottom right. This can be seen
from the following 5-vertex sub-diagram. 

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

\noindent
The edge conditions on the rhombi
of type R1 and R2 in the above diagram give 
$\beta\geq\gamma$ and $\alpha\geq\beta$, respectively, so that 
$\alpha\geq\gamma$, as claimed. This is of course
consistent with the edges of the right-hand boundary
of each K-hive being specified by a partition $\lambda$.


\section{Stretched coefficients}

\subsection{Polynomial conjectures}\
Now we are in a position to define and evaluate stretched  
Kostka coefficients. 
The partition obtained from $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_p)$
by multiplying all of its parts by the same positive integer, $t$, 
is denoted by $t\lambda=(t\lambda_1,t\lambda_2,\ldots,t\lambda_p)$.
With this notation, we refer to $K_{t\lambda,t\beta}$ as stretched Kostka coefficients, where $t$ is said to be the stretching parameter. It is not 
difficult to evaluate these stretched coefficients, particularly
through the use of the hive model, for a range of positive integer
values of $t$. 

For example, for $\lambda=(3,2)$ and $\mu=(1,1,1,1,1)$ the corresponding
stretched Kostka coefficients are given by
\be
 K_{t\lambda,t\mu}=\frac{1}{2}(t+1)(t^2+2t+2).
\label{Ex-Kt}
\ee
The generating function for these coefficients takes the form:
\be
 F_{\lambda\mu}(z)=\sum_{t=0}^\infty\ K_{t\lambda,t\mu}\ z^t
  = \frac{1+z+z^2}{(1-z)^4}.
\label{Ex-Fz}
\ee 
On the basis of this and many other examples we were led to
the following:

\begin{conjecture}~\cite{KTT1}
For all partitions $\lambda$ and $\mu$ such that $K_{\lambda\mu}>0$
there exists a polynomial $P_{\lambda\mu}(t)$ in $t$ with positive
rational coefficients such that $P_{\lambda\mu}(0)=1$ and
$P_{\lambda\mu}(t)=K_{t\lambda,t\mu}$ for all positive integers $t$.
\label{Conj-K}
\end{conjecture}

\begin{conjecture}~\cite{KTT1}
Given that the degree of the polynomial $K_{t\lambda,t\mu}$ is $d$,
the generating function for $K_{t\lambda,t\mu}$ takes the form
$F_{\lambda\mu}(z)=G_{\lambda\mu}(z)/(1-z)^{d+1}$, with 
$G_{\lambda\mu}(z)$ a polynomial of degree $\leq d$ having
non-negative integer coefficients. 
\label{Conj-F}
\end{conjecture}

Much of these conjectures has now been proved. In particular the
fact that $P_{\lambda\mu}(t)$ is polynomial appears to have
been proved first by Kirillov and Reshetikhin~\cite{KR}, with
a more recent proof provided by Billey, Guillemin and
Rassart~\cite{BGR}. 
In fact all that remains to be answered are the questions of the 
positivity of the coefficients in $P_{\lambda\mu}(t)$ and 
$G_{\lambda\mu}(z)$.

Before looking in more detail at the nature of the
polynomials $P_{\lambda\mu}(t)$ we note:

\begin{saturation condition}~\cite{KTT1} %(K-Saturation)
\begin{equation}
K_{t\lambda,t\mu}>0 \iff  K_{\lambda\mu}>0.
\label{K-sat}
\end{equation}
\label{Theo-Ksat}
\end{saturation condition}

\begin{proof}
This can be seen immediately from Theorem~\ref{Theo-JK} by noting that
$|t\lambda|=t\,|\lambda|$ and $ps(t\lambda)_r=t\,ps(\lambda)_r$
for all partitions $\lambda$ and all $r$. It follows that 
\begin{equation}
K_{\lambda\mu}>0 \iff |\lambda|=|\mu| \mbox{ and } \lambda\succeq \mu \\
\iff |t\lambda|=|t\mu| \mbox{ and } t\lambda\succeq t\mu
\iff K_{t\lambda,t\mu}>0,
\end{equation}
as required.
\end{proof}

Turning to the Conjecture~\ref{Conj-K} itself, the following 
key component has been established:

\begin{theorem}~\cite{K1,BGR}
Let $\lambda$ and $\mu$ be partitions of lengths 
$\ell(\lambda),\ell(\mu)\leq n$ such that $K_{\lambda\mu}>0$.
Then $P_{\lambda\mu}(t)=K_{t\lambda,t\mu}$ 
is a polynomial of degree 
at most $(n-1)(n-2)/2$ in $t$.
\label{Theo-BGR}
\end{theorem}

Clearly, Property~\ref{Prop-Kw} then implies as a corollary of
Theorem~\ref{Theo-BGR} that
if  $K_{\lambda\beta}>0$ then $P_{\lambda\beta}(t)=K_{t\lambda,t\beta}$
is also a polynomial in $t$ with the same upper bound on its degree.

\section{Factorisation}

Berenstein and Zelevinsky~\cite{BZ} introduced the notion of
{\it primitive} Kostka coefficients and pointed out that
every Kostka coefficient may be expressed as a product of 
primitive Kostka coefficients. 
First we deal with the case $K_{\lambda\mu}$ where $\lambda$ and $\mu$
are both partitions.
Following Berenstein 
and Zelevinsky, we make the following definition.
\begin{definition}
Let $\lambda$ and $\mu$ be partitions such that $|\lambda|=|\mu|$,
$\ell(\lambda),\ell(\mu)\leq n$
and $\lambda\succeq_n\mu$, so that $K_{\lambda\mu}>0$. Then  
$K_{\lambda\mu}$ is said to be {\it primitive}
if $\lambda\succ_n\mu$, that is $\ps(\lambda)_r>\ps(\mu)_r$ for
all $r=1,2,\ldots,n-1$. Conversely, if $K_{\lambda\mu}$ is
not primitive then there exists at least one 
value of $r$, with $1\leq r<n$, such that $\ps(\lambda)_r=ps(\mu)_r$.
\label{Def-prim}
\end{definition}

If $K_{\lambda\mu}>0$ but $K_{\lambda\mu}$ is not primitive
then $K_{\lambda\mu}$ factorises in accordance with the
following theorem.

\begin{theorem}\label{Theo-Kfact}
Let $\lambda,\mu$ be partitions such that $|\lambda|=|\mu|$ and 
$\ell(\lambda),\ell(\mu)\leq n$, with $\lambda\succeq_n\mu$ and 
$ps(\lambda)_r=ps(\mu)_r$ for some $r$ such that $1\leq r<n$.
Let $\lambda=(\sigma,\tau)$
and $\mu=(\zeta,\eta)$, with 
$\sigma=(\lambda_1,\lambda_2,\ldots,\lambda_r)$,
$\tau=(\lambda_{r+1},\lambda_{r+2},\ldots,\lambda_n)$, 
$\zeta=(\mu_1,\mu_2,\ldots,\mu_r)$
and $\eta=(\mu_{r+1},\mu_{r+2},\ldots,\mu_n)$, then
\be
        K_{\lambda\mu}=K_{\sigma\zeta}\ K_{\tau\eta}.
\label{Eq-Kfact}
\ee
\end{theorem}

We first give a combinatorial proof based on the use
of semistandard tableaux, and then a second combinatorial
proof based on the use of K-hives.

\begin{proof}[Proof 1.]
It follows from the definition of semistandard tableaux that no entry
$k$ of $T\in {\cal T}^\lambda(n)$ may appear lower than the $k$th row
of $T$. If $\ps(\lambda)_r=\ps(\mu)_r$ then all entries $1,2,\ldots,r$ 
completely fill the first $r$ rows of $T$. This means that all the
remaining  entries $r+1,r+2,\ldots,n$ must fill the rows of $T$ below 
the $r$th. Thus the top $r$ rows of $T$ constitute a semistandard
tableau $T_r\in{\cal T}^\sigma(r)$ of shape $F^\sigma$ with entries 
taken from the set $\{1,2,\ldots,r\}$, while the bottom $(n-r)$ rows
of $T$ constitute a second semistandard tableau $T\in{\cal T}^\tau(n-r)$
of shape $F^\tau$ with entries taken from the set $\{r+1,r+2,\ldots,n\}$.
Moreover, if any such  semistandard tableaux $T_r$ of shape
$F^\sigma$ and $T_{n-r}$ of shape $F^\tau$ are 
joined together to create a tableau $T$ of shape $F^\lambda$
with $\lambda=(\sigma,\tau)$, then $T$ is itself semistandard
since all the entries in the bottom row of $T_r$, 
which are necessarily $\leq r$, 
are strictly less than all the entries in the top row of $T_{n-r}$,
which are necessarily $\geq(r+1)$.

Setting, $\x=\y\,\z$ with $\y=(x_1,x_2,\ldots,x_r)$
and $\z=(x_{r+1},x_{r+2},\ldots,x_n)$ it follows from (\ref{Eq-sxT})
that
\[
  s_\lambda(\x)=\sum_{T\in{\cal T}^\lambda(n)}\ \x^{\wgt(T)}
   =\sum_{T_r\in{\cal T}^\sigma(r)}\ 
    \sum_{T_{n-r}\in{\cal T}^\tau(n-r)} 
    \y^{\wgt(T_r)}\ \z^{\wgt(T_{n-r})}.
\] 
It then follows from Property~\ref{Prop-K} that
\begin{align*}
  K_{\lambda\mu}&= 
\hbox{$\# T\in{\cal T}^\lambda(n)$ with $\wgt(T)=\mu$}\cr
&=
\left(\hbox{$\# T_r\in{\cal T}^\sigma(r)$ with $\wgt(T_r)=\zeta$}\right) 
\cdot
\left(\hbox{$\# T_{n-r}\in{\cal T}^\tau(n-r)$ with $\wgt(T_{n-r})=\eta$}\right)\cr 
&= K_{\sigma\zeta}\ K_{\tau\eta}\,,\nonumber
\end{align*}
as required. 
\end{proof}

\begin{proof}[Proof 2.]
First it should be noted that the hypothesis
$\lambda\succeq_n\mu$ implies that $K_{\lambda\mu}>0$. Moreover, we 
have $ps(\sigma)_i=ps(\lambda)_i\geq ps(\mu)_i=ps(\zeta)_i$
for $i=1,2,\ldots,r-1$ and $|\sigma|=ps(\sigma)_r=ps(\lambda)_r
=ps(\mu)_r=ps(\zeta)_r=|\zeta|$. Thus $\sigma\succeq_r\zeta$ and
hence $K_{\sigma\zeta}>0$. In addition we have 
$ps(\tau)_i=ps(\lambda)_{r+i}-ps(\lambda)_r=ps(\lambda)_{r+i}-|\sigma|
\geq ps(\mu)_{r+i}-|\zeta|=ps(\mu)_{r+i}-ps(\mu)_r=ps(\eta)_i$
for $i=1,2,\ldots,n-r$, and $|\tau|=|\lambda|-|\sigma|=|\mu|-|\zeta|=|\eta|$.
Thus $\tau\succeq_{n-r}\eta$ and hence $K_{\tau,\eta}>0$.

Now consider the K-hive with boundary determined by $\lambda=(\sigma,\tau)$

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

\noindent
The rules about
edge sums are such that on the boundary of the triangular region $T$ we have
$|\zeta|=|0|+|\rho|=|\rho|$. Since $|\zeta|=|\sigma|$ we have 
$|\rho|=|\sigma|$. The same rules applied to the parallelogram $X$ 
then imply that the sum of the edge lengths on the boundary between
$X$ and $A$ must be $|0|+|\sigma|-|\rho|=0$. Since $X$ can be viewed
as a collection of rhombi of type R2, applying the hive condition 
$\beta\geq\delta$ to each of these rhombi implies that the edge
lengths on the lower right boundary of $X$ must be non-negative. Since
their sum is zero, they must all be zero, as indicated in the
diagram.   
The $\alpha\geq \gamma$ hive condition for R2 may then be
applied to these same rhombi constituting $X$, yielding
the constraints $\rho_i\leq \sigma_i$ for $i=1,2,\ldots,r$. 
Since $|\rho|=|\sigma|$, we must have $\rho_i=\sigma_i$
for $i=1,2,\ldots,r$, that is $\rho=\sigma$.


Thus each K-hive $H$ with boundary $\lambda$ and $\mu$ consists of a
parallelogram $X$ in which all edge lengths are fixed, together
with a K-hive $T$ with boundary $\sigma$ and $\zeta$, and a second
K-hive $A$ with boundary $\tau$ and $\eta$. The hive conditions for
$H$ imply those appropriate to $T$ and $A$. 

In order to prove the required factorisation (\ref{Eq-Kfact}) it only
remains to show that combining all possible hives $T$ and $A$ with
a parallelogram $X$ of the appropriate boundary gives a hive $H$ in which
all the hive conditions corresponding to rhombi crossing the
boundaries of $T$ with $X$, and $A$ with $X$, are automatically
satisfied. Since, for K-hives we only use the rhombi of type R1 and
R2, it is clear that no such rhombus crosses the boundary between
$T$ and $X$, while only rhombi of type R1 cross the boundary between
$A$ and $X$. One such rhombus has been shown above. 

We may look in more detail at such a rhombus by means of the following 
diagram which shows a strip one edge length wide on 
either side of the $A-X$ boundary.

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

With the edge labels as shown, the R2 rhombus condition applied
in the region $A$ just below the $A-X$ boundary gives $\delta\leq\tau_1$, 
while the same
rhombus condition applied in the region $X$ 
just above the $A-X$ boundary gives $\rho_r\leq\beta\leq\sigma_r$. Since
$\rho_r=\sigma_r$ and $\tau_1=\lambda_{r+1}\leq\lambda_r=\sigma_r$,
we have $\delta\leq\tau_1\leq\sigma_r=\beta$. However, this is
just what is required to satisfy the R1 condition (\ref{HCedge}).

This completes the proof of the K-hive factorisation theorem.
\end{proof}

Repeated use of this theorem allows any non-primitive 
Kostka coefficient $K_{\lambda\mu}$ to be expressed as
a unique product of primitive Kostka coefficients
$K_{\sigma\zeta}$. It is only necessary at each stage 
to factor out the term meeting the hypotheses
of the above Theorem~\ref{Theo-Kfact} with the
smallest possible value of $r$.

Applying the above argument to stretched Kostka coefficients
immediately gives the following:

\begin{theorem}\label{Theo-tKfact}
Let $\lambda,\mu$ be partitions such that $|\lambda|=|\mu|$ and 
$\ell(\lambda),\ell(\mu)\leq n$, with $\lambda\succeq_n\mu$ and 
$ps(\lambda)_r=ps(\mu)_r$
for some $r$ for which $1\leq r<n$. 
Let $\lambda=(\sigma,\tau)$
and $\mu=(\zeta,\eta)$, with 
$\sigma=(\lambda_1,\lambda_2,\ldots,\lambda_r)$,
$\tau=(\lambda_{r+1},\lambda_{r+2},\ldots,\lambda_n)$, 
$\zeta=(\mu_1,\mu_2,\ldots,\mu_r)$
and $\eta=(\mu_{r+1},\mu_{r+2},\ldots,\mu_n)$, 
then for all positive integers $t$ we have
\be
        P_{\lambda\mu}(t)=P_{\sigma\zeta}(t)\ P_{\tau,\eta}(t).
\label{Eq-tKfact}
\ee
\end{theorem}

An example of this type of factorisation has been provided in the 
introduction in (\ref{Eq-Ex2}).

It is quite instructive from a combinatorial point of view, 
although not strictly necessary by virtue of 
Property~\ref{Prop-Kw}, 
to extend the above analysis to the
case of Kostka coefficients $K_{\lambda\beta}$ for which the
weight $\beta$ is not necessarily a partition. In this case
$K_{\lambda\beta}$ is said to be primitive if $|\lambda|=|\beta|$
and  $ps(\lambda)_r\geq ps(\beta)_I$ for any proper
subset $I$ of $N=\{1,2,\ldots,n\}$ with $r=\#I$. 

In the non-primitive case, we have:

\begin{theorem}\label{Theo-Kbetafact}
Let $\lambda$ be a partition with $\ell(\lambda)\leq n$, and let
$\beta=(\beta_1,\beta_2,\ldots,\beta_n)$ be a weight such that 
$|\lambda|=|\beta|$ and $ps(\lambda)_i\geq ps(\beta)_I$ for any
$I\subset N$, with $i=\#I$. Then $K_{\lambda\beta}$ is not 
primitive if there exists a proper subset $I=\{i_1,i_2,\ldots,i_r\}$
of $N$ such that $ps(\lambda)_r=ps(\beta)_I$ with $r=\#I$ for some 
$r$ for which $1\leq r<n$. Let the complement of $I$ in $N$ be denoted
by $\ov{I}=\{j_1,j_2,\ldots,j_{n-r}\}$. 
In such a case let 
$\sigma=(\lambda_1,\lambda_2,\ldots,\lambda_r)$,
$\tau=(\lambda_{r+1},\lambda_{r+2},\ldots,\lambda_n)$, 
$\zeta=(\beta_{i_1},\beta_{i_2},\ldots,\beta_{i_r})$
and $\eta=(\beta_{j_1},\beta_{j_2},\ldots,\beta_{j_{n-r}})$, so that 
$\lambda=(\sigma,\tau)$, with $\sigma$ and $\tau$ partitions,
and $\beta=\zeta\cup\eta$, with $\zeta$ and $\eta$ weights, not
necessarily partitions,
satisfying the partial sum constraints $|\zeta|=|\sigma|$ and 
$|\eta|=|\tau|$. Then
\be
        K_{\lambda\beta}=K_{\sigma\zeta}\ K_{\tau\eta}.
\label{Eq-Kbetafact}
\ee
\end{theorem}

A complete combinatorial proof of this theorem, based on the
use of hives, is presented in an Appendix below. 

Once again scaling everything by $t$ is straightforward. 
If $K_{\lambda\beta}$
is primitive then so is $K_{t\lambda,t\beta}$ since all the 
partial sum conditions are scaled by the same factor $t$. By
the same token the factorisation occurs in the stretched non-primitive
case just as it does in the unstretched non-primitive case -- all boundary
edges are simply scaled by $t$, and as we have shown, it is these
boundary edges that completely determine the factorisation.
Thus under the hypotheses of Theorem~\ref{Theo-Kbetafact} we have
\be
        P_{\lambda\beta}(t)=P_{\sigma\zeta}(t)\ P_{\tau\eta}(t).
\label{Eq-Pbetafact}
\ee

This is illustrated for $n=6$ and $r=3$ by $\lambda=(9,6,4,4,2,0)$
and $\beta=(2,6,3,7,6,1)$, for which $ps(\lambda)_3=19=ps(\beta)_I$
with  $I=\{2,4,5\}$. In this case $\sigma=(9,6,4)$, $\tau=(4,2,0)$,
$\zeta=(6,7,6)$ and $\eta=(2,3,1)$. Correspondingly we find
\be
P_{96442,263761}=(t+1)(2t+1), \ P_{964,676}=(2t+1), \ \ P_{42,231}=(t+1),
\label{Eq-PbetafactEx}
\ee 
thereby exemplifying the factorisation (\ref{Eq-Pbetafact}).

It is interesting to note that the above factorisation of Kostka 
coefficients can be extended to the case of $q$-dependent 
Kostka--Foulkes polynomials, $K_{\lambda\mu}(q)$. 
These have a combinatorial definition
in terms of the charge statistic on semistandard Young tableaux~\cite[p.~242]{M}.
By way of illustration, in the case of the above example we find
\begin{align*}
K_{t(96442),t(766321)}(q)&=q^{3t}\ \frac{q^{t+1}-1}{q-1}\
\frac{q^{2t+1}-1}{q-1} \\
K_{t(964),t(766)}(q)&=q^{2t}\ \frac{q^{2t+1}-1}{q-1}\\
K_{t(42),t(321)}(q)&=q^t\ \frac{q^{t+1}-1}{q-1}.
\end{align*}


\section{The zeros of stretched Kostka polynomials}

As has been noted the
stretched Kostka polynomials $P_{\lambda\mu}(t)$
contain factors $(t+m)$ for some sequence of values $m=1,2,\ldots,M$
for some positive integer $M$. This is no accident. In this section
we describe a method of determining $M$ for stretched Kostka
polynomials. It will be recalled that the Kostka
coefficients are defined in terms of Schur functions by (\ref{K-def}). 
It then follows from (\ref{S-def}) that
$P_{\lambda\mu}(t)=K_{t\lambda,t\mu}$ is the coefficient of
$x_1^{t\mu_1}x_2^{t\mu_2}\cdots x_n^{t\mu_n}$ in
the expansion of
\be
     s_{t\lambda}(\mathbf{x})
      =\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.
Then $P_{\lambda\mu}(-m)=K_{-m\lambda,-m\mu}$ is the coefficient of
$x_1^{-m\mu_1}x_2^{-m\mu_2}\cdots x_n^{-m\mu_n}$
in the expansion of $s_{-m\lambda}(\mathbf{x})$.
However
\be
s_{-m\lambda}(\mathbf{x}) 
      =\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$
and $\ov{\mathbf{x}}=(\ov{x}_1,\ov{x}_2,\ldots,\ov{x}_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{\mathbf{x}}).
\label{s-mlambda}
\ee
Since $x_1^{-m\mu_1}x_2^{-m\mu_2}\cdots x_n^{-m\mu_n}
=\ov{x}_1^{m\mu_1}\ov{x}_2^{m\mu_2}\cdots\ov{x}_n^{m\mu_n}$
it follows that $P_{\lambda\mu}(-m)=K_{-m\lambda,-m\mu}$
is the coefficient of 
$\ov{x}_1^{m\mu_1}\ov{x}_2^{m\mu_2}\cdots\ov{x}_n^{m\mu_n}$
in the expansion of the right hand side.
It then follows, replacing the dummy variables $\ov{x}_i$
by $x_i$ for $i=1,2,\ldots,n$, that $P_{\lambda\mu}(-m)=K_{-m\lambda,-m\mu}$
is the coefficient of $x_1^{m\mu_1}x_2^{m\mu_2}\cdots x_n^{m\mu_n}$
in the expansion of $s_{m\tilde{\lambda}}(\mathbf{x})$, where
$\tilde\lambda=(\lambda_n,\ldots,\lambda_2,\lambda_1)$
is the weight obtained by reversing the order of the parts of
$\lambda$, including any trailing zeros.
Then to exploit the above it is only necessary to standardise 
\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 is carried out in the usual way~\cite{L}
by reordering the columns of the numerator determinant. 
However there are two quite different possible outcomes:
\be
  s_{m\tilde{\lambda}}(\x)
   = 
\begin{cases}
 0&\hbox{case (i)};\cr
 \eta_\rho\,s_{\rho}(\x) \ \mbox{with}\ \eta_\rho=\pm1 \ \  &\hbox{case (ii)}.\cr
\end{cases}
\label{S-mod}
\ee

For example, in the case $n=5$ and $\lambda=(4,2,1,0,0)$ we 
have $\tilde\lambda=(0,0,1,2,4)$. For $m=1$ this gives
$s_{m\tilde{\lambda}}(\x)=s_{0,0,1,2,4}(\x)=0$. Similarly
for $m=2$ we have $s_{m\tilde{\lambda}}(\x)=s_{0,0,2,4,8}(\x)=0$.
However, for $m=3$ we obtain 
$s_{m\tilde{\lambda}}(\x)=s_{0,0,3,6,12}(\x)=-s_{8,4,3,3,3}(\x)$,
while for $m=5$ we have
$s_{m\tilde{\lambda}}(\x)=s_{0,0,4,8,16}(\x)=-s_{12,6,4,3,3}(\x)$.

More generally, the case (i) result $0$ arises if and only if 
\be
     m\,\lambda_{n-k+1}+n-k=m\,\lambda_{n-l+1}+n-l
\label{S-0}
\ee
for some $k$ and $l$ such that $1\leq l<k\leq n$. 
In all other cases the formula given in case (ii)
applies for some partition $\rho$ of length at most $n$ 
and weight $m|\lambda|$, and $\eta_\rho=\pm1$ 
is a sign factor recording the number of transpositions
of columns of the numerator determinant of (\ref{S-m})
required to standardise the Schur function.

It follows that we can expect there to be a possibility
of two types of zero of $P_{\lambda\mu}(t)$ for $t=-m$: type (i) 
associated with case (i) of (\ref{S-mod}), and type 
(ii) associated under certain conditions
on $\rho$ and $m\,\mu$ with case (ii). Indeed adopting the
notation of (\ref{S-mod}) we have the following:

\begin{proposition}
\label{Zeros}
Let $\lambda$ and $\mu$ be such that $K_{\lambda\mu}$
is primitive. Then $P_{\lambda\mu}(t)=K_{t\lambda,t\mu}$ contains a 
factor $(t+m)$ if and only if either case (i) applies and 
\be
            m=(j-i)/(\lambda_i-\lambda_j)
\label{m-sol}
\ee
for some $i$ and $j$ such that $1\leq i<j\leq n$, 
or case (ii) applies and 
\be
        ps(\rho)_k<m\,ps(\mu)_k
\label{m-ps}
\ee
for some $k$ such that $1\leq k <n$. 
\end{proposition}

\begin{proof}
We have already noted that $P_{\lambda\mu}(-m)=K_{-m\lambda,-m\mu}$
is the coefficient of\break $x_1^{m\mu_1}x_2^{m\mu_2}\cdots x_n^{m\mu_n}$
in $s_{m\tilde\lambda}(\x)=s_{m\lambda_n,\ldots,m\lambda_2,m\lambda_1}
(x_1,x_2,\ldots,x_n)$. Thus if case (i) of (\ref{S-mod}) 
applies then $P_{\lambda\mu}(-m)=0$, while if case (ii) applies
then $P_{\lambda\mu}(-m)=\eta_\rho K_{\rho,m\mu}$. The conditions for case 
(i) to apply are given in (\ref{S-0}). However, setting $i=n-k+1$ 
and $j=n-l+1$ leads immediately to the required case (i) conditions
(\ref{m-sol}) for $P_{\lambda\mu}(-m)=0$. 
Turning to case (ii) of (\ref{S-mod}) 
$P_{\lambda\mu}(-m)=\eta_\rho\,K_{\rho,m\mu}$ will be zero
by virtue of Theorem~\ref{Theo-JK}
if any one of the partial sum conditions 
$ps(\rho)_k\geq m\,ps(\mu)_k$ for all $k=1,2,\ldots,n$ is 
violated. Since $|\rho|=m\,|\mu|$ this leaves precisely the 
required case (ii) conditions (\ref{m-ps}) for $P_{\lambda\mu}(-m)=0$.
\end{proof}

We may extend our earlier example with $n=5$ and
$\lambda=(4,2,1,0,0)$ by taking $\mu=(3,1,1,1,1)$
for illustrative purposes. We have already seen that
there are type (i) zeros, independent of $\mu$ that
arise for $m=1$ and $m=2$. These arise from (\ref{m-sol})
for the pairs $(i,j)=(3,4)$ and $(3,5)$, respectively,
leading to $(j-i)/(\lambda_i-\lambda_j)=(4-3)/(1-0)=1$
and $(5-3)/(1-0)=2$. For $m=3$ we have a type (ii)
zero since $P_{\lambda\mu}(-3)=\eta_\rho K_{\rho,m\mu}=-K_{84333,93333}=0$
by virtue of the fact that $ps(\rho)_1=8<9=ps(m\mu)_1$. 
On the other hand for $m=4$ we have 
$P_{\lambda\mu}(-4)=\eta_\rho K_{\rho,m\mu}=-K_{12\,6433,12\,4444}=-3$
which is non-zero, and the same will be true for
all $m\geq4$.
 
In view of our earlier remarks about the sequence
of zeros of $P_{\lambda\mu}(t)$ for $t=-m$ with $m=1,2,\ldots,M$,
it comes as no surprise that we are able to elaborate on the
above and establish 
that the zeros are indeed consecutive and that for
any primitive $K_{\lambda\mu}$ we can always find 
a finite $M>0$ such that 
$P_{\lambda\mu}(-m)=0$ for all $m=1,2,\ldots,M$, but thereafter
$P_{\lambda\mu}(-m)\neq0$ for all $m>M$.

All this is borne out in our example with $n=5$, $\lambda=(4,2,1,0,0)$
and $\mu=(3,1,1,1,1)$ for which
\be
 P_{\lambda\mu}(t)=K_{t\lambda,t\mu}=\frac{1}{60}(t+1)(t+2)(t+3)(3t^2+7t+10),
\label{Ex-KPt}
\ee
for which $M=3$ and we have consecutive zeros at $t=-m$ 
with $m=1,2,3$. Of these, as we have seen, the first two are type (i) 
and the third is type (ii). The first non-zero case occurs with 
$t=-4$ and we obtain from the explicit formula (\ref{Ex-KPt})
the result $P_{\lambda\mu}(-4)=-3$ that we had found earlier. In fact for $t=-m$
it is clear that (\ref{Ex-KPt}) gives $P_{\lambda\mu}(-m)<0$ for all $m>M=3$.

\section{The degrees of stretched Kostka polynomials}

As we have seen the calculation of stretched 
Kostka polynomials may be reduced to that of calculating 
these polynomials in primitive cases only. Even so the task 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 result. 
Let the edge labelling of a particular 5-vertex
subset of a K-hive be as shown below in the left hand diagram, 
with two identical labels $\alpha$.

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

This diagram contains rhombi of type R1 and R2.
The hive conditions (\ref{HCedge}) for
the former imply $\alpha\leq\beta$, while those for the latter give
$\beta\leq\alpha$. It follows that $\beta=\alpha$. This result is displayed
more simply by deleting all the edges except those sharing the
same label $\alpha$, and suppressing the label itself.
This gives the right hand diagram 
where the equality of a pair of edge labels in a linear sequence
forces an identical edge label in a neighbouring line. 

Applying these notions to the case of K-hives 
with boundaries of length $n$ and with border labels
determined by $0$, $\lambda$ and $\mu$, it follows from the above
that any equalities of successive parts of $\lambda$ propagate 
as equalities of edge labels within each possible K-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 
$0$ and $\mu$-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 K-hive the differences 
in values between 
neighbouring entries along these lines are all $\alpha$.

This process is to be repeated for all sequences of equal edge
labels along the $\lambda$-boundary.  Finally, all neighbouring
vertices on all three boundaries are to be connected by edges.
In this way we arrive at a graph $G_{n;\lambda}$ that depends
only upon $n$ and $\lambda$. 
\medskip

For example, for $n=6$ and $\lambda=(4,2,2,0,0,0)$
the graph $G_{n;\lambda}$ takes the form:

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

With this notation we have:

\begin{proposition}
\label{K-degree}
Let $\lambda$ and $\mu$ be partitions of lengths
$\ell(\lambda),\ell(\mu)\leq n$ such that
$K_{\lambda\mu}>0$. Let $\deg(P_{\lambda\mu}(t))$ be the degree of 
the corresponding stretched K-polynomial 
$P_{\lambda\mu}(t)=K_{t\lambda,t\mu}$.
Let $\d(G_{n;\lambda})$ be the number of 
connected components of the graph $G_{n;\lambda}$ that
are not connected to the boundary.
Then 
\be
      \deg(P_{\lambda\mu}(t))\leq \d(G_{n;\lambda}).
\label{K-bound}
\ee
Moreover, if
$\lambda=(w_1^{v_1},w_2^{v_2},\ldots,w_r^{v_r})$,
with $w_1>w_2>\cdots>w_r\geq0$, 
$v_s\geq1$ for all $s=1,2\ldots,r$, with $r\geq 2$,
and $v_1+v_2+\cdots+v_r=n$, then
\be
      \d(G_{n;\lambda})=\frac{1}{2}(n-1)(n-2)
-\sum_{s=1}^r \frac{1}{2}v_s(v_s-1).
\label{G-formula}
\ee
\end{proposition}

\begin{proof}
Any labelling of the vertices of the hive must be such that
the difference $\alpha$ in values along each interior edge of 
the graph $G_{n;\lambda}$ is, by construction of those
edges, equal to a corresponding edge value on the parallel 
$\lambda$-boundary, that is 
$\alpha=\lambda_i=w_s$ for some $i$ and a corresponding $s$.  
For each 
connected component this fixes the values of all vertex labels
in terms of that of any one vertex of that component. In 
the case of a component connected to the boundary, the value
at the boundary vertex fixes all the others in that component.
The maximum number of degrees of freedom in 
assigning entries to the corresponding set of K-hives
with given boundary is then $\d(G_{n;\lambda})$. 

The application of the stretching parameter $t$ leaves $G_{n;\lambda}$ 
unaltered, that is $G_{n;t\lambda}=G_{n;\lambda}$, so that the 
number of degrees of freedom in assigning entries to the
stretched K-hives is still $\d(G_{n;\lambda})$. 
For each connected component of $G_{n;\lambda}$ that is not connected 
to the boundary we may select any one convenient vertex. The 
values of its label are not fixed by the hive constraints.
They must satisfy a set of linear inequalities that are all scaled by $t$ 
as both the  boundary vertex and edge labels are scaled by the stretching 
parameter $t$. It follows that the range of 
allowed values of the label must be either independent of $t$ or 
linear in $t$, thereby giving rise to a corresponding contribution 
to $P_{\lambda\mu}(t)$ that is at most linear in $t$.
The number of degrees of freedom, $\d(G_{n;\lambda})$, 
that we have identified therefore gives an upper bound on the 
degree of the corresponding stretched K-polynomial in $t$.

The number of internal vertices of $G_{n;\lambda}$ is
$(n-1)(n-2)/2$. For given $n$ and arbitrary $\lambda$ this
provides a preliminary upper bound on the degree of $P_{\lambda\mu}(t)$. 
However, for
$\lambda=(w_1^{v_1},w_2^{v_2},\ldots,w_r^{v_r})$,
each $s$ such that $v_s>1$ specifies a sequence of components
of $\lambda$ having the same value, namely $w_s$. 
There is a corresponding set of $v_s(v_s-1)/2$ interior edges 
within $G_{n;\lambda}$. Whether or not these interior edges
reach the boundary, as they do in the two cases $s=1$ and $s=r$, 
their introduction reduces the number of  connected components 
not linked to the boundary by $v_s(v_s-1)/2$. 
The result (\ref{G-formula}) then follows by 
noting that for different $s$ the sets of vertices linked by the 
interior edges are disjoint, so that their contributions to the reduction
of $\d(G_{n;\lambda})$ are independent. 
\end{proof}

In the case of our example with $n=6$ and 
$\lambda=(4,2,2,0,0,0)=(4,2^2,0^3)$
we can see from the graph of $G_{n;\lambda}$ that $\d(G_{n;\lambda})=6$,
in agreement with the formula (\ref{G-formula}) that gives
$\d(G_{n;\lambda})=5\cdot4/2-2\cdot1/2-3\cdot2/2=6$.
Hence for all $\mu$ the degree of the corresponding stretched
Kostka coefficient polynomial $P_{\lambda\mu}(t)$ must satisfy 
\be
    \deg(P_{\lambda\mu}(t))\leq 6.
\ee 
By way of example, for $\mu=(3,1,1,1,1,1)$ we find
\be
P_{\lambda\mu}(t)=\frac{1}{72}(t+1)(t+2)(t+3)(t+4)(t^2+2t+3)
\quad\hbox{so that}\quad
F_{\lambda\mu}(z)=\frac{1+3z+6z^2}{(1-z)^7},
\ee
while for $\mu=(2,2,1,1,1,1)$ we have
\be
P_{\lambda\mu}(t)=\frac{1}{60}(t+1)(t+2)(t+3)(3t+5)(t^2+2t+2)
\quad\hbox{so that}\quad
F_{\lambda\mu}(z)=\frac{1+9z+19z^2+7z^3}{(1-z)^7}.
\ee
On the other hand if $\mu=(3,2,1,1,1,0)$ we find
\be
P_{\lambda\mu}(t)=\frac{1}{24}(t+1)(t+2)(t+3)(t+4)
\quad\hbox{so that}\quad
F_{\lambda\mu}(z)=\frac{1}{(1-z)^5}.
\ee
The third case in which $\deg(P_{\lambda\mu}(t))=4<6$ is one for which 
$K_{\lambda\mu}$ is not primitive.
In both the other cases $K_{\lambda\mu}$
is primitive, and we have $\deg(P_{\lambda\mu}(t))=6$ so that the bound 
(\ref{K-bound}) is saturated.

On the basis of very many calculations of this type we are led
to the following: 

\begin{conjecture}
\label{K-saturation}
Let $\lambda$ and $\mu$ be partitions of lengths
$\ell(\lambda),\ell(\mu)\leq n$ such that $K_{\lambda\mu}>0$.
Let $P_{\lambda\mu}(t)=K_{t\lambda,t\mu}$,
then $\deg(P_{\lambda\mu}(t))=\d(G_{n;\lambda})$ for all $\mu$
such that $K_{\lambda\mu}$ is primitive.
\end{conjecture}

We might point out that a formula for the dimension
$d=\dim G(\lambda,\mu)$ of the convex Gelfand-Tsetlin polytope
$G(\lambda,\mu)$, which is nothing other than
our $\deg(P_{\lambda\mu}(t))$, has been given in Section~7
Exercise~3.a. of~\cite{K1},
and also quoted in Section~5.4 of~\cite{K2}. 
With the summation
upper limit extended appropriately, this formula coincides with our
$\d(G_{n;\lambda})$ if we choose $n=s=\ell(\mu)$. 
Thus if $K_{\lambda\mu}$ is primitive, in which 
case it is necessarily true that $n=\ell(\mu)$, the above 
conjecture is equivalent to the claim made regarding the 
formula given in~\cite{K1}. 
However, in non-primitive cases such as that exemplified in 
(\ref{Eq-Ex1}),
the cited formula in~\cite{K1}
does not yield the correct value, $6$,
of $\deg(P_{\lambda\mu}(t))$. Instead, the formula yields the value 
$\d(G_{9;\lambda})=21$. To obtain the correct
result one must first factorise the non-primitive K-polynomial
and then apply the above conjecture to each of the primitive factors 
to give $\deg(P_{\lambda\mu}(t))=2+4=6$, in accordance with 
(\ref{Eq-Ex2}). 

Finally, we should note that the work of Kirillov~\cite{K2}
includes a wealth of conjectures concerning not just Kostka 
coefficients and polynomials, but also what he calls
parabolic Kostka polynomials and 
Littlewood-Richardson polynomials. The latter are also
discussed in~\cite{KTT2}.
\bigskip

\noindent{\bf Note added in proof}.\ \ 
The validity of the above Conjecture~\ref{K-saturation},
including its restriction to the primitive case, has recently 
been proved by McAllister~\cite{McA}.


\begin{thebibliography}{999999}

\bibitem[BK]{BK}
A.D. Berenstein and A.N. Kirillov,
{\it Groups generated by involutions, Gelfand-Tsetlin patterns
and combinatorics of Young tableaux},
St Petersburg Math. J. {\bf 7} (1966), 77--127.

\bibitem[BZ]{BZ}
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[BGR]{BGR}
S. Billey, V. Guillemin and E. Rassart,
{\it A vector partition function for the multiplicities of $sl_k(\C)$},
J. Algebra {\bf 278} (2004), 251--293.

\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[DeLM]{DeLM}
J.A. De Loera and T.B. McAllister,
{\it Vertices of Gelfand-Tsetlin polytopes},
Discr. Comput. Geom. {\bf 32} (2004), 459--470.

\bibitem[E]{E}
E. Ehrhart,
{\it Polyn\^omes arithm\'etiques et m\'ethode des poly\`edres en combinatoire},
Internat. Ser. Numer. Math., Vol.~35,
Birkh\"auser--Verlag, Basel, 1977.

\bibitem[GT]{GT}
I.M. Gel'fand and M.L. Tsetlin,
{\it Finite-dimensional representations of the group of unimodular
matrices},
Dokl. Akad. Nauk. SSSR {\bf 77} (1950), 825--828. 

\bibitem[JK]{JK}
G. James and A. Kerber,
{\it The representation theory of the symmetric group},
Encyclopedia of mathematics and its applications {\bf 16},
Addison--Wesley, Reading, 1981.

\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 polynomial nature of 
stretched Littlewood-Richardson coefficients},
S\'eminaire Lotharingien de Combinatoire {\bf 54A} (2006),
Article~B54Ad, 19~pp.

\bibitem[K1]{K1}
A.N. Kirillov,
{\it Ubiquity of Kostka polynomials},
in Physics and Combinatorics 1999,
World Scientific, Singapore, 2001, pp.~85--200.

\bibitem[K2]{K2}
A.N. Kirillov,
{\it An invitation to the generalized saturation conjecture},
RIMS Publ. Kyoto Univ. {\bf 40} (2004), 1147--1239.

\bibitem[KR]{KR}
A.N. Kirillov and N.Y. Reshetikhin,
{\it The Bethe Ansatz and the combinatorics of Young tableaux},
J. Soviet Math. {\bf 41} (1988), 925--955.


\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[L]{L}
 D.E. Littlewood,
{\it The theory of group characters and matrix representations of groups},
2nd ed., Clarendon Press, Oxford, 1950.

\bibitem[M]{M}
I.G. Macdonald,
{\it Symmetric functions and Hall polynomials}, 
2nd ed., Oxford University Press, Oxford, 1995.

\bibitem[McA]{McA}
T.B. McAllister, 
{\it Degrees of stretched Kostka coefficients},
{\tt ar$\chi$iv:math.RT/0603173}, (2006).

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

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


%\bibitem[Z]{Zelobenko 1973}
%D.P. Zelobenko,
%{\it Compact Lie groups and their representations}
%Transl. Math. Monographs, Vol. 40,
%Amer. Math. Soc., Providence, 1973.

\end{thebibliography}


\section*{Appendix}
\setcounter{section}{5}
\setcounter{theorem}{3}
\setcounter{equation}{2}

Here we present a proof of the following factorisation
theorem for $K_{\lambda\beta}$ in the case where 
$\beta$ is any weight, not necessarily a partition, 
such that $K_{\lambda\beta}$ is not primitive. The approach
is instructive since it is indicative of the way in
which our factorisation result may be extended to the
case of Littlewood-Richardson coefficients. 
An account of this is presented elsewhere~\cite{KTT2}.

\begin{theorem}
Let $\lambda$ be a partition with $\ell(\lambda)\leq n$, and let
$\beta=(\beta_1,\beta_2,\ldots,\beta_n)$ be a weight such that 
$|\lambda|=|\beta|$ and $ps(\lambda)_i\geq ps(\beta)_I$ for any
$I\subset N=\{1,2,\ldots,n\}$, with $i=\#I$. 
Then $K_{\lambda\beta}$ is not 
primitive if there exists a proper subset $I=\{i_1,i_2,\ldots,i_r\}$
of $N$ such that $ps(\lambda)_r=ps(\beta)_I$ with $r=\#I$ for some 
$r$ for which $1\leq r<n$. Let the complement of $I$ in $N$ be denoted
by $\ov{I}=\{j_1,j_2,\ldots,j_{n-r}\}$. In such a case let 
$\sigma=(\lambda_1,\lambda_2,\ldots,\lambda_r)$,
$\tau=(\lambda_{r+1},\lambda_{r+2},\ldots,\lambda_n)$, 
$\zeta=(\beta_{i_1},\beta_{i_2},\ldots,\beta_{i_r})$
and $\eta=(\beta_{j_1},\beta_{j_2},\ldots,\beta_{j_{n-r}})$, so that 
$\lambda=(\sigma,\tau)$, with $\sigma$ and $\tau$ partitions,
and $\beta=\zeta\cup\eta$, with $\zeta$ and $\eta$ weights, not
necessarily partitions, satisfying the partial sum constraints 
$|\zeta|=|\sigma|$ and $|\eta|=|\tau|$. Then
\be
        K_{\lambda\beta}=K_{\sigma\zeta}\ K_{\tau\eta}. 
\ee
\end{theorem}


\noindent{\bf Proof} Consider first the special case for which 
$\beta=(\theta,\zeta,\phi)$ and $\eta=(\theta,\phi)$ with 
$\#\zeta=r$ and $\#\theta+\#\phi=n-r$. The hives
$H$ whose enumeration gives $K_{\lambda\beta}$ are illustrated
schematically in the following diagram. 

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

As in our proof
of (\ref{Eq-Kfact}), covering the parallelograms $Y$ and $X$
with rhombi of type R1 and R2, respectively, and applying the 
$\gamma\leq\alpha$ hive conditions gives  
$|\zeta|\leq |\xi|+|\chi|+|\psi| \leq |0|+|\rho|\leq |\sigma|$.
Since $|\zeta|=|\sigma|$ the intervening inequalities 
must be equalities. Then as before the constraint $|\rho|=|\sigma|$
coupled with the R2 hive conditions $\rho_i\leq\sigma_i$ for
$i=1,2,\ldots,r$ implies that $\rho=\sigma$. In exactly
the same way the constraint $|\zeta|=|\xi|+|\chi|+|\psi|$
coupled to the R1 hive conditions of the form 
$\zeta_j\leq \xi_j,\chi_k,\psi_l$, as appropriate, gives 
$\zeta=(\xi,\chi,\psi)$. 
Since $|\rho|=|\sigma|$ and the edge labels along 
the upper left boundary of $X$
are all $0$, it follows, as indicated, that the same is true 
of the lower right boundary edges of $X$. We note also that 
$|\kappa|+|\zeta|=|\xi|+|\chi|+|\psi|+|\omega|$, so that 
$|\kappa|=|\omega|$. Finally, it follows by using the
$\beta\geq\delta$ hive condition for R1 that $\kappa_j\geq\omega_j$
for all $j$. Hence $\kappa=\omega$ so that the right-hand boundary
of $A$ matches up exactly with the left-hand boundary of $B$. All
this shows that each hive $H$ contributing to $K_{\lambda\beta}$
consists of a subhive $T$ contributing to $K_{\sigma\zeta}$
and a subhive formed from the union of $A$ and $B$ contributing
to $K_{\tau\eta}$ with $\eta=(\theta,\phi)$. The remaining portions
$X$ and $Y$ are completely constrained by the equality of edge labels
across each of these parallelograms in each direction.

In order to prove the validity of (\ref{Eq-Kbetafact}) it only remains 
to show that all cross boundary hive conditions are automatically
satisfied once the hives $T$ and $A\cup B$ are specified. The only
cases of concern are R1 hives crossing the $X-B$ boundary and the
R2 hives crossing the $T-Y$ boundary. The former are covered by the
argument used in the proof of Theorem~\ref{Theo-Kfact}. The
latter are dealt with in a precisely analogous way, through
the consideration of a subdiagram following the $T-Y$ and $X-B$ boundary
of width equal to two edge lengths, as shown below.

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

First of all in the portions of the strips overlapping the
regions $X$ and $Y$, we have $\rho_r=\sigma_r$ and
$\kappa_1\geq\gamma\geq\omega_1$. However $\kappa_1=\omega_1$.
In $B$ and $T$ the R2 and R1 hive conditions imply $\omega_1\leq\tau_1$
and $\rho_r\leq\alpha$. Combining these we have 
$\gamma=\omega_1\leq\tau_1=\lambda_{r+1}\leq\lambda_r
=\sigma_r=\rho_r\leq\alpha$.
Hence the R2 hive condition $\gamma\leq\alpha$ is automatically
satisfied everywhere on the $T-Y$ boundary.

This completes the proof of (\ref{Eq-Kbetafact}) for one class
of non-primitive cases. Generalising to the case of any weight
$\beta$ such that $K_{\lambda\beta}$ is not primitive, is now
rather straightforward. The most general type of case is
illustrated below:

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

Here, the pattern is clear. We have $\lambda=(\sigma,\tau)$
and $\beta=\zeta\cup\eta$ with $\zeta=\cup_i\gamma_i$ and
$\eta=\cup_j \alpha_j$, where in general $\alpha_i$ and $\gamma_j$
are themselves weights with many parts, 
as are $\zeta$ and $\eta$. The regions
$X_i$ and $Y_i$ are all parallelograms composed of rhombi
if type R2 and R1, respectively. The total number of edges 
specified by $\gamma_i$ for all $i$ is $r$, and the total
number of edges specified by $\alpha_i$ for all $i$ is $n-r$,
thereby matching the number of parts of the partitions
$\sigma$ and $\tau$, including any trailing zeros. All
edges along the $X_i-A_{i+1}$ boundaries are $0$, and 
all along the $Y_i-T_i$ boundaries are specified by the 
parts of $\gamma_i$. The right and left-hand edges of 
$A_i$ and $A_{i+1}$ match. The same is true of $T_i$ and
$T_{i+1}$. Juxtaposing these edges creates subhives $T=\cup_i T_i$ 
and $A=\cup_i A_i$ appropriate to $K_{\sigma\zeta}$ and
$K_{\tau\eta}$. All the hive conditions are satisfied.

Conversely, reconstituting $H$ by inserting fixed edge parallelograms
$X_i$ and $Y_i$ between the various $T_i$ and $A_i$
corresponding to K-hives $T$ and $A$, always gives rise to
a K-hive, as required. This is because the necessary hive
conditions for all hives of type
R1 and R2 crossing $X_i-A_{i+1}$ and $T_i-Y_i$ boundaries,
respectively, are once again automatically satisfied. The
argument is precisely the same as that given previously.

This completes the proof of Theorem~\ref{Theo-Kbetafact}.
\qed


\end{document}



