\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\OneNumberAllTheorems
\usepackage{amscd}
\usepackage[all]{xy}
%\usepackage{verbatim}
%\usepackage{dsfont}
%\usepackage{MnSymbol}
\usepackage{tikz}
\usepackage{tikz-cd}
\usepackage{tkz-euclide}
%\usepackage{hyperref}
%\hypersetup{
% colorlinks=true,
% linkcolor=red,
% filecolor=magenta,
% urlcolor=cyan,
% citecolor=blue,
%}
%\urlstyle{same}
\usepackage{mathrsfs}
%\setlist{nolistsep}
%\graphicspath{converted_graphics}
%\theoremstyle{plain}
%\equalenv{corollary}{coro}
%\equalenv{definition}{defi}
%\equalenv{proposition}{prop}
%\equalenv{example}{exam}
\newcommand{\dsp}{\displaystyle}
\newcommand{\bi}[1]{\emph{#1}}
%\newcommand{\bi}[1]{\textbf{\textit{#1}}}
\newcommand{\xra}{\xrightarrow}
\newcommand{\CC}{\mathbb{C}}
\renewcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathscr{F}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\HH}{\mathbb{H}}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\gl}{GL}
\DeclareMathOperator{\End}{End}
%\newcommand{\spl}{\text{SL}}
%\newcommand{\gl}{\text{GL}}
\DeclareMathOperator{\spl}{SL}
\DeclareMathOperator{\dm}{dim}
\DeclareMathOperator{\dt}{det}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\ssi}{SI}
\DeclareMathOperator{\Rep}{Rep(Q,\beta)}
\DeclareMathOperator{\Id}{Id}
\DeclareMathOperator{\invariant}{I}
\DeclareMathOperator{\semi}{SI}
\DeclareMathOperator{\lam}{\lambda}
\newcommand{\unlam}{\underline{\lambda}}
\newcommand{\cone}{C(Q,\beta)}
\newcommand{\dmm}{\underline{\mathbf{dim}} }
\newcommand{\inv}[1]{\invariant(Q,{#1})}
\newcommand{\si}[1]{\semi(Q,{#1})}
%%%%%%%%% a placer avant \begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
\author{\firstname{Brett} \lastname{Collins}}
\address{Bucknell University\\
Mathematics Department\\
One Dent Dr.\\
Lewisburg, PA 17837, USA}
\email{bac043@bucknell.edu}
\thanks{The author was partially supported by the NSA under grant H98230-15-1-0022.}
%%%%% Sujet
\subjclass{16G20, 05E15}
\keywords{Quiver representations, semi-invariants, Littlewood--Richardson coefficients, Horn's Conjecture, branching rule, hive model.}
%%%%% Gestion
\DOI{10.5802/alco.143}
\datereceived{2018-05-23}
\daterevised{2020-07-08}
\dateaccepted{2020-08-10}
%%%%% Titre et résumé
\title[Generalized Littlewood--Richardson coefficients]{Generalized Littlewood--Richardson coefficients for branching rules of GL$(n)$ and extremal weight crystals}
\begin{abstract}
Following the methods used by Derksen--Weyman in~\cite{DW11}
and Chindris in~\cite{Chi08},
we use quiver theory to represent the generalized Littlewood--Richardson coefficients for the branching rule for the diagonal embedding of $\text{GL}(n)$ as the dimension of a weight space of semi-invariants. Using this, we prove their saturation and investigate when they are nonzero. We also show that for certain partitions the associated stretched polynomials satisfy the same conjectures as single Littlewood--Richardson coefficients. We then provide a polytopal description of this multiplicity and show that its positivity may be computed in strongly polynomial time. Finally, we remark that similar results hold for certain other generalized Littlewood--Richardson coefficients.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\section{Introduction}
\subsection{Context and motivation}
Littlewood--Richardson coefficients appear in many contexts in representation theory, such as the coefficients in the decomposition of a product of symmetric polynomials or the tensor product of irreducible representations of $\gl(n)$. One way to define Littlewood--Richardson coefficients is as follows: let $V$ be a complex vector space of dimension $n$ and $\lambda = (\lambda_1,\ldots, \lambda_n)$ a weakly decreasing sequence of $n$ integers. Denote the irreducible rational representation of $\gl(n)$
with highest weight $\lambda$ by $S^\lambda(V)$. Given three weakly decreasing sequences of~$n$ integers $\lambda(1), \lambda(2), \lambda(3)$, the Littlewood--Richardson coefficient $c^{\lambda(2)}_{\lambda(1),\lambda(3)}$ is defined to be the multiplicity of $S^{\lambda(2)}(V)$ in $S^{\lambda(1)}(V)\otimes S^{\lambda(3)}(V)$, that is,
\[
c^{\lambda(2)}_{\lambda(1),\lambda(3)} = \dm_\CC \Hom_{\gl(V)}(S^{\lambda(2)}(V), S^{\lambda(1)}(V) \otimes S^{\lambda(3)}(V)).
\]
Similarly, sums of products of these coefficients, which we call generalized Littlewood--Richardson coefficients throughout this paper, appear naturally in the decompositions of various algebraic objects. In particular, generalized Littlewood--Richardson coefficients describe the multiplicities in the branching rules of restricted representations of $\gl(n)$, as described in~\cite{HJ09} and~\cite{HTW05}. While there is no known way to describe the multiplicities in each of these branching rules using quiver theory, we show that we can do exactly such for one of them, that is, we describe the coefficients as the dimension of a weight space of semi-invariants for a certain quiver, dimension vector, and weight. More generally, we do this for the generalized Littlewood--Richardson coefficient
\begin{equation}\label{one}
f(\lambda(1),\ldots, \lambda(m)) \coloneqq
\sum c^{\lambda(1)}_{\alpha(1),\alpha(2)} c^{\lambda(2)}_{\alpha(2),\alpha(3)}\cdots c^{\lambda(m-1)}_{\alpha(m-1),\alpha(m)} c^{\lambda(m)}_{\alpha(m),\alpha(1)}
\end{equation}
for $m \geq 4$ and even, where the summation ranges over all partitions $\alpha(i)$. This multiplicity describes the coefficients arising from the branching rule for the diagonal embedding $\gl(n) \subseteq \gl(n) \times \gl(n)$ in the case $m=6$. We remark in the \hyperlink{section-others}{last section} that similar techniques likewise represent two other generalized Littlewood--Richardson coefficients in this manner.
Recently, Littlewood--Richardson coefficients have been of vital interest in geometric complexity theory which seeks to determine the complexity of computational problems by using tools from algebraic geometry and representation theory to provide lower bounds, and the complexity is quite commonly compared to that of computing certain multiplicities like Littlewood--Richardson coefficients. Understanding the complexity of certain cases of these generalized coefficients or even whether they're nonzero can then be used in comparison to other computational problems. A common technique in combinatorics is to associate a polytope to a multiplicity in such a way that the number of lattice points of the polytope is precisely this number. Because the polytope is defined by a system of linear inequalities, combinatorial optimization may then be used to determine the complexity of the multiplicities as well as the properties of the polytope.
Knutson and Tao~\cite{KT99} provided a polytopal description of Littlewood--Richardson coefficients, allowing them to give a combinatorial proof of the saturation of the coefficients (Theorem~\ref{LR-saturation}) and complete the proof of Horn's conjecture (Theorem~\ref{Horn}). Derksen and Weyman~\cite{DW00a} then reproved the saturation property in the context of quiver representations by using the saturation of weight spaces of semi-invariants. The motivation for this paper may then be summarized as providing an explicit quiver theoretic interpretation of these generalized Littlewood--Richardson coefficients in order to prove their saturation and use results of quiver theory to study their combinatorial and geometric properties.
\subsection{Main results}
\label{section:Introduction}
One of the main and most useful results is that of the saturation of this multiplicity.
\begin{theorem}\label{saturation-sun}
Let $\lambda(1),\ldots, \lambda(2k)$ be weakly decreasing sequences of $n$ integers for $k \geq 2$. For every integer $r \geq 1$,
\[
f(r\lambda(1),\ldots, r\lambda(2k)) \neq 0 \Longleftrightarrow
f(\lambda(1),\ldots, \lambda(2k)) \neq 0.
\]
\end{theorem}
We extend the results of~\cite{KT99} by using their hive models to provide a polytopal description of the generalized Littlewood--Richardson coefficients in Section~\ref{polytope}. By using results in combinatorial optimization theory and the above saturation property, we prove the following theorem.
\begin{theorem}\label{sun-complexity}
Determining whether the multiplicity~\eqref{one} is positive or not can be decided in polynomial time. Even more, it can be decided in strongly polynomial time in the sense of~\cite{Tar86}.
\end{theorem}
Horn's conjecture (Theorem~\ref{Horn}) relates the set of possible eigenvalues arising from a sum of Hermitian matrices to the nonvanishing of Littlewood--Richardson coefficients. To describe a corresponding statement of the conjecture to multiplicity~\eqref{one}, we need to define some notation. For an $m$-tuple $(I_1,\ldots, I_m)$ of subsets of $\{1,\ldots, n\}$, define the following weakly decreasing sequences of integers (the notation is explained in the \hyperref[notation]{subsection} at the end of this section):
\[
\unlam(I_i) = \begin{cases}
\lambda'(I_i) & i \text{ even} \\
\lambda'(I_i) -((|I_i| - |I_{i-1}| - |I_{i+1}|)^{n-|I_i|}) & i \text{ odd},
\end{cases}
\]
where we identify $I_0$ and $I_m$. Define the rational convex polyhedral cone $K(n,m) \subseteq \RR^{mn}$, $m \geq 4$ and even, to be all $m$-tuples $(\lambda(1),\ldots, \lambda(m))$ of weakly decreasing sequences of $n$ reals that satisfy $\sum_{i \text{ even}} |\lambda(i)| = \sum_{i \text{ odd}} |\lambda(i)|$ and
\begin{equation*}
\sum_{i \text{ even}} \sum_{j \in I_i} \lambda(i)_j \leq \sum_{i \text{ odd}} \sum_{j \in I_i} \lambda(i)_j
\end{equation*}
for every tuple $(I_1, \ldots, I_m)$ such that $\unlam(I_i)$, $1 \leq i \leq m$, are partitions and
\[
f(\unlam(I_1), \ldots, \unlam (I_m)) \neq 0.
\]
A corresponding statement of Horn's conjecture for this multiplicity is then as follows, where we describe the generalized eigenvalue problem for $f$ in Section~\ref{Hermitian}.
\begin{theorem}
\label{generalization-Horn}
The following statements are true.
\begin{enumerate}%[\normalfont(1)]
\item The cone $K(n,m) \subseteq \RR^{nm}$, $m \geq 4$ and even, consists of all $m$-tuples $(\lambda(1),\ldots, \lambda(m))$ of weakly decreasing sequences of $n$ reals satisfying $\sum_{i \text{ even}} |\lambda(i)| = \sum_{i \text{ odd}} |\lambda(i)|$ and
\[
\sum_{i \text{ even}} \sum_{j \in I_i} \lambda(i)_j \leq \sum_{i \text{ odd}} \sum_{j \in I_i} \lambda(i)_j
\]
for every tuple $(I_1, \ldots, I_m)$ such that the $\unlam(I_i)$, $1 \leq i \leq m$, are partitions and
\[
f(\unlam(I_1), \ldots, \unlam (I_m)) = 1.
\]
\item If $(\lambda(1),\ldots, \lambda(m)) \in K(n,m)$, then the tuple satisfies the generalized eigenvalue problem for $f$.
\item If $\lambda(1),\ldots, \lambda(m)$ are weakly decreasing sequences of $n$-integers, then
\[
(\lambda(1),\ldots, \lambda(m)) \in K(n,m) \Longleftrightarrow f(\lambda(1),\ldots,\lambda(m)) \neq 0.
\]
\item $\dm K(n,m) = mn-1$.
\end{enumerate}
\end{theorem}
In particular, this provides a recursive procedure for finding all nonzero generalized Littlewood--Richardson coefficients of this type.
We use this description to describe all facets of the cone of effective weights in the case $n=2,\,m=6$ and find the minimal set of inequalities on the $\lambda(i)$ (see Example~\ref{n=2} and the \hyperref[appendix]{Appendix}).
One consequence of this description of the sequences in the cone $K(n,m)$ is the following factorization formula.
\begin{theorem}\label{factorization}
Let $(\lambda(1), \ldots, \lambda(m)) \in K(n,m) \cap \Z^{mn-1}$. For any tuple of subsets $I=(I_1, \ldots, I_m)$ of $S=\{1,\ldots, n\}$ satisfying the conditions defining $K(n,m)$, we have the factorization
\[
f(\lambda(1),\ldots, \lambda(m)) = f(\lambda(1)^*,\ldots, \lambda(m)^*) \cdot f(\lambda(1)^\#,\ldots, \lambda(m)^\#),
\]
where
\begin{align*}
\lambda(p)^*& = (\lambda(p)_{i_{j_1}}, \ldots, \lambda(p)_{i_{j_r}}), %\quad
&&&I_j &= \{i_{j_1}, \ldots, i_{j_r}\}, \\
\lambda(p)^\# &= (\lambda(p)_{\tilde{i}_{j_1}}, \ldots, \lambda(p)_{\tilde{i}_{j_{n-r}}}), \quad &&&S \backslash I_j &= (\tilde{i}_{j_1}, \ldots, \tilde{i}_{j_{n-r}}).
\end{align*}
\end{theorem}
In addition, we investigate the stretched Littlewood--Richardson polynomials $f(N\lambda(1),\ldots, N\lambda(m))$ for certain $\lambda(1),\ldots, \lambda(m)$ in Section~\ref{stretched-polynomials}. The tuples we investigate turn out to have the same behavior as the stretched Littlewood--Richardson polynomials for a single coefficient, namely, they satisfy conjectures of King, Tollu, and Toumazet~\cite{KTT04} and of Fulton, providing evidence that the conjectures for the stretched polynomials for a single Littlewood--Richardson coefficient extend to those of generalized Littlewood--Richardson coefficients. Our examples are based on corresponding examples in~\cite{Fei15} for the quiver associated to a single Littlewood--Richardson coefficient. As opposed to Fei's examples, ours do not always lie on an extremal ray of the cone of effective weights.
The organization of this paper is as follows. In Section~\ref{preliminaries} we provide background on quiver invariant theory and state a certain saturation property for effective weights of quivers proved by Derksen and Weyman~\cite{DW00a}. The quiver associated to multiplicity~\eqref{one} is defined in Section~\ref{section-saturation} and its saturation property is proven. After recalling more detailed descriptions of the facets of the cone of effective weights for acyclic quivers in Section~\ref{section-facets}, we describe the facets of our quiver in Section~\ref{section-facets-quivers}, which allows a description of the Horn-type inequalities of the multiplicity in Section~\ref{section-Horn}. A moment map description of the cone associated to our quiver is provided by the generalized eigenvalue problem in Section~\ref{Hermitian} while we use the Horn-type inequalities to prove a factorization formula in Section~\ref{section-factorization}. In Section~\ref{stretched-polynomials}, we explicitly calculate the stretched Littlewood--Richardson polynomials in certain cases and verify that they share some of the same properties as the stretched polynomials for single Littlewood--Richardson coefficients. We provide a polytopal description of the multiplicity in Section~\ref{polytope} and prove the complexity of computing its positivity. Finally, we discuss in Section~\ref{section-others} that our methodology can be used to prove similar results for other generalized Littlewood--Richardson coefficients, in particular, for a multiplicity arising from another branching rule of $\gl(n)$ and a multiplicity related to extremal weight crystals. We state without proof the corresponding main results for these multiplicities.
\subsection{Relation to existing literature}
Horn made his famous \hyperref[Horn]{conjecture} in 1962~\cite{Hor62}, yet the motivation for it goes back to Weyl in 1912~\cite{Wey12}. Weyl was interested in necessary and sufficient inequalities on the eigenvalues of Hermitian matrices such that one matrix was the sum of the other two due to questions in solid mechanics. Many advances were made over the next 50 years (see~\cite{Ful97b} for a survey of the history and results pertaining to this problem), and the connection was made between the eigenvalue problem and Schubert calculus, resulting in Horn's conjecture.
The second part of the conjecture provides a recursive process for determining all triples $(I_1,I_2,I_3)$ of subsets of $\{1,\ldots, n\}$ which are necessary to determine if $(\lambda(1),\lambda(2), \lambda(3))$ is such a solution. The first major step in proving the conjecture was made when Klyachko~\cite{Kly98} found necessary and sufficient homogeneous linear inequalities for the eigenvalues. It remained, however, to find a minimal set of inequalities. Klyachko had claimed that these inequalities were independent, but Woodward~\cite{AW98} showed that many inequalities were redundant, and later Belkale~\cite{Bel01} showed that all the inequalities for which $c^{\lambda(I_2)}_{\lambda(I_1),\lambda(I_3)} > 1$ are redundant, which includes the set found by Woodward. The remaining inequalities would be irredundant by a theorem of Klyachko provided the saturation of Littlewood--Richardson coefficients.
\begin{theorem}[Saturation conjecture]\label{LR-saturation}
For weakly decreasing sequences of $n$ integers $\lambda, \mu, \nu$, $c^{N\nu}_{N \lambda, N\mu} \neq 0$ for some positive $N$ if and only if $c^{\nu}_{\lambda, \mu} \neq 0.$
\end{theorem}
The statement that $c^{\nu}_{\lambda, \mu} \neq 0$ implies $c^{N\nu}_{N\lambda,N\mu} \neq 0$ for all positive integers $N$ follows immediately from the Littlewood--Richardson rule or by these multiplicities forming a semigroup (see~\cite{Zel99}). Knutson, Tao, and Woodward~\cite{KTW04}
used combinatorial gadgets called honeycombs and hive models to prove the saturation conjecture, completing the proof of Horn's conjecture; a similar proof of the conjecture using only hive models is found in~\cite{Buc00}. A geometric proof of the saturation conjecture using Schubert calculus was also given by Belkale~\cite{Bel06}. Derksen, Schofield, and Weyman~\cite{DSW07} showed that the number of subrepresentations of a specific dimension of a given dimension vector for an acylic quiver may be determined using Schubert calculus, which is why Derksen and Weyman defined a specific quiver and dimension vector for which this number was a given Littlewood--Richardson coefficient. In this way, they were able to extend results about Littlewood--Richardson coefficients to the quiver setting and prove the saturation conjecture for Littlewood--Richardson coefficients in~\cite{DW00a} by using results from quiver theory.
The multiplicity~\eqref{one} for the branching rule of the diagonal embedding of $\gl(n)$ was first proven in~\cite{Kin71}. The proof may also be found in~\cite{HTW05} (see~\cite{Koi89} and~\cite{HJ09} for further discussion).
\subsection{Notation}\label{notation}
A partition $\lambda$ of length $n$ is a weakly decreasing sequence of $n$ positive integers, denoted $\lambda = (\lambda_1, \ldots, \lambda_n)$.
We identify two partitions $\lambda$ and $\mu$ if one can be written as the other by adjoining (finitely) many zeros at the end of the sequence. As such, we say $\lambda$ is a partition of at most $n$ (nonzero) parts if $\lambda = (\lambda_1, \ldots, \lambda_n) \in \Z^n$ with $\lambda_1 \geq \ldots \geq \lambda_n \geq 0$. If $\lambda = (\lambda_1, \ldots, \lambda_n)$ and $\mu$ are weakly decreasing sequences (not necessarily of integers), we define $r \lambda = (r\lambda_1, \ldots, r\lambda_n)$ for $r \in \RR^+$ and $\lambda + \mu$ is defined by adding componentwise after extending the sequences by zeros as necessary. Every partition $\lambda$ may be identified with a Young diagram, and we denote the conjugate partition as $\lambda'$, which is the partition associated to the reflection of the Young diagram of $\lambda$ across the main diagonal, \ie switching the rows and columns. If $I=\{z_1 < \cdots < z_r\}$ is an $r$-tuple of integers, $\lambda(I)$ is defined by $\lambda(I) = (z_r-r, \ldots, z_1-1)$. For an integer $c$ and a non-negative integer $r$, we denote the $r$-tuple $(c,\ldots, c)$ more simply as $(c^r)$. For a sequence of real numbers $\lambda = (\lambda_1, \ldots, \lambda_n)$, we define $|\lambda| = \sum_{i=1}^n \lambda_i$.
\looseness-1
For a complex vector space $V$ of dimension $n$ and a weakly decreasing sequence of $n$ integers $\lambda = (\lambda_1, \ldots, \lambda_n)$, we denote the irreducible rational representation of $\gl(V)$ with highest weight $\lambda$ as $S^\lambda(V)$. Given any three weakly decreasing sequences of $n$ integers $\lambda(1), \lambda(2), \lambda(3)$, the Littlewood--Richardson coefficient $c_{\lambda(1), \, \lambda(3)}^{\lambda(2)}$ is defined to be
\[
c_{\lambda(1), \, \lambda(3)}^{\lambda(2)} = \dm_\CC \Hom_{\gl(V)}(S^{\lambda(2)}(V), S^{\lambda(1)}(V) \otimes S^{\lambda(3)}(V)),
\]
that is, the multiplicity of $S^{\lambda(2)}(V)$ in $S^{\lambda(1)}(V) \otimes S^{\lambda(3)}(V)$.
%\vspace{.2in}
\section{Preliminaries}\label{preliminaries}
\subsection{Preliminaries}
A quiver $Q = (Q_0,Q_1,t,h)$ consists of a finite set of vertices $Q_0$, a finite set of arrows $Q_1$, and functions $t,h : Q_1 \to Q_0$ that assign the tail $ta$ and head $ha$ of each arrow $a$, commonly denoted $ta \xra{a} ha$. Note that we allow multiple arrows between two vertices and loops in the directed graph $Q$.
Throughout this paper we always work over the complex numbers $\CC$. A representation $V$ of $Q$ is a family of finite-dimensional vector spaces (over $\CC$) $\{V(x) \mid x \in Q_0\}$ together with a family of linear transformations $\{V(a):V(ta) \to V(ha) \mid a \in Q_1\}$. For a representation $V$, its dimension vector $\dmm \, V$ is defined by $\dmm \, V(x) = \dm_\CC V(x)$ for all $x \in Q_0$.
The dimension vectors of representations of $Q$ then lie in $\Gamma = \Z^{Q_0}$, the set of integer-valued functions on $Q_0.$
For each vertex $x \in Q_0$, there is a simple representation $S_x$ defined by the dimension vector $e_x(y) = \delta_{x,y}$ for all $y \in Q_0$, where $\delta_{x,y}$ is the Kronecker delta.
Given two representations $V$ and $W$ of $Q$, define a morphism $\phi : V \to W$ of representations to be a collection of linear maps $\{\phi(x): V(x) \to W(x) \mid x \in Q_0\}$ such that for every arrow $a \in Q_1$ we have $\phi(ha)V(a) = W(a) \phi(ta)$. Define $\Hom_Q(V,W)$, or simply $\Hom(V,W)$, to be the $\CC$-vector space of all morphisms from $V$ to $W$. We thus obtain the abelian category $\text{Rep}(Q)$ of all quiver representations of $Q$. We call $V'$ a subrepresentation of $V$ if $V'(x)$ is a subspace of $V(x)$ for all vertices $x \in Q_0$ and $V'(a) = V(a)|_{V'(ta)}$ for all arrows $a \in Q_1$.
For any $\alpha, \beta \in \Gamma$, define the Euler form by
\[
\langle \alpha, \beta \rangle = \dsp \sum_{x \in Q_0} \alpha(x) \beta(x) - \sum_{a \in Q_1} \alpha(ta) \beta(ha).
\]
\subsection{Semi-invariants for quivers}
For a dimension vector $\beta$ of a quiver $Q$, the representation space of $\beta$-dimensional representations of $Q$ is defined as
\[
\Rep = \bigoplus_{a \in Q_1} \Hom \left( \CC^{\beta(ta)}, \CC^{\beta(ha)} \right).
\]
If $\gl(\beta) = \prod_{x \in Q_0} \gl(\beta(x))$, then there is a natural action of $\gl(\beta)$ on $\Rep$ given by simultaneous conjugation: for $g = (g(x))_{x \in Q_0} \in \gl(\beta)$ and $V = (V(a))_{a \in Q_1} \in \Rep$, $g \cdot V$ is defined by
\[
(g \cdot V)(a) = g(ha)V(a)g(ta)^{-1} \quad \forall a \in Q_1.
\]
Hence, $\Rep$ is a rational representation of the linearly reductive group $\gl(\beta)$ and the $\gl(\beta)$-orbits parameterize the isomorphism classes of $\beta$-dimension representations of $Q$. If $Q$ is without oriented cycles, there is only one closed $\gl(\beta)$-orbit in $\Rep$ (specifically, the orbit of the unique $\beta$-dimensional semisimple representation $\bigoplus_{x \in Q_0} S_x^{\beta(x)})$, so the invariant ring $\CC[\Rep]^{\gl(\beta)}$ is simply $\C$. However, while there are only constant $\gl(\beta)$-invariant polynomial functions on $\Rep$, the action descends to that of the subgroup $\spl(\beta)$, and the invariant ring under the action of this group is highly nontrivial.
Let $\si{\beta} = \C[\Rep]^{\spl(\beta)}$ be the ring of semi-invariants. Since $\gl(\beta)$ is linearly reductive and $\spl(\beta)$ is the commutator subgroup of $\gl(\beta)$, we have the weight space decomposition
\[
\si{\beta} = \bigoplus_{\sigma \in X^*(\gl(\beta))} \si{\beta}_\sigma,
\]
where $X^*(\gl(\beta))$ is the group of rational characters of $\gl(\beta)$ and
\[
\si{\beta}_\sigma = \{f \in \C[\Rep] \mid g \cdot f = \sigma(g)f \; \; \forall g \in \gl(\beta)\}
\]
is the space of semi-invariants of weight $\sigma$. A character (or weight) of $\gl(\beta)$ is of the form
\[
\{g(x) \mid x \in Q_0\} \in \gl(\beta) \mapsto \prod_{x \in Q_0} (\det g(x))^{\sigma(x)}
\]
for $\sigma(x) \in \Z$ for all $x \in Q_0$, so we may identify $X^*(\gl(\beta))$ with $\Z^{Q_0}$. For an integer-valued function $\alpha$ on $Q_0$, define $\sigma = \langle \alpha, \cdot \rangle$ by
\[
\sigma(x) = \langle \alpha, e_x \rangle = \alpha(x) - \sum_{y \to x} \alpha(y), \quad \forall x \in Q_0.
\]
One can similarly define $\sigma = \langle \cdot, \alpha \rangle.$
Given a quiver $Q$ and dimension vector $\beta$, define $\Sigma(Q,\beta)$ to be the set of (integral) effective weights:
\[
\Sigma(Q,\beta) = \{\sigma \in \Z^{Q_0} \mid \si{\beta}_\sigma \neq 0\}.
\]
Schofield~\cite{Sch92} constructed determinantal semi-invariants for quivers that proved to be quite useful in studying the ring of semi-invariants. Derksen and Weyman~\cite{DW00a} (see also~\cite{SB01}) showed that these semi-invariants in fact span all spaces of semi-invariants. An important consequence of this result is the following saturation property. We use the notation $\beta' \hookrightarrow \beta$ to mean that every $\beta$-dimensional representation has a subrepresentation of dimension $\beta'$. If $\sigma \in \R^{Q_0}$ is a real-valued function on the set of vertices $Q_0$ and $\beta$ is an integer-valued function on $Q_0$, define $\sigma(\beta)$ by
\[
\sigma(\beta) = \sum_{x \in Q_0} \sigma(x) \beta(x).
\]
\begin{theorem}[\cite{DW00a}, Theorem 3]
\label{saturation}
Let $Q$ be a quiver without oriented cycles and $\beta$ is a dimension vector of $Q$. Then
\[
\Sigma(Q,\beta) = \{\sigma \in \Z^{Q_0} \mid \sigma(\beta) = 0 \text{ and } \sigma(\beta') \leq 0 \; \forall \beta' \hookrightarrow \beta \}.
\]
In particular, $\Sigma(Q,\beta)$ is saturated, that is, if $\sigma$ is a weight and $r \geq 1$ an integer,
\[
\si{\beta}_\sigma \neq 0 \Longleftrightarrow \si{\beta}_{r \sigma} \neq 0.
\]
\end{theorem}
Crawley-Boevey and Geiss~\cite{CBG02} also show how the saturation of semi-invariants is related to the saturation of Littlewood--Richardson coefficients and Weyl's eigenvalue problem, explaining why quiver representations provide a natural setting for these classical problems.
We will later use this theorem to prove the saturation of the multiplicity~\eqref{one} and give an explicit description of the nonzero generalized Littlewood--Richardson coefficients of this form.
%\vspace{.2in}
\section{Branching rules and weight spaces of semi-invariants }\label{section-saturation}
\subsection{Saturation theorem}
In this section we will show that the multiplicity~\eqref{one} described in the branching rule for the diagonal embedding for $\gl(n)$ stated in the introduction arises as the dimension of the weight space of semi-invariants for a certain quiver and dimension vector which we construct. A proof of the saturation of the multiplicity will then follow from Theorem~\ref{saturation}.
\subsection{Sun quiver}
Construct a quiver $Q$ in the following way: for $k \geq 2$, start with a regular $2k$-gon with the vertices labeled $(n,i)$, $1 \leq i \leq 2k$, which we call the central vertices, and an arrow connecting $(n,i)$ with $(n,i+1)$ (we will always consider $(n,2k+1) = (n,1)$), where the arrows alternate in direction. At each central vertex $(n,i)$ attach an equioriented $A_n$ quiver, called a flag and denoted $\F(i)$, where $\F(i)$ goes out of the central vertex if $i$ is odd and into the central vertex if $i$ is even. We will later associate each flag with a weakly decreasing sequence with at most $n$ parts and each central arrow with some arbitrary partition. For instance, for $k=3$ the quiver looks like
\[
\xymatrix{&&&& \ar@{~>}[dl]^{\lambda(2)} \\
&& 3 \ar@{~>}[ul]_{\lambda(3)} & 2 \ar[l]_{\alpha(2)} \ar[dr]^{\alpha(1)} \\
\ar@{~>}[r]_{\lambda(4)} & 4 \ar[ur]^{\alpha(3)} \ar[dr]_{\alpha(4)} &&& 1 \ar@{~>}[r]_{\lambda(1)}& \\
&& 5 \ar@{~>}[dl]_{\lambda(5)} & 6 \ar[l]^{\alpha(5)} \ar[ur]_{\alpha(6)} \\
&&&& \ar@{~>}[ul]_{\lambda(6)}}
\]
with $n$ vertices along each flag, denoted here by wavy arrows. Label the $j^{th}$ vertex along the $i^{th}$ flag by $(j,i)$, numbered so that $(n,i)$ denotes each center vertex or simply $i$ when it is understood.
Define the dimension vector $\beta$ as $\beta(j,i) = j$ for each $1\leq i \leq 2k$ and $1 \leq j \leq n$. We will show that the generalized Littlewood--Richardson coefficient in~\eqref{one} is the dimension of the weight space of semi-invariants for a certain weight for this quiver and the associated dimension vector $\beta$.
Throughout the rest of this paper all results except in Section~\ref{section-others} will be for $k \geq 2$ and the quiver $Q$ with $2k$ flags, which we call the \bi{sun quiver} or the \bi{$2k$-sun quiver} when we want to emphasize the number of flags, and $\beta$ is the dimension vector defined by $\beta(j,i) = j$.
\begin{lemma}
\label{sun-2}
Let $\sigma \in \Z^{Q_0}$ be a weight for the $2k$-sun quiver, $k \geq 2$. If $\dm \si{\beta}_\sigma \neq 0$, then the weight must satisfy $(-1)^i \sigma(j,i) \geq 0$ for all $1 \leq j \leq n, \, 1 \leq i \leq 2k$. Furthermore,
\[
\dm \si{\beta}_\sigma = \sum c^{\phi(1)}_{\alpha(1), \alpha(2)} c^{\phi(2)}_{\alpha(2), \alpha(3)} \, \cdots \, c^{\phi(2k)}_{\alpha(2k), \alpha(1)},
\]
where the sum ranges over all partitions $\alpha(1), \ldots, \alpha(2k),$ and
\[
\phi(i) = (n^{(-1)^i\sigma(n,i)}, \ldots, 1^{(-1)^i \sigma(1,i)})'
\]
for $1 \leq i \leq 2k$.
\end{lemma}
\begin{proof}
Define $V_j(i) = \CC^{\beta(j,i)}$ as the vector space assigned to vertex $(j,i)$. A standard calculation using Cauchy's rule (see~\cite{Ful97a}, page 121) shows that the affine coordinate ring $\CC[\Rep]$ decomposes as a sum of tensor products of irreducible representations of the general linear groups $\gl(V_j(i))$ with contributions from each of the flags and central arrows. Specifically, if $\F(i)$ is a flag going out of a central vertex, meaning when $i$ is odd, then the $n-1$ arrows of the flag contribute
\[
\dsp \bigoplus_{\phi^1(i), \ldots, \phi^{n-1}(i)} S^{\phi^1(i)} V_1(i)^* \otimes \bigotimes_{j=2}^{n-1} (S^{\phi^{j-1}(i)} V_j(i) \otimes S^{\phi^j(i)} V_j(i)^*) \otimes S^{\phi^{n-1}(i)} V_n(i)
\]
for some partitions $\phi^1(i), \ldots, \phi^{n-1}(i)$. We want to determine when these terms give nonzero semi-invariants of weight $\sigma$. Because the $j^{th}$ term of $\spl(\beta)$ acts trivially on each $S^{\phi^m(i)} V_k(i)$ whenever $j \neq k$, the terms of $\spl(\beta)$ distribute to the corresponding terms of the sum across the tensor products.
The term $(S^{\phi^1(i)} V_1(i)^*)^{\spl(V_1(i))} \neq 0$ if and only if $\phi^1(i)$ is of size $w \times \dm V_1(i) = w \times 1$ for some $w \in \Z_{\geq 0}$.
Hence, in this case, the space is one-dimensional and is spanned by a semi-invariant of weight $-w$. Therefore, $(S^{\phi^1(i)} V_1(i)^*)^{\spl(V_1(i))}$ contains a nonzero semi-invariant of weight $\sigma (1,i)$ if and only if $\sigma(1,i) < 0$ and $\phi^1(i)$ is of size $-\sigma(1,i)\times 1 = (1^{-\sigma(1,i)})'$. We know from this that $(S^{\phi^1(i)} V_1(i)^*)^{\spl(V_1(i))}$ is nonzero if and only if it is one-dimensional.
Next, $(S^{\phi^1(i)} V_2 (i) \otimes S^{\phi^2(i)} V_2(i)^*)^{\spl(V_2(i))}$ is nonzero if and only if $\phi^2(i)_p - \phi^1(i)_p = k \in \Z_{\geq 0}$ for all $p$. That is, $\phi^2(i)$ is $\phi^1(i)$ plus some extra columns, which must be of length $\dm V_2(i) =\beta(i,2) = 2$. In this case, the space being nonzero is equivalent to it being spanned by a semi-invariant of weight equal to the negative of the number of extra columns. Hence, $(S^{\phi^1(i)} V_2 (i) \otimes S^{\phi^2(i)} V_2(i)^*)^{\spl(V_2(i))}$ contains a semi-invariant of weight $\sigma(2,i)$ if and only if the space is one-dimensional and $\phi^2(i)=(2^{-\sigma(2,i)}, 1^{-\sigma(1,i)})'.$
Reasoning this way and continuing by sorting the spaces of semi-invariants in $\si{\beta}$ of weight $\sigma$, we have that $\phi^1(i)$ is of size $-\sigma(1,i) \times 1$ and $\phi^j(i)$ is attained from $\phi^{j-1}(i)$ by adjoining a rectangle of size $-\sigma(j,i) \times j$ to the left of it. Thus, $\phi^{n-1}(i) = ((n-1)^{-\sigma(n-1,i)}, \ldots, 1^{-\sigma(1,i)})'$ and the contribution of the flag $\F(i)$ for odd $i$ to $\si{\beta}_{\sigma}$ is precisely $S^{\phi^{n-1}(i)} V_n(i)$.
Similarly, if $\F(i)$ is a flag going into a central vertex, meaning $i$ is even, then $\sigma(j,i) \geq 0$ for all $1 \leq j \leq n-1$ and the contribution of the flag $\F(i)$ to $\dm \si{\beta}_{\sigma}$ is $\dm S^{\phi^{n-1}(i)} V_n(i)^*$ with
\[
\phi^{n-1}(i) = ((n-1)^{\sigma(n-1,i)}, \ldots, 1^{\sigma(1,i)})'.
\]
In addition, the $2k$ central arrows give unspecified partitions $\alpha_i$ with at most $n$ parts each. By taking into account the weights at the central vertices and denoting $V_n(i)$ as simply $V(i)$, we may tensor the contributions from the central vertices to the space of semi-invariants with appropriate powers of the determinant to obtain $\gl$-representations, the dimensions of which will be the Littlewood--Richardson coefficients we want. To be precise, we get
\[
\begin{aligned}
\multicolumn{2}{l}{$\dm \left((S^{\phi^{n-1}(2i-1)}V(2i-1) \otimes S^{\alpha_{2i-2}} V(2i-1)^* \otimes S^{\alpha_{2i-1}}V(2i-1)^* \right.$}
\\
\left. \otimes \dt_{V(2i-1)}^{-\sigma(n,2i-1)})^{\gl(V(2i-1))}\right)
&\Mk =\Mk c^{\phi(2i-1)}_{\alpha_{2i-2}, \alpha_{2i-1}}
\\%\\
\dm \Mk \left(\Mk (S^{\phi^{n-1}(2i)}V(2i)^* \Mk \otimes \Mk S^{\alpha_{2i}} V(2i) \Mk \otimes\Mk S^{\alpha_{2i-1}}V(2i) \Mk \otimes \Mk \dt_{V(2i)}^{-\sigma(n,2i)})^{\gl(V(2i))} \Mk \right) &\Mk =\Mk c^{\phi(2i)}_{\alpha_{2i-1}, \alpha_{2i}}
\end{aligned}
\]
for each $i=1, \ldots, k$ (recall that we consider the central vertex $(n,2k)$ to be the same as $(n,0)$ and so on). Putting these together, the dimension of $\si{\beta}_{\sigma}$ is as stated.
\end{proof}
\looseness-1
For weakly decreasing sequences $\lambda(1), \ldots, \lambda(2k) $ of $n$ integers, define the weight $\sigma_1$ as
\begin{equation}
\label{weight-sigma_1}
\sigma_1(j,i) = \begin{cases}
(-1)^i(\lambda(i)_j - \lambda(i)_{j+1}) & 1 \leq i \leq 2k, \, 1 \leq j \leq n-1 \\
(-1)^i \lambda(i)_n & 1 \leq i \leq 2k, \, j = n. \end{cases}
\end{equation}
The following is immediate from calculating what the $\phi(i)$ are with respect to this weight.
\begin{lemma}
\label{si-saturation}
Let $\lambda(1),\ldots, \lambda(2k)$, $k\geq 2$, be weakly decreasing sequences of $n$ integers. Then for every integer $r \geq 1$, we have
\[
f(r \lambda(1), \ldots, r\lambda(2k)) = \sum c^{r\lambda(1)}_{\alpha(1), \alpha(2)} c^{r\lambda(2)}_{\alpha(2), \alpha(3)} \, \cdots \, c^{r\lambda(2k)}_{\alpha(2k), \alpha(1)} = \dm \si{\beta}_{r\sigma_1}.
\]
In particular, when $k=3$ and $r=1$ the dimension of this weight space of semi-invariants is the multiplicity of the branching rule in \textup{(}\ref{one}\textup{)}.
\end{lemma}
\begin{proof}
Because the general case is proven in precisely the same way, assume $r=1$. The proof is then the same as that of Lemma~\ref{sun-2} because $\phi(i) = \lambda(i)$ with this weight.
\end{proof}
\begin{rema}
While it is clear that $\lambda(1),\ldots, \lambda(2k)$ must be partitions if the multiplicity $f(\lambda(1),\ldots, \lambda(2k))$ is to be nonzero, this is verified from the conditions for $\sigma$ in Lemma~\ref{sun-2} and the description of $\sigma_1$.
\end{rema}
\begin{proof}[Proof of Theorem~\ref{saturation-sun}]
By representing the multiplicity as the dimension of a weight space of semi-invariants as in Lemma~\ref{si-saturation}, the saturation of this multiplicity immediately follows from Theorem~\ref{saturation}.
\end{proof}
\begin{rema}
In this way, we have written the generalized Littlewood--Richardson coefficient $f(\lambda(1), \ldots, \lambda(m))$ as the dimension of a certain weight space of semi-invariants of some quiver. However, we can only express the generalized Littlewood--Richardson coefficient in terms of quiver invariant theory when $m$ is even and at least four. When $m \geq 3$ is odd, this process fails because the first and last flags will be oriented the same direction which would require the central arrow connecting the first and last central vertices to be pointed both directions, an impossibility, while if $m=2$ we would have an oriented cycle.
\end{rema}
%\vspace{.2in}
\section{The facets of the cone of effective weights}\label{section-facets}
In this section we provide the necessary background for the description of the facets of the cone of effective weights for the sun quiver given in the next section. For a quiver $Q$, recall the notations $\sigma(\beta)$ and $\beta' \hookrightarrow \beta$ for a real-valued function $\sigma \in \RR^{Q_0}$ and dimension vector $\beta$ as defined immediately preceding Theorem~\ref{saturation}.
The cone of effective (real) weights $C(Q,\beta)$ is defined as
\[
C(Q,\beta) = \{\sigma \in \RR^{Q_0} \mid \sigma(\beta) = 0 \text{ and } \sigma(\beta') \leq 0 \, \forall \beta' \hookrightarrow \beta\}.
\]
Note that the set of lattice points is precisely $\Sigma(Q,\beta)$.
The condition $\sigma(\beta)=0$ is clearly necessary for $\sigma$ to be effective. This is because the action of the one-dimensional torus $\{(t \Id_{\beta(i)})_{i \in Q_0} \mid t \in k \backslash \{0\}\}$ on $\Rep$ is trivial, so if $f$ is a nonzero semi-invariant of weight $\sigma$ and $g_t = (t\Id_{\beta(i)})_{i \in Q_0} \in \gl(\beta)$, then
\[
g_t \cdot f = t^{\sigma(\beta)} \cdot f,
\]
which implies $\sigma(\beta)=0$. Surprisingly, satisfying a certain set of linear homogenous inequalities is sufficient for a weight to be effective (see Theorems~\ref{spanning} and~\ref{facet-decomp} below).
King provided a numerical criterion for $\sigma$-(semi-)stability for finite-dimensional algebras based on the Hilbert--Mumford criterion from GIT, which we now recall.
\begin{theorem}[\cite{Kin94}] Let $Q$ be a quiver, $\beta$ a dimension vector, and $V \in \Rep$. Suppose $\sigma \in \Z^{Q_0}$ is a weight such that $\sigma(V) = 0$. Then
\begin{enumerate}%[\normalfont(1)]
\item $V$ is $\sigma$-semi-stable if and only if $\sigma(\dmm \,{V'}) \leq 0$ for every subrepresentation $V'$ of $V$;
\item $V$ is $\sigma$-stable if and only if $\sigma(\dmm \, {V'}) < 0$ for every proper nontrivial subrepresentation $V'$ of $V$.
\end{enumerate}
We call $\beta$ \emph{$\sigma$-(semi)-stable} if there exists a $\sigma$-\textup{(}semi-\textup{)}stable representation in $\Rep$.
\end{theorem}
King's numerical criterion is amazingly useful because it reduces the determination of (semi-)stability of a representation from subrepresentations to dimension vectors of these subrepresentations, of which there are only finitely many.
Schofield defined determinantal semi-invariants which span the weight spaces of semi-invariants, and together with his study of general representations the set $\Sigma(Q,\beta)$ may be described in the following way.
\begin{theorem}[{\cite[Theorem 3]{DW00a}}]
\label{spanning}
Let $Q$ be a quiver and $\beta$ a sincere dimension vector, \ie $\beta(x) \neq 0$ for all $x \in Q_0$. If $\sigma = \langle \alpha, \cdot \rangle \in \Z^{Q_0}$ is a weight with $\alpha \in \Z^{Q_0}$, then the following statements are equivalent:
\begin{enumerate}%[\normalfont(1)]
\item $\dm \si{\beta}_\sigma \neq 0;$
\item $\sigma(\beta) = 0$ and $\sigma(\beta') \leq 0$ for every $\beta' \hookrightarrow \beta;$
\item $\alpha$ is a dimension vector, $\sigma(\beta) = 0$, and $\alpha \hookrightarrow \alpha + \beta$.
\end{enumerate}
\end{theorem}
\looseness-1
The following result is proved by the previous theorem and is quite useful in practice.
\begin{lemma}[{Reciprocity Property \cite[Corollary 1]{DW00a}}] %\emph{()}
\label{reciprocity}
For any dimension vectors $\alpha, \beta$ and quiver $Q$ without oriented cycles, we have
\[
\dm \si{\beta}_{\langle \alpha, \cdot, \rangle} = \dm \si{\alpha}_{-\langle \cdot, \beta \rangle}.
\]
\end{lemma}
Denote this common value of the dimensions of the weight spaces by $\alpha \circ \beta$. By the saturation of effective weights (Theorem~\ref{saturation}) and the reciprocity property, we have
\[
\alpha \circ \beta \neq 0 \Longleftrightarrow r\alpha \circ s \beta \neq 0, \; \forall r,s \geq 1.
\]
A dimension vector $\beta \in \Z_{\geq 0}^{Q_0}$ is called a \emph{Schur root} if there exists a $\beta$-dimensional representation $V$, called a \emph{Schur representation}, such that $\End_Q(V,V) \cong \CC$.
\begin{theorem}[{\cite[Corollary 5.2]{DW11}}]
\label{facet-decomp}
Let $Q$ be a quiver without oriented cycles and $N$ vertices, and $\beta$ a Schur root. Then
\begin{enumerate}%[\normalfont(1)]
\item $\dm C(Q, \beta) = N-1$, and
\item $\sigma \in C(Q,\beta)$ if and only if $\sigma(\beta) = 0$ and $\sigma(\beta_1) \leq 0$ for every decomposition $\beta = c_1 \beta_1 + c_2 \beta_2$ with $\beta_1, \beta_2$ Schur roots, $\beta_1 \circ \beta_2 = 1$, and $c_i = 1$ whenever $\langle \beta_i, \beta_i \rangle < 0$. Moreover, this list of linear homogeneous inequalities is minimal.
\end{enumerate}
\end{theorem}
The following theorem is useful for calculating whether or not a dimension vector is Schur.
\begin{theorem}[{\cite[Theorem 6.1]{Sch92}}]
\label{Schofield-Schur}
Let $\beta \in \Z_{\geq 0}^{Q_0}$ be a dimension vector. The following are equivalent:
\begin{enumerate}%[\normalfont(1)]
\item $\beta$ is a Schur root;
\item $\sigma_\beta(\beta') < 0$ for all $\beta' \hookrightarrow \beta$, $\beta' \neq 0,\, \beta$, where $\sigma_\beta = \langle \beta, \cdot \rangle - \langle \cdot, \beta \rangle.$
\end{enumerate}
\end{theorem}
These results allow a precise description of the facets of $C(Q,\beta)$ for a quiver $Q$ without oriented cycles and $\beta$ a Schur root; see Theorem 5.1 in~\cite{DW11} for the general statement.
%\vspace{.2in}
\section{The facets of the cone of effective weights for the sun quiver}\label{section-facets-quivers}
In order to use the results in the previous section to describe the facets of $C(Q,\beta)$ for the sun quiver, we'll first show that the dimension vector $\beta$ is Schur and determine conditions on the $\beta_1'$s that can appear in the decompositions.
\begin{lemma}
\label{Schur-root}
The dimension vector $\beta$ for the sun quiver is Schur.
\end{lemma}
\begin{proof}
The dimension vector $\beta$ is indivisible, meaning the greatest common divisor of its coordinates is one. By a result of Kac
(\cite[Theorem B(d)]{Kac82}),
to show $\beta$ is Schur, it suffices to show that $\beta$ is in the fundamental region of the graph, meaning that the support of $\beta$ is a connected graph and $\tau_i(\beta) \leq 0$ for all vertices $i \in Q_0$, where $e_i$ denotes the dimension vector of the simple representation at vertex $i$ and $\tau_i(\cdot) \coloneqq \langle e_i, \cdot \rangle + \langle \cdot, e_i \rangle$. This is immediately checked to hold for all $n \geq 1$.
\end{proof}
\begin{coro}
\label{dim-cones}
For the sun quiver $Q$, $\dm C(Q,\beta) = mn-1$.
\end{coro}
\begin{proof}
This immediately follows from Lemma~\ref{Schur-root} and Theorem~\ref{facet-decomp}.
\end{proof}
Now consider the following dimension vectors $\beta_1$ for the sun quiver, where $e_{(j,i)}$ denotes the dimension vector of the simple representation at vertex $(j,i)$:
\begin{enumerate}
\item\label{proof_coro5.2_1} $\beta_1 = e_{(j,i)}$ for a flag $i$ going out of the central vertex, or $\beta_1 = \beta - e_{(j,i)}$ for a flag $i$ going into a central vertex;
\item\label{proof_coro5.2_2} $\beta_1 \neq \beta$, $\beta_1 \circ (\beta - \beta_1) = 1$, and $\beta_1$ is weakly increasing with jumps of at most one along each of the $m$ flags.
\end{enumerate}
Denote the set of such $\beta_1$ by $\mathcal{D}$. We show in the next lemma that each $\beta_1 \in \mathcal{D}$ defines a facet of $\cone$, which is called a \emph{regular facet} if $\beta_1$ is in the form described in~\eqref{proof_coro5.2_2}, while a facet defined by some $\beta_1$ as described in~\eqref{proof_coro5.2_1} is called \emph{trivial}. The interpretation of the inequalities arising from the $\beta_1 \in \mathcal{D}$ is given in Remark~\ref{facets-interpretation}.
\begin{lemma}
\label{facets-2}
For the sun quiver $Q$, the regular facets of $C(Q,\beta)$ are of the form
\[
\mathbb{H}(\beta_1) \cap C(Q,\beta),
\]
where $\beta_1$ is weakly increasing with jumps of at most one along the flags, $\beta_1 \neq \beta$, and $\beta_1 \circ (\beta - \beta_1) = 1$.
\end{lemma}
\begin{proof}
The proof is the same as the one given in~\cite[Lemma 5.2]{Chi08}, which we include here for completeness. By Theorem 5.1 in~\cite{DW11}, a facet $\mathcal{F}$ is of the form
\[
\mathbb{H}(\beta_1) \cap C(Q,\beta),
\]
where $\beta_1, \beta_2$ are Schur roots, $\beta_1 \circ \beta_2 = 1$, and $\beta = c_1\beta_1 + c_2\beta_2$ for some $c_1, c_2 \geq 1$.
Suppose that $\beta_1$ is not of the form as in~\eqref{proof_coro5.2_1}. We'll show that $\beta_1$ is weakly increasing with jumps of at most one along the flags. Denote $c_1\beta_1 = \beta_1'$ and $c_2\beta_2 = \beta_2'$. Because it is clear that $s_1 \beta_1 \circ s_2 \beta_2 \geq \beta_1 \circ \beta_2$ for all $s_1,s_2 \geq 1$, $\beta_1' \circ \beta_2' \neq 0$. By Theorem~\ref{spanning}, it follows that any representation of dimension vector $\beta$ has a subrepresentation of dimension vector $\beta_1'$. Choose a $\beta$-dimensional representation which is injective along the flags going into a central vertex and surjective along the flags going out of the central vertex. Then $\beta_1'$ is weakly increasing along the flags going in and has jumps of at most one (from the end of the flag towards the center vertex) along the flags going out, or else the maps couldn't be surjective.
We'll show that $\beta_1'$ is weakly increasing along each flag $\mathcal{F}(i)$ going out of a central vertex. Suppose to the contrary that $\beta_1'(l+1) - \beta_1'(l) < 0$ for some $l \in \{1, \ldots, n-1\}$. Then $\beta_1' - e_l \hookrightarrow \beta'_1$. Moreover, $\beta_1' \circ \beta_2' \neq 0$ is equivalent to $\beta_1'$ being $-\langle \cdot, \beta_2' \rangle-$semi-stable by reciprocity (Theorem~\ref{reciprocity}). Thus, $\langle \beta_1' - e_l, \beta_2' \rangle \geq 0$, so $\beta'_2(l) \leq \beta_2'(l-1)$, implying $\beta_1'(l) \geq 1 + \beta_1'(l-1)$. As we previously showed that $\beta_1'$ has jumps of at most one along such a flag, we must have $\beta_1'(l) = 1 + \beta_1'(l-1)$. Thus, $c_1 = 1$ and $e_l \hookrightarrow \beta_1'$. We then have that $\beta_1' = \beta_1$ is a Schur root by assumption, hence is $\sigma_{\beta_1'}$-semistable by Theorem~\ref{Schofield-Schur}, and $e_l, \, \beta_1' - e_l \hookrightarrow \beta_1'$, with $\beta_1' \neq e_l$. Therefore, by the same theorem, $\sigma_{\beta'_1}(e_l)< 0$ and $\sigma_{\beta'_1}(\beta_1'-e_l)< 0,$ which is a contradiction. Thus, $\beta_1'$ must be weakly increasing along the flags going out of a central vertex. By a similar argument, $\beta_1'$ will have jumps of at most one along each flag going in.
Finally, we'll show that $c_1=c_2=1$. Because $\beta_1' = c_1\beta_1$ has jumps of at most one along each flag, we have $0 \leq c_1(\beta_1(l+1,i) - \beta_1(l,i)) \leq 1$ for all $l \in \{1, \ldots, n-1\}$ and $i \in \{1, \ldots, m\}.$ If there are no $l,i$ such that $\beta_1(l+1,i) - \beta_1(l,i) \neq 0$, then $c_1 = 1$, while otherwise there must exist an $i$ such that $\beta_1'(l,i) =1,$ so $c_1=1$. Similarly, $c_2=1$.
Thus, $\beta = \beta_1 + \beta_2$ with $\beta_1$ weakly increasing of jumps of at most one along the flags.
\end{proof}
\begin{lemma}
\label{inequalities}
Let $\sigma \in \HH(\beta)$ for the sun quiver. Then $\sigma \in \cone$ if and only if the following are true:
\begin{enumerate}%[\normalfont(1)]
\item\label{lemma5.4_1} $(-1)^i \sigma(e_{(j,i)}) \geq 0$ for all $1 \leq j \leq n-1, \, 1 \leq i \leq m$;
\item\label{lemma5.4_2} $\sigma(\beta_1) \leq 0$ for every $\beta_1 \neq \beta$ weakly increasing with jumps of at most one along the flags and $\beta_1 \circ (\beta - \beta_1) = 1$.
\end{enumerate}
\end{lemma}
\begin{proof}
The description of the regular facets in Lemma~\ref{facets-2} proves one direction, while if $\sigma \in \cone$, then $\sigma(\beta_1) \leq 0$ for every $\beta_1 \in \mathcal{D}$ by Theorem~\ref{spanning}, which is equivalent to~\eqref{lemma5.4_1} and~\eqref{lemma5.4_2}.
\end{proof}
\begin{rema}
\label{facets-interpretation}
Let $\sigma_1$ be the weight we defined for the sun quiver in equation~\eqref{weight-sigma_1}. In particular,
\[
\sigma_1(e_{(j,i)}) = (-1)^i(\lambda(i)_j - \lambda(i)_{j+1}), \quad \, \, 1 \leq i \leq m, \, 1 \leq j \leq n-1.
\]
The inequalities arising from a trivial facet of $C(Q,\beta)$, as described in~\eqref{lemma5.4_1} in the preceding lemma, called the \emph{chamber inequalities}, simply state that the sequences $\lambda(i)$ are weakly decreasing sequences of real numbers. Because we will always assume this, we exclude these $\beta_1$ from our considerations. The inequalities arising from~\eqref{lemma5.4_2} in the lemma are called the \emph{regular inequalities}, and the corresponding facet is regular.
\end{rema}
%\vspace{.2in}
\section{Horn-type inequalities}\label{section-Horn}
In this section let $\beta_1$ be a dimension vector which is weakly increasing with jumps of at most one along each of the flags towards the central vertices. Define the following jump sets:
\[
I_i = \{l \mid \beta_1(l,i) > \beta_1(l-1,i), \, 1 \leq l \leq n\}
\]
with the convention $\beta_1(0,i) =0$ for all $i$. Because $\beta_1$ defines a tuple $I=(I_1, \ldots, I_m)$, we'll commonly denote $\beta_1$ by $\beta_I$. Note that $|I_i| = \beta_I(n,i)$ for each $i$.
Conversely, each tuple $I = (I_1, \ldots, I_m)$ of subsets of $\{1, \ldots, n\}$ defines a dimension vector $\beta_I$ because if
\[
I_i = \{z_1(i) < \cdots < z_r(i)\},
\]
then $\beta_I(j,i) = j-1$ for all $z_{k-1}(i) \leq j < z_k(i)$ for all $1 \leq k \leq r+1$, with the convention that $z_0(i) = 0$ and $z_{r+1}(i) = n+1$ for all $i$. This means that going towards the center vertex on the $i^{th}$ flag, the dimension at a vertex is 0 until the vertex $z_1(i)$, at which it becomes 1 and continues to be 1 until the vertex $z_2(i)$, at which point it becomes $2$, and so on.
\begin{defi}
For the dimension vector $\beta$ associated to the sun quiver, define $T(n,m)$ to be the set of all tuples $I=(I_1, \ldots, I_m)$ such that $\beta_I \neq \beta$ (equivalently, $|I_i| 0, $ is the bit length of the specifications: $\sum_{i=1}^k\log_2 \lambda_i$.
\begin{theorem}
Deciding whether $c^{\nu}_{\lambda,\mu}$ is positive can be computed in strongly polynomial time in the sense of~\cite{GLS93}. This means that the number of arithmetic steps is polynomial in the number of positive parts of $\nu$ \textup{(}say $n$\textup{)}, does not depend on the bit lengths of $\lambda_i, \mu_j, \nu_k$, and the bit length of every intermediate operand that arises in the algorithm is polynomial in the total bit length of $\lambda, \mu, \nu$.
\end{theorem}
In fact, by attaching zeros to the partitions, one can subsume the dependence on $n$ into the bit lengths of $\lambda,\mu,$ and $\nu$. This is especially amazing as the the dimension of the Weyl module $S^\nu(V)$ is exponential in $n$ and the bit lengths of the $\nu_k$'s, yet deciding if an exponential dimensional object $S^\nu(V)$ arises in the decomposition of another exponential dimensional object $S^\lambda(V) \otimes S^\mu(V)$ can be decided in time that is polynomial in only $n$ and the bit lengths of the labels $\lambda,\mu,$ and $\nu$.
Because of results such as these along with the ubiquity of the plethysm problem and related problems in representation theory, GCT allows one to compare the complexity of several problems. The proof of deciding the positivity of a Littlewood--Richardson coefficient relies on two main points: a polyhedral interpretation of these numbers and the saturation theorem. While we define a polytope for the generalized Littlewood--Richardson coefficients to prove a similar result, it would be nice to have a purely combinatorial algorithm, such as those of max-flow or weighted matching problems in combinatorial optimization. Much work has been made towards this for single Littlewood--Richardson coefficients (see~\cite{BI09},~\cite{BI13}, and~\cite{Ike16}).
\subsection{Polytopal description}
In order to determine the complexity of the positivity of multiplicity (\ref{one}), we will define a polytope by determining a system of homogeneous linear inequalities whose number of integer-valued solutions is precisely the multiplicity. The idea is to use the Littlewood--Richardson hives defined by Knutson and Tao in~\cite{KT99}.
To define the polytope associated with multiplicity (\ref{one}), subdivide a regular $m$-gon into $m$ triangles with $n+1$ vertices along each exterior edge and a common vertex at the center. Subdivide each of these triangles into $n^2$ triangles of the same size, so the hexagon is divided into $mn^2$ total triangles. We label the edges in the $r^{th}$ triangular array in the following way: the first subscript $i$ refers to the row from bottom to top while the second subscript $j$ refers to the diagonal from left to right, and $0 \leq i,j \leq n-1$. The edges along increasing diagonals are labeled $e_{ij},$ the edges along decreasing diagonals are labeled $f_{ij}$, and the horizontal edges are $g_{ij}$. The superscript $r$ refers to which triangular array is used, though this is often neglected. For instance, when $n=3$ the $r^{th}$ triangular array is labeled
\[
\begin{tikzpicture}
\draw (0,0) -- ++(0:6) -- ++(120:6) -- cycle;
\draw (0,0) -- ++(0:2) -- ++(120:2) -- cycle;
\draw (2,0) -- ++(0:2) -- ++(120:2) -- cycle;
\draw (4,0) -- ++(0:2) -- ++(120:2) -- cycle;
\draw (2,0) -- ++(60:2) -- ++(180:2) -- cycle;
\draw (4,0) -- ++(60:2) -- ++(180:2) -- cycle;
\draw (3,1.7) -- ++(60:2) -- ++(180:2) -- cycle;
\coordinate [label={below left: }] ($a_{00}$) at (0,0);
\coordinate [label={below: }] ($a_{10}$) at (2,0);
\coordinate [label={below:}] ($a_{20}$) at (4,0);
\coordinate [label={below:}] ($a_{30}$) at (6,0);
\coordinate [label={left:}] ($a_{01}$) at (1,1.7);
\coordinate [label={below: }] ($a_{11}$) at (3,1.7);
\coordinate [label={right:}] ($a_{21}$) at (5,1.7);
\coordinate [label={left:}] ($a_{02}$) at (2,3.4);
\coordinate [label={right:}] ($a_{12}$) at (4,3.4);
\coordinate [label={above:}] ($a_{03}$) at (3,5.15);
\foreach \i in {$a_{00}$,$a_{01}$,$a_{02}$,$a_{03}$,$a_{10}$,$a_{11}$,$a_{12}$,$a_{20}$,$a_{21}$,$a_{30}$}
\fill (\i) circle (2pt);
\coordinate [label={below: $g_{00}$ }] () at (1,0);
\coordinate [label={below: $g_{01}$}] () at (3,0);
\coordinate [label={below: $g_{02}$}] () at (5,0);
\coordinate [label={below: $g_{10}$}] () at (2,1.7);
\coordinate [label={below: $g_{11}$}] () at (4,1.7);
\coordinate [label={below: $g_{20}$ }] () at (3,3.5);
\coordinate [label={left: $e_{00}$}] () at (.5,.8);
\coordinate [label={left: $f_{00}$}] () at (1.6,.8);
\coordinate [label={left: $e_{01}$}] () at (2.5,.8);
\coordinate [label={left: $f_{01}$}] () at (3.6,.8);
\coordinate [label={right: $e_{02}$}] () at (4.5,.8);
\coordinate [label={right: $f_{02}$}] () at (5.7,.8);
\coordinate [label={left: $e_{10}$}] () at (1.5,2.6);
\coordinate [label={left: $f_{10}$}] () at (2.6,2.6);
\coordinate [label={right: $e_{11}$}] () at (3.5,2.6);
\coordinate [label={right: $f_{11}$}] () at (4.6,2.6);
\coordinate [label={left: $e_{20}$}] () at (2.5,4.4);
\coordinate [label={right: $f_{20}$}] () at (3.5,4.4);
\end{tikzpicture}
\]
Let $E$ be the set of hive edges and $\RR^E$ the labelings of these edges by real numbers. There are three ways that two adjacent triangles inside a single triangular array can form a rhombus:
\begin{center}
\begin{tikzpicture}
\coordinate [label={above: $g_{i+1j}$}] () at (-2,.5);
\coordinate [label={below: $g_{ij}$}] () at (-3,-.5);
\coordinate [label={left: $e_{ij}$}] () at (-3.5,0);
\coordinate [label={right: $e_{i+1j}$}] () at (-1.5,-.2);
\coordinate [label={below left:}] (a) at (-4,-.5);
\coordinate [label={above left:}] (b) at (-3,.5);
\coordinate [label={below right:}] (c) at (-2,-.5);
\coordinate [label={above:}] (d) at (-1,.5);
\draw (a)--(b)--(d)--(c)--cycle;
\draw (b)--(c);
\foreach \i in {a,b,c,d}
\fill (\i) circle (2pt);
\coordinate [label={left: $e_{i+1j}$}] () at (1.5,.5);
\coordinate [label={right: $f_{i+1j}$}] () at (2.5,.5);
\coordinate [label={left: $f_{ij}$}] () at (1.5,-.6);
\coordinate [label={right: $e_{ij+1}$}] () at (2.5,-.6);
\coordinate [label={above:}] (a) at (2,1);
\coordinate [label={left:}] (b) at (1,0);
\coordinate [label={right:}] (c) at (3,0);
\coordinate [label={below:}] (d) at (2,-1);
\draw (a)--(b)--(d)--(c)--cycle;
\draw (b)--(c);
\foreach \i in {a,b,c,d}
\fill (\i) circle (2pt);
\coordinate [label={left: $f_{ij}$}] () at (5.3,-.1);
\coordinate [label={above: $g_{i+1j}$}] () at (6,.5);
\coordinate [label={below: $g_{ij+1}$}] () at (7,-.5);
\coordinate [label={right: $f_{ij+1}$}] () at (7.5,0.2);
\coordinate [label={above:}] (a) at (5,.5);
\coordinate [label={above right:}] (b) at (7,.5);
\coordinate [label={below: }] (c) at (6,-.5);
\coordinate [label={below right:}] (d) at (8,-.5);
\draw (a)--(b)--(d)--(c)--cycle;
\draw (b)--(c);
\foreach \i in {a,b,c,d}
\fill (\i) circle (2pt);
\end{tikzpicture}
\end{center}
We say these rhombi satisfy the \bi{rhombus inequalities} if for each triangle and rhombus appearing, we have
\begin{gather}
\label{rhombus-edge-inequalities}
e_{ij} \Mk \geq \Mk e_{ij+1}, \;\; g_{ij} \Mk \geq \Mk g_{i+1 j}; \quad \
f_{i+1 j} \Mk \geq\Mk f_{ij}, \;\; e_{i j+1} \Mk \geq \Mk e_{i+1 j}; \quad \
f_{ij} \Mk \geq \Mk f_{i j+1}, \;\; g_{i+1 j} \Mk \geq \Mk g_{i j+1};
%\end{equation}
%\[
\\
\nonumber e_{ij} + f_{ij} = g_{ij}, \qquad \quad e_{i \, j+1} + f_{ij} = g_{i+1 \,j}.
\end{gather}
Define an \bi{$(m,n)$-LR sun hive} to be a regular $m$-gon subdivided into $m$ triangular arrays with $n+1$ vertices along each edge that satisfies the rhombus inequalities and the border conditions
\begin{equation}
\label{boundary-edge-conditions}
\sum_{i=0}^{n-1} e^r_{i0} + \sum_{i=0}^{n-1} f^r_{i n-i} = \sum_{j=0}^{n-1} g_{0j}
\end{equation}
for each $1 \leq r \leq m$. It is \bi{integral} if the labeling lies in $\Z^E$. These inequalities define a convex polyhedral cone, denoted $C \subseteq \RR^E$. An \bi{LR hive} is a single triangular array that satisfies the rhombus inequalities and border conditions for that array, so an $(m,n)$-LR sun hive consists of $m$ LR hives with $n$ edges along each side of the boundary of a regular $m$-gon and with the respective conditions and appropriately shared sides. Let $B$ be the set of border edges $g^k_{0j}$ for $1\leq r \leq m, \; 0 \leq j \leq n-1$, and $\rho: \RR^E \to \RR^B$ the restriction map of an LR sun hive to its border. For each $b \in \RR^B$, the fiber $\rho^{-1}(b) \cap C$ is a compact polytope, called the \bi{$m$-sun hive polytope} over $b$.
We recall the main result of~\cite{KT99}. For three $n$-tuples
\[
\lambda = (\lambda_1,\ldots, \lambda_n), \qquad
\mu = (\mu_1,\ldots, \mu_n), \qquad
\nu = (\nu_1, \ldots, \nu_n)
\]
that satisfy the boundary condition $|\nu| = |\lambda| + |\mu|$, the triangular array with border determined by $\lambda, \mu, \nu$ is the one with specified border edges
\[
\begin{tikzpicture}
\coordinate (l0) at (10,0);
\coordinate (n1) at (12,0);
\coordinate (n2) at (14,0);
\coordinate (n3) at (16,0);
\coordinate (n4) at (18,0);
\coordinate (l1) at (11,1.7);
\coordinate (ln1) at (13,1.7);
\coordinate (ln2) at (15,1.7);
\coordinate (l2) at (12,3.4);
\coordinate (ln3) at (14,3.4);
\coordinate (l3) at (13,5.1);
\coordinate (l4) at (14,6.8);
\coordinate (m1) at (15,5.1);
\coordinate (m2) at (16,3.4);
\coordinate (m3) at (17,1.7);
\draw (l0)--(l4)--(n4)--cycle;
\draw (l3)--(m1)--(ln3)--(m2)--(ln2)--(m3)--(n3)--cycle;
\draw (l3)--(ln3)--(l2)--(ln1)--(n1)--(l1)--cycle;
\draw (ln3)--(ln2)--(ln1)--cycle;
\draw (ln1)--(ln2)--(n2)--cycle;
\draw (l1)--(ln1)--(n1)--cycle;
\foreach \i in {l0,l1,l2,l3,l4,n1,n2,n3,n4,m1,m2,m3,ln1,ln2,ln3}
\fill (\i) circle (2pt);
\tkzLabelSegment[left=2pt](l0,l1){$\lambda_1$}
\tkzLabelSegment[left=2pt](l1,l2){$\lambda_2$}
\tkzLabelSegment[left=2pt](l2,l3){$\ldots$}
\tkzLabelSegment[left=2pt](l3,l4){$\lambda_n$}
\tkzLabelSegment[right=2pt](l4,m1){$\mu_1$}
\tkzLabelSegment[right=2pt](m1,m2){$\mu_2$}
\tkzLabelSegment[right=2pt](m2,m3){$\ldots$}
\tkzLabelSegment[right=2pt](m3,n4){$\mu_n$}
\tkzLabelSegment[below=2pt](l0,n1){$\nu_1$}
\tkzLabelSegment[below=2pt](n1,n2){$\nu_2$}
\tkzLabelSegment[below=2pt](n2,n3){$\ldots$}
\tkzLabelSegment[below=2pt](n3,n4){$\nu_n$}
\end{tikzpicture}
\]
\begin{theorem}[\cite{KT99}, Theorem 4]
\label{LR-hives}
The Littlewood--Richardson coefficient $c^\nu_{\lambda, \, \mu}$ is the number of integer LR hives with boundary labels determined by $\lambda, \mu$, and $\nu$.
\end{theorem}
Because we are only interested in integer LR hives it suffices to restrict to when $\lambda,\mu,\nu$ are partitions. Further, if each partition has at most $n$ parts, then the LR hives are LR $n$-hives. Though the border conditions are obvious from the necessary condition that $|\nu| = |\lambda| + |\mu|$ for $c^\nu_{\lambda,\mu}$ to be nonzero, the rhombus inequalities seem mysterious at first. Their inspiration comes from Gelfand--Tsetlin patterns and Cauchy's Interlacing Theorem for the eigenvalues of Hermitian matrices. The first two pairs of inequalities ensure that the tuples are weakly decreasing while the third pair gives a way of associating a contratableau satisfying the Littlewood--Richardson rule; for more on this, see~\cite{Buc00}.
Because one LR hive is used to calculate one Littlewood--Richardson coefficient, it stands to reason that ``gluing'' multiple LR hives together appropriately should be used to calculate our generalized Littlewood--Richardson coefficients. Before stating and proving this we first make precise how we intend to ``glue'' the LR hives. Given one LR hive we combine it with another LR hive by requiring the two to share a side other than the base. This results in the second LR hive being flipped. Of course, we need to verify the values assigned to the shared edges coincide and make precise the edge labelings along with the rhombus inequalities for the flipped hive. For the flipped hive the edges on a descending diagonal are now labeled by the $e$'s while the ascending diagonal edges are labeled by the $f$'s.
Under this notation,
\[
e^{k+1}_{j0} = f^{k}_{n-1-j \, j}.
\]
Flipping the triangular arrays causes each type of rhombus to be flipped, but by also switching the labels for the $e$'s and $f'$s the same rhombus inequalities in (\ref{rhombus-edge-inequalities}) hold. For these flipped arrays we will want to specify when $n$-tuples $\lambda, \mu, \nu$ such that $|\nu| = |\lambda| + |\mu|$ determine the border and align along shared edges, but we will wait to do this depending on which side of the flipped hive we want to have labeled $\nu$.
\begin{rema}
When defining the $(m,n)$-LR sun hive the rhombus inequalities did not include those two types arising from rhombi of adjacent triangles from different hives. Because one hive is flipped, there is no natural way of determining which direction the inequality should be and the direction may differ in different examples. Interestingly, though, the direction of the inequalities arising from adjacent hives is the same within each individual example examined.
\end{rema}
With this notation we may now prove the polytopal description of the generalized Littlewood--Richardson coefficient (\ref{one}).
\begin{theorem}
\label{sun hive}
For partitions $\lambda(1), \ldots, \lambda(2k)$, $k \geq 2$, of no more than $n$ parts, the generalized Littlewood--Richardson coefficient
\[
\sum c^{\lambda(1)}_{\alpha(1),\alpha(2)} c^{\lambda(2)}_{\alpha(2),\alpha(3)} \cdots c^{\lambda(2k-1)}_{\alpha(2k-1),\alpha(2k)} c^{\lambda(2k)}_{\alpha(2k),\alpha(1)}
\]
is equal to the number of integer $(2k,n)$-LR sun hives with external boundary labels determined by the $\lambda(i)$ in cyclic orientation (so that the edge labeled $\lambda(r)$ is between the edges labeled $\lambda(r+1)$ and $\lambda(r-1)$). For instance, the boundary labels of a $(6,n)$-LR sun hive are
\[
\begin{tikzpicture}
\draw (-2,2) -- ++(0:2) -- ++(300:2) -- ++(240:2) -- ++(180:2) -- ++(120:2) --++(60:2) --++(0:2) -- cycle;
\coordinate [label={above:$\lambda(2)$}] () at (-.9,2);
\coordinate [label={right:$\lambda(1)$}] () at (.6,1.3);
\coordinate [label={right: $\lambda(6)$}] () at (.5,-.8);
\coordinate [label={below:$\lambda(5)$}] () at (-.9,-1.5);
\coordinate [label={left: $\lambda(4)$}] () at (-2.4,-.8);
\coordinate [label={left:$\lambda(3)$}] () at (-2.4,1.3);
\end{tikzpicture}
\]
\end{theorem}
\begin{proof}
By Theorem~\ref{LR-hives} the Littlewood--Richardson coefficient $c^{\lambda(r)}_{\alpha(r),\alpha(r+1)}$ is equal to the number of integer LR $n$-hives with $\lambda(r)$ as the base which satisfy the boundary conditions and rhombus inequalities, where $\alpha(r), \alpha(r+1)$ are some tuples of no more than $n$ parts forming the other two sides of the $r^{th}$ triangular array. Necessarily the tuple $\alpha(r)$ is also a boundary of the $(r-1)^{th}$ triangular array while $\alpha(r+1)$ is a boundary of the $(r+1)^{th}$. We use the previously defined notation for each hive and adjacent (flipped) hive, so we only need to specify the border labels. If the base labeled $\lambda(r)$ has edges labeled $\lambda(r)_1, \ldots, \lambda(r)_n$ from \emph{left to right}, then the adjacent base labeled $\lambda(r+1)$ has edges labeled $\lambda(r+1)_1, \ldots, \lambda(r+1)_n$ from \emph{right to left}. In this way, edges labeled by $\alpha(r)$ and $\alpha(r+1)$ in the $r^{th}$ LR hive are $\alpha(r)_1, \ldots, \alpha(r)_n, {\alpha(r+1)_1}, \ldots, \alpha(r+1)_n$ clockwise while the edges in the adjacent hive are labeled $\alpha(r+2)_1,\ldots, \alpha(r+2)_n, \alpha(r+1)_1,\ldots, \alpha(r+1)_n$ counterclockwise. The multiplicity
\[
\sum c^{\lambda(1)}_{\alpha(1),\alpha(2)} c^{\lambda(2)}_{\alpha(2),\alpha(3)} \cdots c^{\lambda(2k-1)}_{\alpha(2k-1),\alpha(2k)} c^{\lambda(2k)}_{\alpha(2k),\alpha(1)}
\]
is then equal to the number of integer $(2k,n)$-LR sun hives with these choices of $\alpha(1),\ldots, \alpha(2k)$. The total number of integer $(2k,n)$-LR sun hives with the boundaries $\lambda(1),\ldots, \lambda(2k)$ is then the sum over all possible integer tuples $\alpha(1), \ldots, \alpha(2k)$ with at most $n$ parts.
\end{proof}
\begin{rema}
There is a characterization of LR hives with vertex labels rather than edge labels. Though the two labelings may be used interchangeably for all results concerning a single Littlewood--Richardson coefficient, the vertex labeling fails in the case of the generalized coefficients because the vertices along a shared boundary would not necessarily agree. For instance, the vertex at the center of the regular $n$-gon could only be zero while this would force the external boundary labels to not be the $\lambda(i)$.
\end{rema}
\begin{rema}
In the previous theorem, it is necessary that the number of partitions be at least four and even. We saw that adjacent LR hives must ``flip'' in order to line up the boundary edges and in our description the edges on the side determined by $\lambda(i)$ are labeled by $\lambda(i)_1, \ldots, \lambda(i)_n$ from left to right for odd $i$ and in reverse order for even $i$. If the number of partitions, $m$, were odd, then the first and $m+1$ hives are the same, yet these have different parities, so we get two different labelings. The number of hives must then be even and it is easily checked that $m=2$ fails.
\end{rema}
As we've seen, the rhombus inequalities (\ref{rhombus-edge-inequalities}) and boundary conditions (\ref{boundary-edge-conditions}) determine a polytope whose number of lattice points corresponds to the multiplicity (\ref{one}) when the external boundaries are determined by the $\lambda(r)$. For each $1 \leq r \leq 2k$, these inequalities may be solved into a linear program $A_r \mathbf{x_r} \leq \mathbf{b_r}$, where $A_r$ is a matrix with entries $0,1,-1$, $\mathbf{x_r}$ is the vector of interior edges $e^r_{ij},\, f^r_{ij}, \, g^r_{ij} \; 0 \leq i \leq n-1, \, 0 \leq j \leq n-1$,
and the entries of $\mathbf{b_r}$ are homogeneous, linear forms in the entries of $\lambda(r)$ (which are integral when $\lambda(r)$ is a partition). Because this can be done for each $r$, we can express all of these as a single linear program $A \mathbf{x} \leq \mathbf{b}$, where $A$ is the block sum of the matrices $A_r$ and similarly for $\mathbf{x}$ and $\mathbf{b}$. Again, $\mathbf{b}$ will be homogeneous, which is necessary for the proof of the complexity of the positivity of the generalized Littlewood--Richardson coefficient. In this way, the multiplicity is equal to the number of integer-valued vector solutions $\mathbf{x}$ to this inequality. This proves the following.
\begin{lemma}
\label{linear-program}
For partitions $\lambda(1), \ldots, \lambda(2k)$, $k \geq 2$, there exists a linear program $A\mathbf{x} \leq \mathbf{b}$, where the matrix $A$ has entries $0,1,-1,$ $\mathbf{b}$ is a vector of homogeneous, integral, linear forms in terms of the parts of $\lambda(1), \ldots, \lambda(2k)$, and the multiplicity
\[
\sum c^{\lambda(1)}_{\alpha(1),\alpha(2)} c^{\lambda(2)}_{\alpha(2),\alpha(3)} \cdots c^{\lambda(2k-1)}_{\alpha(2k-1),\alpha(2k)} c^{\lambda(2k)}_{\alpha(2k),\alpha(1)}
\]
is equal to the number of solution vectors $\mathbf{x}$ with integer entries.
\end{lemma}
With this, we can prove the complexity of the positivity of this multiplicity.
\begin{proof}[Proof of Theorem~\ref{sun-complexity}]
First, we claim that the $m$-sun hive polytope, whose number of lattice points equals
\[
f(\lambda(1),\ldots, \lambda(2k)) = \sum c^{\lambda(1)}_{\alpha(1),\alpha(2)} c^{\lambda(2)}_{\alpha(2),\alpha(3)} \cdots c^{\lambda(2k-1)}_{\alpha(2k-1),\alpha(2k)} c^{\lambda(2k)}_{\alpha(2k),\alpha(1)}
\]
contains an (integer) $(2k,n)-$LR sun hive if and only if it is nonempty, which is equivalent to the multiplicity being nonzero. Note that because the polytope is defined by a linear system $A \mathbf{x} \leq \mathbf{b}$ where $\mathbf{b}$ is homogeneous (Lemma~\ref{linear-program}), for any integer $N$, $f(N\lambda(1), \ldots, N \lambda(2k))$ is the number of integer $(2k,n)$-LR sun hives in the polytope with scaled external boundaries.
One direction of the claim is trivial, so suppose the polytope is nonempty. In particular, the polytope has a vertex. One characterization of a vertex of a polytope (see, for instance,~\cite{Sch03})
defined by such a system of inequalities $A \mathbf{x} \leq \mathbf{b}$ is a point $\mathbf{v}$ of the polytope such that $A\mathbf{v} = \mathbf{b}$. Because $A$ is of full rank (because the defined polytope is nonempty) and the entries of $A$ and $\mathbf{b}$ are all integers, Cramer's rule implies that all the vertices of the polytope have rational coefficients. There is then an integer $N$ for which the scaled polytope contains a $(2k,n)$-LR sun hive. The saturation theorem~\ref{saturation-sun} ensures that $f(\lambda(1), \ldots, \lambda(m))$ is positive, so the original polytope contains a $(2k,n)$-LR sun hive.
Determining whether the polytope is nonempty or not can be determined in polynomial time using linear programming, such as the ellipsoid or interior point algorithm. Furthermore, because the linear program $A \mathbf{x} \leq \mathbf{b}$ is combinatorial, positivity can be determined in strongly polynomial time by using the algorithm in~\cite{Tar86}.
\end{proof}
\section{Other generalized Littlewood--Richardson coefficients }
\label{section-others}
\hypertarget{section-others}{}
The same techniques used in this paper can be used to prove similar results for two other generalized Littlewood--Richardson coefficients, and as such we state the results for these multiplicities without proof. The details for the calculations and proofs may be found in the author's PhD thesis.
\subsection{Context and motivation}
The two other multiplicities are
\begin{equation}\label{two}
f_1(\lambda(1),\ldots, \lambda(m)) \coloneqq
\sum c^{\alpha(1)}_{\lambda(1),\lambda(2)} c^{\lambda(3)}_{\alpha(1),\alpha(2)}\cdots c^{\lambda(m-2)}_{\alpha(m-4),\alpha(m-3)} c^{\alpha(m-3)}_{\lambda(m-1), \lambda(m)}
\end{equation}
\goodbreak
\noindent
for $m\geq 4$, and
\begin{equation}\label{three}
f_2(\lambda(1),\ldots, \lambda(m))\coloneqq
\sum c^{\lambda(2)}_{\lambda(1), \alpha(1)} c^{\lambda(3)}_{\alpha(1), \alpha(2)} \cdots c^{\lambda(m-2)}_{\alpha(m-4), \alpha(m-3)} c^{\lambda(m-1)}_{\alpha(m-3), \lambda(m)},
\end{equation}
for $m \geq 3$,
where the case $m=3$ is the Littlewood--Richardson coefficient $c^{\lambda(2)}_{\lambda(1),\lambda(3)}$, and each summation ranges over all partitions $\alpha(i)$. The first multiplicity describes the branching rule for the direct sum embedding $\gl(n) \times \gl(n') \subseteq \gl(n+n')$ when $m=6$. This was first proven in~\cite{Kin70}, and is also proven in~\cite{HTW05} (see also~\cite{HJ09} and~\cite{Koi89}). The second multiplicity describes the tensor product multiplicities for extremal weight crystals of type $A_{+\infty}$, using a combinatorial rule found by Kashiwara~\cite{Kas90} similar to the Littlewood--Richardson rule that described the irreducible components of the tensor product of irreducible representations of the quantized universal enveloping algebra of a symmetrizable Kac--Moody algebra $\mathfrak{g}$ as described in~\cite{Kwo09} (see also~\cite{Kwo10}) again when $m=6$. This generalized multiplicity is described in~\cite{Chi08} and~\cite{Chi09}, and is found to have connections with long exact sequences of finite, abelian $p$-groups, parabolic affine Kazhdan--Lusztig polynomials, and decomposition numbers for $q$-Schur algebras.
\subsection{Statement of results}
The quiver representing multiplicity (\ref{two}) is the generalized star quiver used to describe multiplicity (\ref{three}) in~\cite{Chi08}, except that the first two flags are oriented in the same direction and likewise the last two are going the same direction. The dimension vector $\beta$ is defined like before as $\beta(j,i) = j$ and the weight is defined similar to $\sigma_1$ in equation (\ref{weight-sigma_1}). Similar calculations to the ones in Section~\ref{section-saturation} prove the following.
\begin{theorem}[Saturation property]
Let $\lambda(1),\ldots, \lambda(m)$, $m \geq 4$, be weakly decreasing sequences of $n$ integers. For every integer $r \geq 1$,
\[
f_1(r\lambda(1),\ldots, r\lambda(m)) \neq 0 \Longleftrightarrow f_1(\lambda(1),\ldots, \lambda(m)) \neq 0.
\]
\end{theorem}
The saturation for multiplicity (\ref{three}) is Theorem 1.4 of~\cite{Chi08}. In the same paper, Chindris provides the Horn-type inequalities and a generalization of Horn's conjecture for the second multiplicity in Theorem 1.6.
The corresponding inequalities and a generalization of Horn's conjecture for the first multiplicity above are slightly complicated by the fact that they depend on the parity of $m$. We state below only the results for $m$ even and remark that similar results hold true for $m$ odd.
\begin{enonce*}[remark]{Generalized eigenvalue problem for $f_1$}
% \textbf{Generalized eigenvalue problem for $f_1$.}
For which weakly decreasing sequences $\lambda(1),\ldots, \lambda(2k),\, k\geq 2$, of $n$ real numbers do there exist $n \times n$ complex Hermitian matrices $H(1),\ldots, H(2k)$ with eigenvalues $\lambda(1),\ldots, \lambda(2k)$ such that
\[
\dsp H(1) + \sum_{i=1}^{k-1} H(2i) = H(2k) + \sum_{i=1}^{k-1} H(2i+1)
\]
and such that
\[
%\begin{array}{rcl}
\dsp H(1) + H(2), \quad \dsp (-1)^j(H(1)+H(2)) + \sum_{i=3}^j (-1)^{j+i} H(i,) \quad 3 \leq j \leq 2k-2
%\end{array}
\]
have non-negative eigenvalues?
We define the generalized Klyachko's cone for this multiplicity as the rational convex polyhedral cone of $m$-tuples $(\lambda(1),\ldots, \lambda(m))$ of solutions to this generalized eigenvalue problem. We denote this cone as $K_1(n,m) \subseteq \RR^{nm}$.
For subsets $I_i \subseteq \{1,\ldots, n\}, \, 1 \leq i \leq 2k$, define the following tuple of weakly decreasing sequences of integers:
\[
%\begin{multline*}
\unlam_1(I_i) %\\
= \begin{cases}
\lambda'(I_i) & 1 \leq i \leq 2k-3, %\;
\\[-2pt]
&\hspace*{17.5mm}i \text{ odd} \\
\lambda'(I_2) - ((|I_2| - |I_3|)^{n-|I_2|}) & i=2\\
\lambda'(I_i) - ((|I_i| - |I_{i-1}| - |I_{i+1}|)^{n-|I_i|}) & 4 \leq i \leq 2k-2, %\;
\\[-2pt]
&\hspace*{17.5mm}i \text{ even} \\
\lambda'(I_{2k\Mk-\Mk 1}) \Mk-\Mk ((|I_{2k-1}| \Mk-\Mk |I_{2k-1} \backslash \{n\} \Mk-\Mk |I_{2k} \Mk\backslash\Mk \{n\}|)^{n-|I_{2k-1}|}) & i=2k-1 \\
\lambda'(I_{2k} \backslash \{n\}) & i=2k.
\end{cases}
%\end{multline*}
\]
The generalization of Horn's conjecture for multiplicity (\ref{two}) may then be stated as follows (for $m$ even).
\end{enonce*}
\begin{theorem}
Let $\lambda(1),\ldots, \lambda(m),\, m=2k \geq 4$, be weakly decreasing sequences of $n$ real numbers. Then the following conditions are equivalent:
\begin{enumerate}%[\normalfont(1)]
\item $(\lambda(1),\ldots, \lambda(m)) \in K_1(n,m)$;
\item the numbers $\lambda(i)_j$ satisfy
\[
\sum_{i=1}^{k-1} |\lambda(2i+1)| + |\lambda(2k)| =
|\lambda(1)| + \sum_{i=1}^{k-1} |\lambda(2i)|
\]
and
\[
\sum_{i=1}^{k-1} \sum_{j \in I_i} \lambda(2i+1)_j+ \sum_{j \in I_{2k}} \lambda(2k)_j \leq
\sum_{j \in I_1} \lambda(1)_j + \sum_{i=1}^{k-1} \sum_{j \in I_i} \lambda(2i)_j
\]
for every tuple $(I_1, \ldots, I_{m})$ for which $|I_i|