# Assembling Crystals of Type A

Authors: Vladimir I. Danilov; Alexander V. Karzanov; Gleb A. Koshevoy
Journal: Algebra
 (2013)

---

## Abstract

RegularAn-crystals are certain edge-colored directed graphs, which are related to representations of the quantized universal enveloping algebra Uq(𝔰𝔩n+1). For such a crystal K with colors 1,2,…,n, we consider its maximal connected subcrystals with colors 1,…,n-1 and with colors 2,…,n and characterize the interlacing structure for all pairs of these subcrystals. This enables us to give a recursive description of the combinatorial structure of K via subcrystals and develop an efficient procedure of assembling K.


---

## Body

## 1. Introduction

Crystals are certain “exotic” edge-colored graphs. This graph-theoretic abstraction, introduced by Kashiwara [1, 2], has proved its usefulness in the theory of representations of Lie algebras and their quantum analogues. In general, a finite crystal is a finite directed graph K such that the edges are partitioned into n subsets, or color classes, labeled 1,…,n, each connected monochromatic subgraph of K is a simple directed path, and there are certain interrelations between the lengths of such paths, which depend on the n×n Cartan matrix M=(mij) related to a given Lie algebra 𝔤. Of most interest are crystals of representations, or regular crystals. They are associated to elements of a certain basis of the highest weight integrable modules (representations) over the quantized universal enveloping algebra Uq(𝔤).This paper continues our combinatorial study of crystals begun in [3, 4] and considers n-colored regular crystals of type A, where the number n of colors is arbitrary. Recall that type A concerns 𝔤=𝔰𝔩n+1; in this case the Cartan matrix M is viewed as mij=-1 if |i-j|=1, mij=0 if |i-j|>1, and mii=2. We will refer to a regular n-colored crystal of type A as an An-crystal and omit the term n when the number of colors is not specified. Since we are going to deal with finite regular crystals only, the adjectives “finite” and “regular” will usually be omitted. Also we assume that any crystal in question is (weakly) connected; that is, it is not the disjoint union of two nonempty graphs (which does not lead to loss of generality).It is known that any A-crystalK possesses the following properties. (i) K is acyclic (i.e., has no directed cycles) and has exactly one zero-indegree vertex, called the source, and exactly one zero-outdegree vertex, called the sink of K. (ii) For any I⊆{1,…,n}, each (inclusion-wise) maximal connected subgraph of K whose edges have colors from I is a crystal related to the corresponding I×I submatrix of the Cartan matrix for K. Throughout, speaking of a subcrystal of K, we will mean a subgraph of this sort.Two-colored subcrystals are of especial importance, due to the result in [5] that for a crystal (of any type) with exactly one zero-indegree vertex, the regularity of all two-colored subcrystals implies the regularity of the whole crystal. Let K′ be a two-colored subcrystal with colors i,j in an A-crystal K. Then K′ is the Cartesian product of a path with color i and a path with color j (forming an A1×A1-crystal) when |i-j|>1, and an A2-crystal when |i-j|=1. (The A-crystals belong to the group of simply-laced crystals, which are characterized by the property that each two-colored subcrystal is of type A1×A1 or A2; for more details, see [6].)Another important fact is that for anyn-tuple c=(c1,…,cn) of nonnegative integers, there exists exactly one An-crystal K such that each ci is equal to the length of the maximal path with color i beginning at the source (for short combinatorial explanations, see [4, Section 2]. We denote the crystal K determined by c in this way by K(c) and refer to c as the parameter of this crystal.There have been known several ways to define A-crystals; in particular, via Gelfand-Tsetlin pattern model, semistandard Young tableaux, and Littelmann's path model; see [7–10]. In the last decade there appeared additional, more enlightening, descriptions. A short list of “local” defining axioms for A-crystals is pointed out in [6], and an explicit construction for A2-crystals is given in [3]. According to that construction, any A2-crystal can be obtained from an A1×A1-crystal by replacing each monochromatic path of the latter by a graph viewed as a triangle-shaped half of a directed square grid.Whenn>2, the combinatorial structure of An-crystals becomes much more complicated, even for n=3. Attempting to learn more about this structure, we elaborated in [4] a new combinatorial construction, the so-called crossing model (which is a refinement of the Gelfand-Tsetlin pattern model). This powerful tool has helped us to reveal more structural features of an An-crystal K=K(c). In particular, K has the so-called principal lattice, a vertex subset Π with the following nice properties:(P1)
Π contains the source and sink of K, and the vertices v∈Π are bijective to the elements of the integer box ℬ(c):={a∈ℤn:0≤a≤c}; we write v=v˘[a];(P2)
for anya,a′∈ℬ(c) with a≤a′, the interval of K from v˘[a] to v˘[a′] (i.e., the subgraph of K formed by the vertices and edges contained in directed paths from v˘[a] to v˘[a′]) is isomorphic to the An-crystal K(a′-a), and its principal lattice consists of the principal vertices v˘[a′′] of K with a≤a′′≤a′;(P3)
the set𝒦(-n) of (n-1)-colored subcrystals K′ of K having colors 1,…,n-1 is bijective to Π; more precisely, K′∩Π consists of exactly one vertex, called the heart of K′ w.r.t. K, and similarly for the set 𝒦(-1) of subcrystals of K with colors 2,…,n.Note that a sort of “principal lattice” satisfying (P1) and (P2) can be introduced for crystals of types B and C as well, and probably for the other classical types (see [11, Section 8]); for more about B2-crystals, see also [12]). However, (P3) does not remain true in general for those types. Property (P3) is crucial in our study of A-crystals in this paper.Fora∈ℬ(c), let K↑[a] (resp., K↓[a]) denote the subcrystal in 𝒦(-n) (resp., in 𝒦(-1)) that contains the principal vertex v˘[a]; we call it the upper (resp., lower) subcrystal at a. It is shown in [4] that the parameter of this subcrystal is expressed by a linear function of c and a, and that the total amount of upper (lower) subcrystals with a fixed parameter c′ is expressed by a piecewise linear function of c and c′.In this paper, we further essentially use the crossing model, aiming to obtain a refined description of the structure of anAn-crystal K. We study the intersections of subcrystals K↑[a] and K↓[b] for any a,b∈ℬ(c). This intersection may be empty or consist of one or more subcrystals with colors 2,…,n-1, called middle subcrystals of K. Each of these middle subcrystals K~ is therefore a lower subcrystal of K↑[a] and an upper subcrystal of K↓[b]; so K~ has a unique vertex z in the principal lattice Π↑ of the former, and a unique vertex z′ in the principal lattice Π↓ of the latter. Our main structural results—Theorems 7 and 8—give explicit expressions showing how the “loci” a and b in Π, the “deviation” of (the heart of) K~ from z in Π↑, and the “deviation” of K~ from z′ in Π↓ are interrelated.This gives rise to a recursive procedure of assembling of theAn-crystal K(c). More precisely, suppose that the (n-1)-colored crystals K↑[a] and K↓[b] for all a,b∈ℬ(c) are already constructed. Then we can combine these subcrystals to obtain the desired crystal K(c), by properly identifying the corresponding middle subcrystals (if any) for each pair K↑[a],K↓[b]. This recursive method is implemented as an efficient algorithm which, given a parameter c∈ℤ+n, outputs the crystal K(c). The running time of the algorithm and the needed space are bounded by Cn2|K(c)|, where C is a constant and |K(c)| is the size of K(c). (It may be of practical use for small n and c; in general, an An-crystal has “dimension” n(n+1)/2 and its size grows sharply by increasing c.)This paper is organized as follows. Section2 contains basic definitions and backgrounds. Here we recall “local” axioms and the crossing model for A-crystals and review the needed results on the principal lattice Π of an An-crystal and relations between Π and the (n-1)-colored subcrystals from [4]. Section 3 states Theorems 7 and 8 and gives a recursive description of the structure of an An-crystal K and the algorithm of assembling K. These theorems are proved in Section 4. Section 5 illustrates our assembling method for two special cases of A-crystals: for an arbitrary A2-crystal (in which case the method can be compared with the explicit combinatorial construction in [3]) and for the particular A3-crystal K(1,1,1).It should be noted that the obtained structural results on A-crystals can also be applied to give a direct combinatorial proof of the known fact that any regularBn-crystal (Cn-crystal) can be extracted, in a certain way, from a symmetric A2n-1-crystal (resp., A2n-crystal); this is discussed in detail in ([11], Sections 5–8). Here an Ak-crystal with parameter (c1,…,ck) is called symmetric if ci=ck+1-i.


## 2.  Preliminaries

In this section we recall “local” axioms defining A-crystals, explain the construction of crossing model, and review facts about the principal lattice and subcrystals established in [4] that will be needed later.


### 2.1. A-Crystals

Stembridge [6] pointed out a list of “local” graph-theoretic axioms for the regular simply laced crystals. The (regular) A-crystals form a subclass of those and are defined by axioms (A1)–(A5) below; these axioms are given in a slightly different, but equivalent, form compared with [6].LetK=(V(K),E(K)) be a directed graph whose edge set is partitioned into n subsets E1,…,En, denoted as K=(V(K),E1⊔⋯⊔En). We assume K to be (weakly) connected. We say that an edge e∈Ei has colori or is an i-edge.Unless explicitly stated otherwise, by apath we mean a simple finite directed path, that is, a sequence of the form (v0,e1,v1,…,ek,vk), where v0,v1,…,vk are distinct vertices and each ei is an edge from vi-1 to vi (admitting k=0).The first axiom concerns the structure of monochromatic subgraphs ofK.  (A1)
Fori=1,…,n, each connected subgraph of (V(K),Ei) is a path.So each vertex ofK has at most one incoming i-edge and at most one outgoing i-edge, and therefore one can associate to the set Ei a partial invertible operatorFi acting on vertices: (u,v) is an i-edge if and only if Fiacts at u and Fi(u)=v (or u=Fi-1(v), where Fi-1 is the partial operator inverse to Fi). Since K is connected, one can use the operator notation to express any vertex via another one. For example, the expression F1-1F32F2(v) determines the vertex w obtained from a vertex v by traversing 2-edge (v,v′), followed by traversing 3 edges (v′,u) and (u,u′), followed by traversing 1-edge (w,u′) in backward direction. Emphasize that every time we use such an operator expression in what follows, this automatically says that all corresponding edges do exist in K.We refer to a monochromatic path with colori on the edges as an i-path. So each maximal i-path is an A1-subcrystal with color i in K. The maximal i-path passing a given vertex v (possibly consisting of the only vertex v) is denoted by Pi(v), its part from the first vertex to v by Piin(v), and its part from v to the last vertex by Piout(v) (the tail and head parts of P w.r.t. v). The lengths (i.e., the numbers of edges) of Piin(v) and Piout(v) are denoted by ti(v) and hi(v), respectively.Axioms (A2)–(A5) concern interrelations of different colorsi, j. They say that each component of the two-colored graph (V(K),Ei⊔Ej) forms an A2-crystal when colors i, j are neighboring, which means that |i-j|=1, and forms an A1×A1-crystal otherwise.When we traverse an edge of colori, the head and tail part lengths of maximal paths of another color j behave as follows.(A2)
For different colorsi,j and for an edge (u,v) with color i, one holds tj(v)≤tj(u) and hj(v)≥hj(u). The value (hj(u)-tj(u))-(hj(v)-tj(v)) is the constant mij equal to -1 if |i-j|=1, and 0 otherwise. Furthermore, hj is convex on each i-path, in the sense that if (u,v),(v,w) are consecutive i-edges, then hj(u)+hj(w)≥2hj(v).These constantsmij are just the off-diagonal entries of the Cartan n×n matrix M related to the crystal type A and the number n of colors.It follows that for neighboring colorsi, j, each maximal i-path P contains a unique vertex r such that when traversing any edge e of P before r (i.e., e∈Piin(r)), the tail length tj decreases by 1 while the head length hj does not change, and when traversing any edge of P after r, tj does not change while hj increases by 1. This r is called the critical vertex for P, i, j. To each i-edge e=(u,v), we associate labelℓj(e):=hj(v)-hj(u); then ℓj(e)∈{0,1} and tj(v)=tj(u)-1+ℓj(e). We emphasize that the critical vertices on a maximal i-path P w.r.t. its neighboring colors j=i-1 and j=i+1 may be different (and so are the edge labels on P).Two operatorsF=Fiα and F′=Fjβ, where α,β∈{1,-1}, are said to commute at a vertex v if each of F,F′ acts at v (i.e., corresponding i-edge and j-edge incident with v exist) and FF′(v)=F′F(v). The third axiom indicates situations when such operators commute for neighboring i,j.(A3)
Let|i-j|=1. (a) If a vertex u has outgoing i-edge (u,v) and outgoing j-edge (u,v′) and if ℓj(u,v)=0, then ℓi(u,v′)=1 and Fi, Fj commute at v. Symmetrically: (b) if a vertex v has incoming i-edge (u,v) and incoming j-edge (u′,v) and if ℓj(u,v)=1, then ℓi(u′,v)=0 and Fi-1, Fj-1 commute at v. (See the following picture.)(1)One easily shows that if four vertices are connected by twoi-edges e, e′ and two j-edges e~,e~′ (forming a “square”), then ℓj(e)=ℓj(e′)≠ℓi(e~)=ℓi(e~′) (as illustrated in the picture). Another important consequence of (A3) is that for neighboring colors i,j, if v is the critical vertex on a maximal i-path w.r.t. color j, then v is also the critical vertex on the maximal j-path passing v w.r.t. color i; that is, we can speak of common critical vertices for the pair {i,j}.The fourth axiom points out situations when, for neighboringi,j, the operators Fi,Fj and their inverse ones “remotely commute” (forming the “Verma relation of degree 4”).(A4)
Let|i-j|=1. (i) If a vertex u has outgoing edges with color i and color j and if each edge is labeled 1 w.r.t. the other color, then FiFj2Fi(u)=FjFi2Fj(u). Symmetrically, (ii) if v has incoming edges with color i and color j and if both are labeled 0, then Fi-1(Fj-1)2Fi-1(v)=Fj-1(Fi-1)2Fj-1(v). (See the following picture.)(2)Again, one shows that the label w.r.t.i, j of each of the eight involved edges is determined uniquely, just as indicated in the above picture (where the bigger circles indicate critical vertices).The final axiom concerns nonneighboring colors.(A5)
Let|i-j|≥2. Then for any F∈{Fi,Fi-1} and F′∈{Fj,Fj-1}, the operators F,F′ commute at each vertex where both act.This is equivalent to saying that each component of the two-colored subgraph(V(K),Ei⊔Ej) is the Cartesian product of an i-path P and a j-path P′, or that each subcrystal of K with nonneighboring colors i, j is an A1×A1-crystal.One shows that anyAn-crystal K is finite and has exactly one zero-indegree vertex sK and one zero-outdegree vertex tK, called the source and sink of K, respectively. Furthermore, the An-crystals K admit a nice parameterization: the lengths h1(sK),…,hn(sK) of monochromatic paths starting at the source determine K, and for each tuple c=(c1,…,cn) of nonnegative integers, there exists a (unique) An-crystal K such that ci=hi(sK) for i=1,…,n. (See [4, 6].) We call c the parameter of K and denote K by K(c).


### 2.2.  The Crossing Model forAn-Crystals

Following [4], the crossing modelℳn(c) generating the An-crystal K=K(c) with a parameter c=(c1,…,cn)∈ℤ+n consists of three ingredients:(i)
a directed graphGn=G=(V(G),E(G)) depending on n, called the supporting graph of the model;(ii)
a setℱ=ℱ(c) of feasible functions on V(G);(iii)
a setℰ=ℰ(c) of transformations f↦f′ of feasible functions, called moves.To explain the construction of the supporting graphG, we first introduce another directed graph 𝒢=𝒢n that we call the protograph of G. Its node set consists of elements Vi(j) for all i,j∈{1,…,n} such that j≤i. (To avoid a possible mess, we prefer to use the term “node” for vertices in the crossing model, and the term “vertex” for vertices of crystals.) Its edges are all possible pairs of the form (Vi(j),Vi-1(j)) (ascending edges) or (Vi(j),Vi+1(j+1)) (descending edges). We say that the nodes Vi(1),…,Vi(i) form ith level of 𝒢 and order them as indicated (by increasing j). We visualize 𝒢 by drawing it on the plane so that the nodes of the same level lie in a horizontal line, the ascending edges point North-East, and the descending edges point South-East. See the picture where n=4.(3)The supporting graphG is produced by replicating elements of 𝒢 as follows. Each node Vi(j) generates n-i+1 nodes of G, denoted as vik(j) for k=i-j+1,…n-j+1, which are ordered by increasing k (and accordingly follow from left to right in the visualization). We identify Vi(j) with the set of these nodes and call it a multinode of G. Each edge of 𝒢 generates a set of edges of G (a multiedge) connecting elements with equal upper indices. More precisely, (Vi(j),Vi-1(j)) produces n-i+1 ascending edges (vik(j),vi-1k(j)) for k=i-j+1,…,n-j+1, and (Vi(j),Vi+1(j+1)) produces n-i descending edges (vik(j),vi+1k(j+1)) for k=i-j+1,…,n-j.The resultingG is the disjoint union of n directed graphs G1,…,Gn, where each Gk contains all vertices of the form vik(j). Also Gk is isomorphic to the Cartesian product of two paths, with the lengths k-1 and n-k. For example, for n=4, the graph G is viewed as (4)(where the multinodes are surrounded by ovals) and its componentsG1, G2, G3, G4 are viewed as (5)So each nodev=vik(j) of G has at most four incident edges, namely, (vi-1k(j-1),v), (vi+1k(j),v), (v,vi-1k(j)), and (v,vi+1k(j+1)); we refer to them, when exist, as the NW-, SW-, NE-, and SE-edges and denote them by eNW(v),eSW(v),eNE(v), and eSE(v), respectively.By afeasible function in the model (with a given c), we mean a function f:V(G)→ℤ+ satisfying the following three conditions, where for an edge e=(u,v), ∂f(e) denotes the increment f(u)-f(v) of f on e, and e is called tight for f, or f-tight, if ∂f(e)=0:
(6)(i)fismonotoneontheedges,inthesensethat∂f(e)≥0foralle∈E(G);(ii)0≤f(v)≤ckforeachv∈V(Gk),k=1,…,n;(iii)eachmultinodeVi(j)containsanodevwiththefollowingproperty:theedgeeSE(u)istightforeachnodeu∈Vi(j)precedingv,andeSW(u′)istightforeachnodeu′∈Vi(j)succeedingv.Thefirst node v=vik(j) (i.e., with k minimum) satisfying the property in (iii) is called the switch-node of the multinode Vi(j). These nodes play an important role in our transformations of feasible functions in the model.To describe the rule of transformingf∈ℱ(c), we first extend each Gk by adding extra nodes and extra edges (following [4] and aiming to slightly simplify the description). In the extended directed graph G-k, the node set consists of elements vik(j) for all i=0,…,n+1 and j=0,…,n such that j≤i. The edge set of G-k consists of all possible pairs of the form (vik(j),vi-1k(j)) or (vik(j),vi+1k(j+1)). Then all G-k are isomorphic. The disjoint union of these G-k gives the extended supporting graphG-. The creation of G-2 from G2 for n=4 is illustrated in the picture: (7)Each feasible function onV(G) is extended to the extra nodes v=vik(j) as follows: f(v):=ck if there is a path from v to a node of Gk, and f(v):=0 otherwise (one may say that v lies on the left of Gk in the former case and on the right of Gk in the latter case; in the above picture, such nodes v are marked by white and black circles, resp.). ∂f is extended to the extra edges accordingly. In particular, each edge e of G- not incident with a node of G is tight; that is, ∂f(e)=0. For a node v=vik(j) with 1≤j≤i≤n, define the value ε(v)=εf(v) by
(8)ε(v):=∂f(eNW(v))-∂f(eSE(u))=∂f(eSW(v))-∂f(eNE(u)),
where u:=vik(j-1). For a multinode Vi(j), define the numbers
(9)εi(j):=∑‍(ε(v):v∈Vi(j)),(10)εi(p,j):=εi(p)+εi(p+1)+⋯+εi(j)for1≤p≤j,ε~i(j):=max{0,min{εi(p,j):p=1,…,j}}.
We call ε(v), εi(j), and ε~i(j) the slack at a node v, the total slack at a multinode Vi(j), and the reduced slack at Vi(j), respectively. (Note that ε, ε~ are defined in  (8), (9), and (10) in a slightly different way than in [4], which, however, does not affect the choice of active multinodes and switch-nodes below.)Now we are ready to define the transformations off (or the moves from f). At most n transformations ϕ1,…,ϕn are possible. Each ϕi changes f within level i and is applicable when this level contains a multinode Vi(j′) with ε~i(j′)>0. In this case we take the multinode Vi(j) such that
(11)ε~i(j)>0,ε~i(q)=0forq>j,
referring to it as the active multinode for the given f and i. We increase f by 1 at the switch-node in Vi(j), preserving f on the other nodes of G. It is shown [4] that the resulting function ϕi(f) is again feasible.As a result, the model generatesn-colored directed graph 𝒦(c)=(ℱ,ℰ1⊔⋯⊔ℰn), where each color class ℰi is formed by the edges (f,ϕi(f)) for all feasible functions f to which the operator ϕi is applicable. This graph is just an An-crystal.Theorem 1 (see [4, Th. 5.1]).
For eachc∈ℤ+n, the n-colored graph 𝒦(c) is exactly the An-crystal K(c).


### 2.3.  Principal Lattice and(n-1)-Colored Subcrystals of an An-Crystal

Based on the crossing model, [4] reveals some important ingredients and relations for an An-crystal K=K(c). One of them is the so-called principal lattice, which is defined as follows.Leta∈ℤ+n and a≤c. One easily checks that the function on the vertices of the supporting graph G that takes the constant value ak within each subgraph Gk of G, k=1,…,n, is feasible. We denote this function and the vertex of K corresponding to it by f[a] and v˘[a], respectively, and call them principal ones. So the set of principal vertices is bijective to the integer box ℬ(c):={a∈ℤn:0≤a≤c}; this set is called the principal lattice of K and denoted by Π=Π(c). When it is not confusing, the term “principal lattice” may also be applied to ℬ(c).The following properties of the principal lattice will be essentially used later.Proposition 2 (see [4, Statement  (6.4)]).
Leta∈ℬ(c), k∈{1,…,n}, and a′:=a+1k (where 1k is ith unit base vector in ℝn). The principal vertex v˘[a′] is obtained from v˘[a] by applying the operator string
(12)Sn,k:=wn,k,n-k+1⋯wn,k,2wn,k,1,
where for j=1,…,n-k+1, the substring wn,k,j is defined as
(13)wn,k,j:=FjFj+1⋯Fj+k-1.
When acting on Π, any two (applicable) strings Sn,k,Sn,k′ commute. In particular, any principal vertex v˘[a] is expressed via the source sK=v˘[0] as
(14)v˘[a]=Sn,nanSn,n-1an-1⋯Sn,1a1(sK).Proposition 3 (see [4, Prop. 6.1]).
Forc′,c′′∈Z+n with c′≤c′′≤c, let K(c′:c′′) be the subgraph of K(c) formed by the vertices and edges contained in (directed) paths from v˘[c′] to v˘[c′′] (the interval of K(c) from v˘[c′] to v˘[c′′]). Then K(c′:c′′) is isomorphic to the An-crystal K(c′′-c′), and the principal lattice of K′ consists of the principal vertices v˘[a] of K(c) with c′≤a≤c′′.Let𝒦(-n)(c) denote the set of subcrystals with colors 1,…,n-1, and 𝒦(-1) the set of subcrystals with colors 2,…,n in K (recall that a subcrystal is assumed to be connected and maximal for the corresponding subset of colors).Proposition 4 (see [4, Prop. 7.1]).
Each subcrystal in𝒦(-n) (in 𝒦(-1)) contains precisely one principal vertex. This gives a bijection between 𝒦(-n) and Π (resp., between 𝒦(-1) and Π).We refer to the members of𝒦(-n) and 𝒦(-1) as upper and lower ((n-1)-colored) subcrystals of K, respectively. For a∈ℬ(c), the upper subcrystal containing the vertex v˘[a] is denoted by K↑[a]. This subcrystal has its own principal lattice of dimension n-1, which is denoted by Π↑[a]. We say that the coordinate tuple a is the locus of K↑[a] (and of Π↑[a]) in Π. Analogously, for b∈ℬ(c), the lower subcrystal containing v˘[b] is denoted by K↓[b] and its principal lattice by Π↓[b]; we say that b is the locus of K↓[b] (and of Π↓[b]) in Π. It turns out that the parameters of upper and lower subcrystals can be expressed explicitly as follows.Proposition 5 (see [4, Props. 7.2, 7.3]).
Fora∈ℬ(c), the upper subcrystal K↑[a] is isomorphic to the An-1-crystal K(c↑), where c↑ is the tuple (c1↑,…,cn-1↑) defined by
(15)ci↑:=ci-ai+ai+1,i=1,…,n-1.
The principal vertex v˘[a] is contained in the upper lattice Π↑[a] and its coordinate ℏ↑=(ℏ1↑,…,ℏn-1↑) in Π↑[a] satisfies
(16)ℏi↑=ai+1,i=1,…,n-1.
Symmetrically, forb∈ℬ(c), the lower subcrystal K↓[b] is isomorphic to the An-1-crystal K(c↓) with colors 2,…,n, where c↓ is defined by
(17)ci↓:=ci-bi+bi-1,i=2,…,n.
The principal vertex v˘[b] is contained in the lower lattice Π↓[b] and its coordinate ℏ↓=(ℏ2↓,…,ℏn↓) in Π↓[b] satisfies
(18)ℏi↓=bi-1,i=2,…,n.We callv˘[a] the heart of K↑[a] w.r.t. K, and similarly for lower subcrystals.(One more result given in [4, Remark 5] is a piecewise linear formula to compute, for an (n-1)-tuple q, the number of upper subcrystals of K(c) with the parameter equal to q, but we do not need this in what follows.)Remark 6.
As is mentioned in the Introduction, the crossing model is, in fact, a refinement of the Gelfand-Tsetlin pattern (orGT-pattern) model [7]. More precisely, for c∈ℤ+n, form the partition λ=(λ1≥λ2≥⋯≥λn≥λn+1=0) by setting λi:=c[1:n-i+1], where c[p:q] denotes cp+cp+1+⋯+cq. A GT-pattern for λ is a triangular array X=(xij)1≤j≤i≤n of integers satisfying (a) xij≥xi-1,j,xi+1,j+1 and (b) λi≥xn,i≥λi+1, for all possible i,j. It is shown in [4] that the set of feasible functions f in the crossing model ℳn(c) is bijective to the set of GT-patterns X for λ; such a correspondence is given by xi,j:=f^i(j)+c[1:i-j], where f^i(j) denotes the sum of values of f over the multinode Vi(j). However, it is not clear how to visualize, and work with, principal vertices directly in terms of GT-patterns, whereas such vertices are well visualized and fit to handle in the crossing model.


## 2.1. A-Crystals

Stembridge [6] pointed out a list of “local” graph-theoretic axioms for the regular simply laced crystals. The (regular) A-crystals form a subclass of those and are defined by axioms (A1)–(A5) below; these axioms are given in a slightly different, but equivalent, form compared with [6].LetK=(V(K),E(K)) be a directed graph whose edge set is partitioned into n subsets E1,…,En, denoted as K=(V(K),E1⊔⋯⊔En). We assume K to be (weakly) connected. We say that an edge e∈Ei has colori or is an i-edge.Unless explicitly stated otherwise, by apath we mean a simple finite directed path, that is, a sequence of the form (v0,e1,v1,…,ek,vk), where v0,v1,…,vk are distinct vertices and each ei is an edge from vi-1 to vi (admitting k=0).The first axiom concerns the structure of monochromatic subgraphs ofK.  (A1)
Fori=1,…,n, each connected subgraph of (V(K),Ei) is a path.So each vertex ofK has at most one incoming i-edge and at most one outgoing i-edge, and therefore one can associate to the set Ei a partial invertible operatorFi acting on vertices: (u,v) is an i-edge if and only if Fiacts at u and Fi(u)=v (or u=Fi-1(v), where Fi-1 is the partial operator inverse to Fi). Since K is connected, one can use the operator notation to express any vertex via another one. For example, the expression F1-1F32F2(v) determines the vertex w obtained from a vertex v by traversing 2-edge (v,v′), followed by traversing 3 edges (v′,u) and (u,u′), followed by traversing 1-edge (w,u′) in backward direction. Emphasize that every time we use such an operator expression in what follows, this automatically says that all corresponding edges do exist in K.We refer to a monochromatic path with colori on the edges as an i-path. So each maximal i-path is an A1-subcrystal with color i in K. The maximal i-path passing a given vertex v (possibly consisting of the only vertex v) is denoted by Pi(v), its part from the first vertex to v by Piin(v), and its part from v to the last vertex by Piout(v) (the tail and head parts of P w.r.t. v). The lengths (i.e., the numbers of edges) of Piin(v) and Piout(v) are denoted by ti(v) and hi(v), respectively.Axioms (A2)–(A5) concern interrelations of different colorsi, j. They say that each component of the two-colored graph (V(K),Ei⊔Ej) forms an A2-crystal when colors i, j are neighboring, which means that |i-j|=1, and forms an A1×A1-crystal otherwise.When we traverse an edge of colori, the head and tail part lengths of maximal paths of another color j behave as follows.(A2)
For different colorsi,j and for an edge (u,v) with color i, one holds tj(v)≤tj(u) and hj(v)≥hj(u). The value (hj(u)-tj(u))-(hj(v)-tj(v)) is the constant mij equal to -1 if |i-j|=1, and 0 otherwise. Furthermore, hj is convex on each i-path, in the sense that if (u,v),(v,w) are consecutive i-edges, then hj(u)+hj(w)≥2hj(v).These constantsmij are just the off-diagonal entries of the Cartan n×n matrix M related to the crystal type A and the number n of colors.It follows that for neighboring colorsi, j, each maximal i-path P contains a unique vertex r such that when traversing any edge e of P before r (i.e., e∈Piin(r)), the tail length tj decreases by 1 while the head length hj does not change, and when traversing any edge of P after r, tj does not change while hj increases by 1. This r is called the critical vertex for P, i, j. To each i-edge e=(u,v), we associate labelℓj(e):=hj(v)-hj(u); then ℓj(e)∈{0,1} and tj(v)=tj(u)-1+ℓj(e). We emphasize that the critical vertices on a maximal i-path P w.r.t. its neighboring colors j=i-1 and j=i+1 may be different (and so are the edge labels on P).Two operatorsF=Fiα and F′=Fjβ, where α,β∈{1,-1}, are said to commute at a vertex v if each of F,F′ acts at v (i.e., corresponding i-edge and j-edge incident with v exist) and FF′(v)=F′F(v). The third axiom indicates situations when such operators commute for neighboring i,j.(A3)
Let|i-j|=1. (a) If a vertex u has outgoing i-edge (u,v) and outgoing j-edge (u,v′) and if ℓj(u,v)=0, then ℓi(u,v′)=1 and Fi, Fj commute at v. Symmetrically: (b) if a vertex v has incoming i-edge (u,v) and incoming j-edge (u′,v) and if ℓj(u,v)=1, then ℓi(u′,v)=0 and Fi-1, Fj-1 commute at v. (See the following picture.)(1)One easily shows that if four vertices are connected by twoi-edges e, e′ and two j-edges e~,e~′ (forming a “square”), then ℓj(e)=ℓj(e′)≠ℓi(e~)=ℓi(e~′) (as illustrated in the picture). Another important consequence of (A3) is that for neighboring colors i,j, if v is the critical vertex on a maximal i-path w.r.t. color j, then v is also the critical vertex on the maximal j-path passing v w.r.t. color i; that is, we can speak of common critical vertices for the pair {i,j}.The fourth axiom points out situations when, for neighboringi,j, the operators Fi,Fj and their inverse ones “remotely commute” (forming the “Verma relation of degree 4”).(A4)
Let|i-j|=1. (i) If a vertex u has outgoing edges with color i and color j and if each edge is labeled 1 w.r.t. the other color, then FiFj2Fi(u)=FjFi2Fj(u). Symmetrically, (ii) if v has incoming edges with color i and color j and if both are labeled 0, then Fi-1(Fj-1)2Fi-1(v)=Fj-1(Fi-1)2Fj-1(v). (See the following picture.)(2)Again, one shows that the label w.r.t.i, j of each of the eight involved edges is determined uniquely, just as indicated in the above picture (where the bigger circles indicate critical vertices).The final axiom concerns nonneighboring colors.(A5)
Let|i-j|≥2. Then for any F∈{Fi,Fi-1} and F′∈{Fj,Fj-1}, the operators F,F′ commute at each vertex where both act.This is equivalent to saying that each component of the two-colored subgraph(V(K),Ei⊔Ej) is the Cartesian product of an i-path P and a j-path P′, or that each subcrystal of K with nonneighboring colors i, j is an A1×A1-crystal.One shows that anyAn-crystal K is finite and has exactly one zero-indegree vertex sK and one zero-outdegree vertex tK, called the source and sink of K, respectively. Furthermore, the An-crystals K admit a nice parameterization: the lengths h1(sK),…,hn(sK) of monochromatic paths starting at the source determine K, and for each tuple c=(c1,…,cn) of nonnegative integers, there exists a (unique) An-crystal K such that ci=hi(sK) for i=1,…,n. (See [4, 6].) We call c the parameter of K and denote K by K(c).


## 2.2.  The Crossing Model forAn-Crystals

Following [4], the crossing modelℳn(c) generating the An-crystal K=K(c) with a parameter c=(c1,…,cn)∈ℤ+n consists of three ingredients:(i)
a directed graphGn=G=(V(G),E(G)) depending on n, called the supporting graph of the model;(ii)
a setℱ=ℱ(c) of feasible functions on V(G);(iii)
a setℰ=ℰ(c) of transformations f↦f′ of feasible functions, called moves.To explain the construction of the supporting graphG, we first introduce another directed graph 𝒢=𝒢n that we call the protograph of G. Its node set consists of elements Vi(j) for all i,j∈{1,…,n} such that j≤i. (To avoid a possible mess, we prefer to use the term “node” for vertices in the crossing model, and the term “vertex” for vertices of crystals.) Its edges are all possible pairs of the form (Vi(j),Vi-1(j)) (ascending edges) or (Vi(j),Vi+1(j+1)) (descending edges). We say that the nodes Vi(1),…,Vi(i) form ith level of 𝒢 and order them as indicated (by increasing j). We visualize 𝒢 by drawing it on the plane so that the nodes of the same level lie in a horizontal line, the ascending edges point North-East, and the descending edges point South-East. See the picture where n=4.(3)The supporting graphG is produced by replicating elements of 𝒢 as follows. Each node Vi(j) generates n-i+1 nodes of G, denoted as vik(j) for k=i-j+1,…n-j+1, which are ordered by increasing k (and accordingly follow from left to right in the visualization). We identify Vi(j) with the set of these nodes and call it a multinode of G. Each edge of 𝒢 generates a set of edges of G (a multiedge) connecting elements with equal upper indices. More precisely, (Vi(j),Vi-1(j)) produces n-i+1 ascending edges (vik(j),vi-1k(j)) for k=i-j+1,…,n-j+1, and (Vi(j),Vi+1(j+1)) produces n-i descending edges (vik(j),vi+1k(j+1)) for k=i-j+1,…,n-j.The resultingG is the disjoint union of n directed graphs G1,…,Gn, where each Gk contains all vertices of the form vik(j). Also Gk is isomorphic to the Cartesian product of two paths, with the lengths k-1 and n-k. For example, for n=4, the graph G is viewed as (4)(where the multinodes are surrounded by ovals) and its componentsG1, G2, G3, G4 are viewed as (5)So each nodev=vik(j) of G has at most four incident edges, namely, (vi-1k(j-1),v), (vi+1k(j),v), (v,vi-1k(j)), and (v,vi+1k(j+1)); we refer to them, when exist, as the NW-, SW-, NE-, and SE-edges and denote them by eNW(v),eSW(v),eNE(v), and eSE(v), respectively.By afeasible function in the model (with a given c), we mean a function f:V(G)→ℤ+ satisfying the following three conditions, where for an edge e=(u,v), ∂f(e) denotes the increment f(u)-f(v) of f on e, and e is called tight for f, or f-tight, if ∂f(e)=0:
(6)(i)fismonotoneontheedges,inthesensethat∂f(e)≥0foralle∈E(G);(ii)0≤f(v)≤ckforeachv∈V(Gk),k=1,…,n;(iii)eachmultinodeVi(j)containsanodevwiththefollowingproperty:theedgeeSE(u)istightforeachnodeu∈Vi(j)precedingv,andeSW(u′)istightforeachnodeu′∈Vi(j)succeedingv.Thefirst node v=vik(j) (i.e., with k minimum) satisfying the property in (iii) is called the switch-node of the multinode Vi(j). These nodes play an important role in our transformations of feasible functions in the model.To describe the rule of transformingf∈ℱ(c), we first extend each Gk by adding extra nodes and extra edges (following [4] and aiming to slightly simplify the description). In the extended directed graph G-k, the node set consists of elements vik(j) for all i=0,…,n+1 and j=0,…,n such that j≤i. The edge set of G-k consists of all possible pairs of the form (vik(j),vi-1k(j)) or (vik(j),vi+1k(j+1)). Then all G-k are isomorphic. The disjoint union of these G-k gives the extended supporting graphG-. The creation of G-2 from G2 for n=4 is illustrated in the picture: (7)Each feasible function onV(G) is extended to the extra nodes v=vik(j) as follows: f(v):=ck if there is a path from v to a node of Gk, and f(v):=0 otherwise (one may say that v lies on the left of Gk in the former case and on the right of Gk in the latter case; in the above picture, such nodes v are marked by white and black circles, resp.). ∂f is extended to the extra edges accordingly. In particular, each edge e of G- not incident with a node of G is tight; that is, ∂f(e)=0. For a node v=vik(j) with 1≤j≤i≤n, define the value ε(v)=εf(v) by
(8)ε(v):=∂f(eNW(v))-∂f(eSE(u))=∂f(eSW(v))-∂f(eNE(u)),
where u:=vik(j-1). For a multinode Vi(j), define the numbers
(9)εi(j):=∑‍(ε(v):v∈Vi(j)),(10)εi(p,j):=εi(p)+εi(p+1)+⋯+εi(j)for1≤p≤j,ε~i(j):=max{0,min{εi(p,j):p=1,…,j}}.
We call ε(v), εi(j), and ε~i(j) the slack at a node v, the total slack at a multinode Vi(j), and the reduced slack at Vi(j), respectively. (Note that ε, ε~ are defined in  (8), (9), and (10) in a slightly different way than in [4], which, however, does not affect the choice of active multinodes and switch-nodes below.)Now we are ready to define the transformations off (or the moves from f). At most n transformations ϕ1,…,ϕn are possible. Each ϕi changes f within level i and is applicable when this level contains a multinode Vi(j′) with ε~i(j′)>0. In this case we take the multinode Vi(j) such that
(11)ε~i(j)>0,ε~i(q)=0forq>j,
referring to it as the active multinode for the given f and i. We increase f by 1 at the switch-node in Vi(j), preserving f on the other nodes of G. It is shown [4] that the resulting function ϕi(f) is again feasible.As a result, the model generatesn-colored directed graph 𝒦(c)=(ℱ,ℰ1⊔⋯⊔ℰn), where each color class ℰi is formed by the edges (f,ϕi(f)) for all feasible functions f to which the operator ϕi is applicable. This graph is just an An-crystal.Theorem 1 (see [4, Th. 5.1]).
For eachc∈ℤ+n, the n-colored graph 𝒦(c) is exactly the An-crystal K(c).


## 2.3.  Principal Lattice and(n-1)-Colored Subcrystals of an An-Crystal

Based on the crossing model, [4] reveals some important ingredients and relations for an An-crystal K=K(c). One of them is the so-called principal lattice, which is defined as follows.Leta∈ℤ+n and a≤c. One easily checks that the function on the vertices of the supporting graph G that takes the constant value ak within each subgraph Gk of G, k=1,…,n, is feasible. We denote this function and the vertex of K corresponding to it by f[a] and v˘[a], respectively, and call them principal ones. So the set of principal vertices is bijective to the integer box ℬ(c):={a∈ℤn:0≤a≤c}; this set is called the principal lattice of K and denoted by Π=Π(c). When it is not confusing, the term “principal lattice” may also be applied to ℬ(c).The following properties of the principal lattice will be essentially used later.Proposition 2 (see [4, Statement  (6.4)]).
Leta∈ℬ(c), k∈{1,…,n}, and a′:=a+1k (where 1k is ith unit base vector in ℝn). The principal vertex v˘[a′] is obtained from v˘[a] by applying the operator string
(12)Sn,k:=wn,k,n-k+1⋯wn,k,2wn,k,1,
where for j=1,…,n-k+1, the substring wn,k,j is defined as
(13)wn,k,j:=FjFj+1⋯Fj+k-1.
When acting on Π, any two (applicable) strings Sn,k,Sn,k′ commute. In particular, any principal vertex v˘[a] is expressed via the source sK=v˘[0] as
(14)v˘[a]=Sn,nanSn,n-1an-1⋯Sn,1a1(sK).Proposition 3 (see [4, Prop. 6.1]).
Forc′,c′′∈Z+n with c′≤c′′≤c, let K(c′:c′′) be the subgraph of K(c) formed by the vertices and edges contained in (directed) paths from v˘[c′] to v˘[c′′] (the interval of K(c) from v˘[c′] to v˘[c′′]). Then K(c′:c′′) is isomorphic to the An-crystal K(c′′-c′), and the principal lattice of K′ consists of the principal vertices v˘[a] of K(c) with c′≤a≤c′′.Let𝒦(-n)(c) denote the set of subcrystals with colors 1,…,n-1, and 𝒦(-1) the set of subcrystals with colors 2,…,n in K (recall that a subcrystal is assumed to be connected and maximal for the corresponding subset of colors).Proposition 4 (see [4, Prop. 7.1]).
Each subcrystal in𝒦(-n) (in 𝒦(-1)) contains precisely one principal vertex. This gives a bijection between 𝒦(-n) and Π (resp., between 𝒦(-1) and Π).We refer to the members of𝒦(-n) and 𝒦(-1) as upper and lower ((n-1)-colored) subcrystals of K, respectively. For a∈ℬ(c), the upper subcrystal containing the vertex v˘[a] is denoted by K↑[a]. This subcrystal has its own principal lattice of dimension n-1, which is denoted by Π↑[a]. We say that the coordinate tuple a is the locus of K↑[a] (and of Π↑[a]) in Π. Analogously, for b∈ℬ(c), the lower subcrystal containing v˘[b] is denoted by K↓[b] and its principal lattice by Π↓[b]; we say that b is the locus of K↓[b] (and of Π↓[b]) in Π. It turns out that the parameters of upper and lower subcrystals can be expressed explicitly as follows.Proposition 5 (see [4, Props. 7.2, 7.3]).
Fora∈ℬ(c), the upper subcrystal K↑[a] is isomorphic to the An-1-crystal K(c↑), where c↑ is the tuple (c1↑,…,cn-1↑) defined by
(15)ci↑:=ci-ai+ai+1,i=1,…,n-1.
The principal vertex v˘[a] is contained in the upper lattice Π↑[a] and its coordinate ℏ↑=(ℏ1↑,…,ℏn-1↑) in Π↑[a] satisfies
(16)ℏi↑=ai+1,i=1,…,n-1.
Symmetrically, forb∈ℬ(c), the lower subcrystal K↓[b] is isomorphic to the An-1-crystal K(c↓) with colors 2,…,n, where c↓ is defined by
(17)ci↓:=ci-bi+bi-1,i=2,…,n.
The principal vertex v˘[b] is contained in the lower lattice Π↓[b] and its coordinate ℏ↓=(ℏ2↓,…,ℏn↓) in Π↓[b] satisfies
(18)ℏi↓=bi-1,i=2,…,n.We callv˘[a] the heart of K↑[a] w.r.t. K, and similarly for lower subcrystals.(One more result given in [4, Remark 5] is a piecewise linear formula to compute, for an (n-1)-tuple q, the number of upper subcrystals of K(c) with the parameter equal to q, but we do not need this in what follows.)Remark 6.
As is mentioned in the Introduction, the crossing model is, in fact, a refinement of the Gelfand-Tsetlin pattern (orGT-pattern) model [7]. More precisely, for c∈ℤ+n, form the partition λ=(λ1≥λ2≥⋯≥λn≥λn+1=0) by setting λi:=c[1:n-i+1], where c[p:q] denotes cp+cp+1+⋯+cq. A GT-pattern for λ is a triangular array X=(xij)1≤j≤i≤n of integers satisfying (a) xij≥xi-1,j,xi+1,j+1 and (b) λi≥xn,i≥λi+1, for all possible i,j. It is shown in [4] that the set of feasible functions f in the crossing model ℳn(c) is bijective to the set of GT-patterns X for λ; such a correspondence is given by xi,j:=f^i(j)+c[1:i-j], where f^i(j) denotes the sum of values of f over the multinode Vi(j). However, it is not clear how to visualize, and work with, principal vertices directly in terms of GT-patterns, whereas such vertices are well visualized and fit to handle in the crossing model.


## 3.  Assembling anAn-Crystal

As mentioned in the Introduction, the structure of anAn-crystal K=K(c) can be described in a recursive manner. The idea is as follows. We know that K contains |Π|=(c1+1)×⋯×(cn+1) upper subcrystals (with colors 1,…,n-1) and |Π| lower subcrystals (with colors 2,…,n). Moreover, the parameters of these subcrystals are expressed explicitly by  (15) and  (17). Assume that the set 𝒦(-n) of upper subcrystals and the set 𝒦(-1) of lower subcrystals are already available. Then in order to assemble K, it suffices to point out, in appropriate terms, the intersection K↑[a]∩K↓[b] for all pairs a,b∈ℬ(c) (the intersection may either be empty or consist of one or more (n-2)-colored subcrystals with colors 2,…,n-1 in K). We give an appropriate characterization in Theorems 7 and 8.To state them, we need additional terminology and notation. Consider a subcrystalK↑[a], and let c↑,ℏ↑ be defined as in  (15), (16). For p=(p1,…,pn-1)∈ℬ(c↑), the vertex in the upper lattice Π↑[a] having the coordinate p is denoted by v↑[a,p]. We call the vector Δ:=p-ℏ↑ the deviation of v↑[a,p] from the heart v˘[a] in Π↑[a] and we will use the alternative notation v↑[a∣Δ] for this vertex. In particular, v˘[a]=v↑[a,ℏ↑]=v↑[a∣0].Similarly, for a lower subcrystalK↓[b], let c↓,ℏ↓ be as in  (17), (18). For q=(q2,…,qn)∈ℬ(c↓), the vertex with the coordinate q in Π↓[b] is denoted by v↓[a,q]. Its deviation is ∇:=q-ℏ↓, and we may alternatively denote this vertex by v↓[b∣∇].We call an(n-2)-colored subcrystal with colors 2,…,n-1 in K a middle subcrystal and denote the set of these by 𝒦(-1,-n). Each middle subcrystal K↑↓ is a lower subcrystal of some upper subcrystal K′=K↑[a] of K. By Proposition 4 applied to K′,  K↑↓ has a unique vertex v↑[a∣Δ] in the lattice Π↑[a]. So each K↑↓ can be encoded by a pair (a,Δ) formed by a point a∈ℬ(c) and a deviation Δ in Π↑[a]. At the same time, K↑↓ is an upper subcrystal of some lower subcrystal K↓[b] of K and has a unique vertex v↓[b∣∇] in Π↓[b]. Therefore, the members of 𝒦(-1,-n) determine a bijection
(19)ζ:(a,Δ)↦(b,∇)
between all pairs (a,Δ) concerning upper subcrystals and all pairs (b,∇) concerning lower subcrystals.The mapζ is expressed explicitly in the following two theorems. Here for a tuple ρ=(ρi:i∈I) of reals, we denote by ρ+ (ρ-) the tuple formed by ρi+:=max{0,ρi} (resp., ρi-:=min{0,ρi}), i∈I.Theorem 7 (on two deviations).
Leta∈ℬ(c) and let Δ=(Δ1,…,Δn-1) be a deviation in Π↑[a] (from the heart of K↑[a]). Let (b,∇)=ζ(a,Δ). Then
(20)∇i=-Δi-1,i=2,…,n.Theorem 8 (on two loci).
Leta,b,Δ,∇ be as in the previous theorem. Then
(21)bi=ai+Δi++Δi-1-,i=1,…,n,
letting Δ0=Δn:=0.Proofs of these theorems will be given in the next section.Based on Theorems7 and 8, the crystal K(c) is assembled as follows. By recursion we assume that all upper and lower subcrystals are already constructed. We also assume that for each upper subcrystal K↑[a]≃K(c↑), its principal lattice is distinguished by the use of the corresponding injective map σ:ℬ(c↑)→V(K(c↑)), and similarly for the lower subcrystals. We delete the edges with color 1 in each K↑[a] and extract the components of the resulting graphs, forming the set 𝒦(-1,-n) (arranged as a list) of all middle subcrystals of K(c). Each K↑↓∈𝒦(-1,-n) is encoded by a corresponding pair (a,Δ), where a∈ℬ(c) and the deviation Δ in Π↑[a] is determined by the use of σ as above. Acting similarly for the lower subcrystals K↓[b] (by deleting the edges with color n), we obtain the same set of middle subcrystals (arranged as another list), each of which being encoded by a corresponding pair (b,∇), where b∈ℬ(c) and ∇ is a deviation in Π↓(b). Relations  (21) and  (20) indicate how to identify each member of the first list with its counterpart in the second one. Now restoring the deleted edges with colors 1 and n, we obtain the desired crystal K(c). The corresponding map ℬ(c)→V(K(c)) is constructed easily (e.g., by the use of operator strings as in Proposition 2).We conclude this section with several remarks.Remark 9.
For eacha∈ℬ(c) and each vertex v=v↑[a,p] in the upper lattice Π↑[a], one can express the parameter c↑↓=(c2↑↓,…,cn-1↑↓) of the middle subcrystal K↑↓ containing v, as well as the coordinate ℏ↑↓=(ℏ2↑↓,…,ℏn-1↑↓) of its heart w.r.t. K↑[a] in the principal lattice of K↑↓. Indeed, since K↑↓ is a lower subcrystal of K↑[a], one can apply relations as in  (17) and (18). Denoting the parameter of K↑[a] by c↑ and the coordinate of its heart in Π↑[a] by ℏ↑, letting Δ:=p-ℏ↑, and using  (15), (16), we have for i=2,…,n-1,
(22)ci↑↓=ci↑-pi+pi-1=(ci-ai+ai+1)-(ai+1+Δi)+(ai+Δi-1)=ci-Δi+Δi-1,(23)ℏi↑↓=pi-1=ℏi-1↑+Δi-1=ai+Δi-1.
Symmetrically, ifK↑↓ is contained in K↓[b] and has deviation ∇ in Π↓[b], then for i=2,…,n-1,
(24)ci↑↓=ci-∇i+∇i+1,ℏi↓↑=bi+∇i+1,
where ℏ↓↑ is the coordinate of the heart of K↑↓ w.r.t. K↓[b] in the principal lattice of K↑↓ (note that ℏ↓↑ may differ from ℏ↑↓). We will use  (22) and  (24) in Section 4.Remark 10.
A straightforward implementation of the above recursive method of constructingK=K(c) takes O(2q(n)N) time and space, where q(n) is a polynomial in n and N is the number of vertices of K. Here the factor 2q(n) appears because the total number of vertices in the upper and lower subcrystals is 2N (implying that there appear 4N vertices in total on the previous step of the recursion, and so on). Therefore, such an implementation has polynomial complexity of the size of the output for each fixed n, but not in general. However, many intermediate subcrystals arising during the recursive process are repeated, and we can use this fact to improve the implementation. More precisely, the colors occurring in each intermediate subcrystal in the process form an interval of the ordered set (1,…,n). We call a subcrystal of this sort a color-interval subcrystal, or a CI-subcrystal, of K. In fact, every CI-subcrystal of K appears in the process. Since the number of intervals is n(n+1)/2 and the CI-subcrystals concerning equal intervals are pairwise disjoint, the total number of vertices of all CI-subcrystals of K is O(n2N). It is not difficult to implement the recursive process so that each CI-subcrystal K′ be explicitly constructed only once. As a result, we obtain the following.Proposition 11.
Letc∈ℤ+n. The An-crystal K(c) and all its CI-subcrystals can be constructed in O(q′(n)|V(K(c))|) time and space, where q′(n) is a polynomial in n.Remark 12.
Relation  (21) shows that the intersection of K↑[a] and K↓[b] may consist of many middle subcrystals. Indeed, if Δi>0 and Δi-1<0 for some i, then b does not change by simultaneously decreasing Δi by 1 and increasing Δi-1 by 1. The number of common middle subcrystals of K↑[a] and K↓[b] for arbitrary a,b∈ℬ(c) can be expressed by an explicit piecewise linear formula, using  (21) and the box constraints -ai+1≤Δi≤ci-ai, i=1,…,n-1, on the deviations Δ in Π↑[a] (which follow from  (15) and (16)).


## 4.  Proofs of Theorems7 and 8

Leta, Δ, b, ∇ be as in the hypotheses of Theorem 7. First we show that Theorem 7 follows from Theorem 8.Proof of (20) (in the assumption that (21) is valid).
The middle subcrystalK↑↓ determined by (a,Δ) is the same as the one determined by (b,∇). The parameter c↑↓ of K↑↓ is expressed simultaneously by  (22) and by  (24). Then ci-Δi+Δi-1=ci-∇i+∇i+1 for i=2,…,n-1. Therefore,
(25)Δ1+∇2=Δ2+∇3=⋯=Δn-1+∇n=:α.
In order to obtain  (20), one has to show that α=0. We argue as follows. Renumber the colors 1,…,n as n,…,1, respectively; this yields the crystal K^=K(c^) symmetric to K(c). Then K↓[b] turns into the upper subcrystal K^↑[b^] of K^, where (b^1,…,b^n)=(bn,…,b1). Also the deviation ∇ in Π↓[b] turns into the deviation ∇^=(∇^1,…,∇^n-1)=(∇n,…,∇2) in the principal lattice of K^↑[b^]. Applying relations as in  (21) to (b^,∇^), we have
(26)a^i=b^i+∇^i++∇^i-1-=bn-i+1+∇n-i+1++∇n-i+2-,i=1,…,n,
where a^i:=an-i+1 and ∇^n+:=∇^0-:=0. On the other hand,  (21) for (a,Δ) gives
(27)b^i=bn-i+1=an-i+1+Δn-i+1++Δn-i-,i=1,…,n.
Relations  (26) and  (27) imply
(28)an-i+1=bn-i+1+∇n-i+1++∇n-i+2-=(an-i+1+Δn-i+1++Δn-i-)+∇n-i+1++∇n-i+2-,
whence
(29)Δn-i+1++Δn-i-+∇n-i+1++∇n-i+2-=0,i=1,…,n.
Adding up the latter equalities, we obtain
(30)(Δ1+⋯+Δn-1)+(∇2+⋯+∇n)=0.
This and  (25) imply (n-1)α=0. Hence α=0, yielding  (20) and Theorem 7.Proof of Theorem8.
It is more intricate and essentially uses the crossing model.
For a feasible functionf∈ℱ(c) and its corresponding vertex v in K=K(c), we may denote v as vf and f as fv. From the crossing model it is seen that
(31)ifavertexv∈V(K)belongstoK↑[a]andtoK↓[b],thenthetuplesaandbareexpressedviathevaluesoff=fvinlevelsnand1asfollows:ak=f(vnk(n-k+1)),andbk=f(v1k(1))fork=1,…,n.
Indeed, the principal vertex v˘[a] is reachable from v by applying operators Fi or Fi-1 with i≠n. The corresponding moves in the crossing model do not change f within level n. Similarly, v˘[b] is reachable from v by applying operators Fi or Fi-1 with i≠1, and the corresponding moves do not change f within level 1. Also the first (second) equality in  (31) is valid for the principal function fv˘[a] (resp., fv˘[b]).
Next we introduce special functions on the node setV(G) of the supporting graph G=Gn. Consider a component Gk=(Vk,Ek) of G. It is a rectangular grid of size k×(n-k+1) (rotated by 45° in the visualization of G), and its vertex set is
(32)Vk={vik(j):j=1,…,n-k+1,i=j,…,j+k-1}.
To represent it in a more convenient form, let us rename vik(j) as xi-j+1k(j) or xi-j+1(j) (as though rotating Gk by 45°). Then
(33)Vk={xm(j):m=1,…,k,j=1,…,n-k+1},
the SE-edges of Gk become of the form (xm(j),xm(j+1)), and the NE-edges become of the form (xm(j),xm-1(j)). We distinguish the following subsets of Vk: (i)
the SW-sidePk:={xk(1),…,xk(n-k+1)};(ii)
theright rectangleRk:={xm(j):1≤m≤k-1,1≤j≤n-k+1};(iii)
theleft rectangleLk:={xm(j):1≤m≤k,1≤j≤n-k}. Denote the characteristic functions (in ℝVk) of Pk,Rk, and Lk as πk, ρk,andλk, respectively.
Return toa and Δ as above. We associate to (a,Δ) the functions
(34)fa,Δk:=akπk+(ak+Δk-1-)ρk+Δk+λk
on Vk for k=1,…,n (see Figure 1) and define fa,Δ to be the function on V(G) whose restriction to each Vk is fa,Δk.
In view of  (31), f=fa,Δ takes the values in levels n and 1 as required in  (21) (with k in place of i); namely, f(vnk(n-k+1))=ak and f(v1k(1))=ak+Δk++Δk-1- for k=1,…,n. Therefore, to obtain  (21) it suffices to show the following.
Lemma 13.(i) The functionf=fa,Δis feasible. (ii) The vertexvfbelongs toΠ↑[a]and has the deviationΔin it; in other words,f=fv˘[a∣Δ].
Proof. First we prove assertion (i). Let k∈{1,…,n}. We partition Vk into four subsets (rectangular pieces):
(35)Z1k:=Pk-{xkk(n-k+1)},Z2k:=Lk∖Pk,Z3k:={xkk(n-k+1)},Z4k:=Rk∖Lk,
where Z2k=Z4k=∅ when k=1, and Z1k=Z2k=∅ when k=n. By  (34),
(36)ftakesaconstantvaluewithineachpieceZqk;namely,ak+Δk+onZ1k,ak+Δk++Δk-1-onZ2k;akonZ3k,ak+Δk-1-onZ4k
(as illustrated in Figure 1). Also each edge of Gk connecting different pieces goes either from Z1k to Z2k∪Z3k or from Z2k∪Z3k to Z4k. This and  (36) imply that ∂f(e)≥0 for each edge e∈Ek, whence f satisfies  (6)(i).
The deviationΔ is restricted as -ℏ↑≤Δ≤c↑-ℏ↑, where c↑ is the parameter of the subcrystal K↑[a] and ℏ↑ is the coordinate of its heart v˘[a] in Π↑[a]. Formulas  (15) and  (16) for c↑ and ℏ↑ give
(37)-ak+1≤Δk≤ck-ak,-ak≤Δk-1≤ck-1-ak-1.
The inequalities Δk≤ck-ak and ak≤ck imply ak+Δk+≤ck. The inequalities -ak≤Δk-1 and ak≥0 imply ak+Δk-1-≥0. Then, in view of  (36), we obtain 0≤f(v)≤ck for each node v of Gk, yielding  (6)(ii).
To verify the switch condition  (6)(iii), consider a multinode Vi(j) with i<n. It consists of n-i+1 nodes vik(j), where i-j+1≤k≤n-j+1.
Leti≤n-2. Suppose that v=vik(j) is a node whose SW-edge e=(u,v) exists and is not f-tight. This is possible only if u∈Z1k and v∈Z2k. In this case, k is determined as k=i-j+2; that is, v is the second node in Vi(j). We observe that (a) for the first node vik-1(j) of Vi(j), both ends of its SE-edge e′ belong to the piece Z1k-1; and (b) for any node vik′(j) with k′>k in Vi(j), both ends of its SW-edge e′′ belong either to Z2k′ or to Z4k′. So, such e′ and e′′ are f-tight. Therefore, the node v satisfies the condition in  (6)(iii) for Vi(j).
Now leti=n-1. Then Vi(j) consists of two nodes v=vn-1n-j(j) and v′=vn-1n-j+1(j). Put k:=n-j. Then the edge e=eSE(v) goes from Z1k to Z3k={xkk(n-k+1)}, and the edge e′=eSW(v′) goes from Z3k+1={xk+1k+1(n-k)} to Z4k+1. By  (36), we have ∂f(e)=(ak+Δk+)-ak=Δk+ and ∂f(e′)=ak+1-(ak+1+Δk-)=-Δk-. Since at least one of Δk+,Δk- is zero, we conclude that at least one of e,e′ is tight. So  (6)(iii) is valid again.
Next we prove assertion (ii) in the lemma. (The idea is roughly as follows. For eachk, compare the function fa,Δk=:g with the function h on Vk taking the constant value ak. By  (34), g=h+Δk+λk+Δk-1-ρk. In other words, g is obtained from fv˘[a]∣Vk by adding Δk+ times the “left rectangle function” λk, followed by subtracting |Δk-1-| times the “right rectangle function” ρk. A crucial observation is that adding λk corresponds to applying the operator string Sn-1,k (or shifting by kth unit base vector in the upper principal lattice Π↑[a]), while subtracting ρk corresponds to applying Sn-1,k-1-1 (or shifting by minus (k-1)th unit base vector in Π↑[a]). This is because the substrings w in Sn-1,k correspond to the SW-NE paths in Lk, and the substrings in Sn-1,k-1 to similar paths in Rk≃Lk-1).
Now we give a more careful and formal description. We use induction on(38)η(Δ):=Δ1+⋯+Δn-1.
In view of  (37), η(Δ)≥-a2-⋯-an. Suppose that this turns into equality. Then Δk=-ak+1≤0 for k=1,…,n-1, and f=fa,Δ takes the following values within each Vk (cf.  (36)): f(v)=ak if v∈Pk, and f(v)=0 if v∈Vk-Pk. This f is the minimal feasible function whose values in level n correspond to a; that is, vf is the source of K↑[a]. Then vf is the minimal vertex v˘[a,0] in Π↑[a], and its deviation in Π↑[a] is just Δ, as required. This gives the base of our induction.
Now consider an arbitraryΔ satisfying (37). Let k be such that Δk<ck-ak (if any) and define Δ′k:=Δk+1 and Δ′i:=Δi for i≠k. Then η(Δ)<η(Δ′). We assume by induction that assertion (ii) is valid for fa,Δ, and our aim is to show validity of (ii) for fa,Δ′.
In what followsf stands for the former function fa,Δ.
Letv′ be the vertex with the deviation Δ′ in Π↑[a]. Both vf and v′ are principal vertices of the subcrystal K↑[a], and the coordinate of v′ in Π↑[a] is obtained from the one of vf by increasing its kth entry by 1. According to Proposition 2 (with n is replaced by n-1), v′ is obtained from vf by applying the operator string
(39)Sn-1,k=wn-1,k,n-k⋯wn-1,k,1,
where wn-1,k,j=Fj⋯Fj+k-1 (cf.  (12)). In light of this, we have to show that
(40)when(thesequenceofmovescorrespondingto)Sn-1,kisappliedtof,theresultingfeasiblefunctionisexactlyfa,Δ′.
For convenience,mth term Fj+m-1 in the substring wn-1,k,j will be denoted by ϕ(j,m), m=1,…,k. So wn-1,k,j=ϕ(j,1)ϕ(j,2)⋯ϕ(j,k).
We distinguish between two cases:Δk≥0 and Δk<0.
Case
1 [Δk≥0]. An essential fact is that the number k(n-k) of operators in Sn-1,k is equal to the number of nodes in the left rectangle Lk of Gk. Moreover, the level of each node xm(j) of Lk is equal to the “color” of the operator ϕ(j,m) (indeed, xm(j)=vj+m-1k(j) and ϕ(j,m)=Fj+m-1).
Letfj,m denote the current function on V(G) just before the application of ϕ(j,m) (when the process starts with f=fa,Δ). We assert that
(41)foreachm,theapplicationofϕ(j,m)tofj,mincreasesthevalueatthenodexmk(j)by1,
whence  (40) will immediately follow.
In order to show  (41), we first examine tight edges and the slacks ε(v) of the nodes v in levels <n for the initial function f. One can see from  (36) that
(42)fork′=1,…,n,eachnodevofthesubgraphGk′hasatleastoneenteringedge(i.e.,eSW(v)oreNW(v))whichisf-tight,except,possibly,forthenodesvk′k′(1),vk′-1k′(1),vnk′(n-k′+1),vn-1k′(n-k′+1)
indicated by stars in Figure1.
Claim. For k′=1,…,n and a node v of  Gk′ at a level <n,(a)
ifv≠vk′k′(1),vk′-1k′(1), then ε(v)=0;(b)
ifv=vk′k′(1), then ε(v)=ck′-ak′-Δk′+≥0;(c)
ifv=vk′-1k′(1), then ε(v)=-Δk′-≥0.
Proof of Claim.Let v=vik′(j) and i<n. By  (8), the slack ε(v) is equal to f(w)+f(z)-f(u)-f(v), where w:=vi-1k′(j-1), z:=vi+1k′(j), u:=vik′(j-1) (these vertices belong to the extended graph G-k′). We consider possible cases and use  (36).(i)
Ifw,z,u are in Gk′, then ∂f(w,v)=∂f(u,z).(ii)
If bothv,w are in the piece Z1k′ of Gk′, then f(w)=f(v) and f(u)=f(z)=ck′.(iii)
Ifj=1 and i≤k′-2, then f(v)=f(z) and f(u)=f(w)=ck′. So in these cases we have ε(v)=0, yielding (a).(iv)
Letv=vk′k′(1). Then f(v)=ak′+Δk′+ and f(u)=f(w)=f(z)=ck′. This gives ε(v)=ck′-ak′-Δk′+, yielding (b).(v)
Letv=vk′-1k′(1). Then f(v)=ak′+Δk′++Δk′-1-, f(z)=ak′+Δk′+ and f(u)=f(w)=ck′. This gives ε(v)=-Δk′-1-, yielding (c).
This claim and the relationsΔk-=0 and Δk<ck-ak enable us to estimate the total slacks εi(j) for f at the multinodes Vi(j) with i<n:
(43)(i)theedgeeSW(vkk+1(1))isf-tight,ε(vkk(1))>0,andε(v)=0fortheothernodesvinVk(1);soεk(1)>0;(ii)ifi≠k,n,thenε(vii(1)),ε(vii+1(1))≥0andε(v)=0fortheothernodesvinVi(1);soεi(1)≥0;(iii)ifi≠nandj>1,thenε(v)=0forallnodesvinVi(j);soεi(j)=0.
Now we are ready to prove  (41). When dealing with a current function fj,m and seeking for the node at level j+m-1 where the operator ϕ(j,m) should act to increase fj,m, we can immediately exclude from consideration any node v that has at least one tight entering edge (in view of the monotonicity condition  (6)(i)).
Due to  (42) and  (43)(i), for the initial function f=f1,k, there is only one node in level k that has no tight entering edge, namely, vkk(1). So, at the first step of the process, the first operator ϕ(1,k) of Sn-1,k acts just at vkk(1), as required in  (41).
Next consider a step withf′:=fj,m for (j,m)≠(1,k), assuming validity of  (41) on the previous steps.
(A) Letj=1 (and m<k). For v:=vmk(1) and z:=vm+1k(1), we have f′(v)=f(v)≤f(z)=f′(z)-1. So the unique edge e=(z,v) entering v is not f′-tight. By  (42), there are at most two other nodes in level m that may have no tight entering edges for f (and therefore, for f′), namely, vmm(1) and vmm+1(1). Then ϕ(1,m) must act at v, as required in  (41) (since the nontightness of the SW-edge e of v implies that none of the nodes vmm′(1) in Vm(1) preceding v (i.e., with m′<k) can be the switch-node).
(B) Letj>1. Comparing f′ with f in the node v:=xmk(j)=vj+m-1k(j) and its adjacent nodes, we observe that v has no f′-tight entering edge and that εf′(v)>0. Also for any other node v′ in level j+m-1, one can see that if v′ has a tight entering edge for f, then this property holds for f′ as well, and that εf(v′)≥εf′(v′)≥0. Using this, properties  (42), (43) (iii), and condition  (11), one can conclude that the total and reduced slacks for f′ at the multinode V′:=Vj+m-1(j) are positive, that V′ is the active multinode for f′ in level j+m-1, and that ϕ(j,m) can be applied only at v, yielding  (41) again.
Thus,  (40) is valid in Case 1.
Case
2 [Δk<0]. We assert that in this case the string Sn-1,k acts within the right rectangle Rk+1 of the subgraph Gk+1 (note that Rk+1 is of size k×(n-k)). More precisely,
(44)eachoperatorϕ(j,m)modifiesthecurrentfunctionbyincreasingitsvalueatthenodexmk+1(j)by1.
Then the resulting function in the process is justfa,Δ′ (in view of (Δ′)k-=Δk-+1), yielding  (40).
To show  (44), we argue as in the previous case and use  (42) and the previous claim. Since Δk<0, part (i) in  (43) for the initial function f is modified as follows:
(45)forj=1,…,n-k,theSW-edgeofeachnodexkk+1(j)=vj+k-1k+1(j)isnotf-tight,ε(vkk+1(1))>0,ε(vkk(1))≥0,andε(v)=0fortheothernodesvinVk(1);soεk(1)>0,
while properties (ii) and (iii) preserve.
By  (42) and  (45), there are only two nodes in level k that have no f-tight entering edges, namely, vkk(1) and vkk+1(1). Also e=eSW(vkk+1(1)) is not tight. So, at the first step, ϕ(1,k) must act at vkk+1(1), as required in  (44) (since the nontightness of e implies that the node vkk(1) preceding vkk+1(1) cannot be the switch-node in Vk(1)).
The fact thatϕ(1,m) with m<k acts at vmk+1(1) is shown by arguing as in (A) above. And for j>1, to show that ϕ(j,m)=Fj+m-1 acts at xmk+1(j)=vj+m-1k+1(j), we argue as in (B) above. Here, when m=k, we also use the fact that the edge eSW(xkk+1(j)) is not f-tight (by  (45) ), whence both edges entering xkk+1(j) are not tight for the current function. So  (44) is always valid.
Thus, we have the desired property  (40) in both Cases 1 and 2, and statement (ii) in Lemma 13 follows.
This completes the proof of relation  (21), yielding Theorem 8.Figure 1
The partition ofVk (see Section 4).


## 5.  Illustrations

In this concluding section, we give two illustrations to the above assembling construction for A-crystals. The first one refines the interrelation between upper and lower subcrystals in an arbitraryA2-crystal; this can be compared with the explicit construction (the so-called “sail model”) for A2-crystals in [3]. The second one visualizes the subcrystals structure for one instance of A3-crystals, namely, K(1,1,1).


### 5.1.A2-Crystals

The subcrystals structure becomes simpler when we deal with anA2-crystal K=K(c1,c2). In this case the roles of upper, lower, and middle subcrystals are played by 1-paths, 2-paths, and vertices of K, respectively, where by an i-path we mean a maximal path of color i.Consider an upper subcrystal inK. This is a 1-path P=(v0,v1,…,vp) containing exactly one principal vertex v˘[a] of K (the heart of P); here vi stands for ith vertex in P,  a=(a1,a2)∈ℤ+2, and a≤c. Let v˘[a]=vh. Formulas  (15) and  (16) give
(46)|P|=p=c1-a1+a2,h=a2.
Fix a vertex v=vi of P. It belongs to some 2-path (lower subcrystal) Q=(u1,u2,…,uq). Let v=uj and let v˘[b]=uh- be the principal vertex of K occurring in Q (the heart of Q). The vertex v forms a middle subcrystal of K; its deviations from the heart of P and from the heart of Q are equal to i-h=:δ and j-h-=:δ-, respectively. By  (20) in Theorem 7, we have δ-=-δ. Then we can compute the coordinates b by the use of  (21) and, further, apply  (17) and  (18) to compute the length of Q and the locus of its heart. This gives the following:
(47)(i)ifδ≥0(i.e.,a2≤i≤c1-a1+a2),thenb1=a1+δ=a1+i-a2,b2=a2,|Q|=c2-b2+b1=c2-2a2+a1+i,and|Q|-h-=|Q|-b1=c2-a2;(ii)ifδ≤0(i.e.,0≤i≤a2),thenb1=a1,b2=a2+δ=a2+(i-a2)=i,|Q|=c2-b2+b1=c2-i+a1,andh-=b1=a1.Using  (46) and  (47), one can enumerate the sets of 1-paths and 2-paths and properly intersect corresponding pairs, obtaining the A2-crystal K(c). It is rather routine to check that the resulting graph coincides with the one generated by the sail model from [3]. Next we outline that construction.Givenc∈ℤ+2, the A2-crystal K(c) is produced from two particular two-colored graphs R and L, called the right sail of size c1 and the left sail of size c2, respectively. The vertices of R correspond to the vectors (i,j)∈ℤ2 such that 0≤j≤i≤c1, and the vertices of L to the vectors (i,j)∈ℤ2 such that 0≤i≤j≤c2. In both R and L, the edges of color 1 are all possible pairs of the form ((i,j),(i+1,j)), and the edges of color 2 are all possible pairs of the form ((i,j),(i,j+1)). (Observe that both R and L satisfy axioms (A1)–(A4), R is isomorphic to K(c1,0),  L is isomorphic to K(0,c2), and their critical vertices are the “diagonal vertices” (i,i).)In order to produceK(c), take c2 disjoint copies R1,…,Rc2 of R and c1 disjoint copies L1,…,Lc1 of L, referring to Rj as jth right sail and to Li as ith left sail. Let D(Rj) and D(Li) denote the sets of diagonal vertices in Rj and Li, respectively. For all i=1,…,c1 and j=1,…,c2, we identify the diagonal vertices (i,i)∈D(Rj) and (j,j)∈D(Li). The resulting graph is just the desired K(c). The edge colors of K(c) are inherited from L and R. One checks that K(c) has (c1+1)×(c2+1) critical vertices; they coincide with the diagonal vertices of the sails. The principal lattice of K(c) is just constituted by the critical vertices.The case(c1,c2)=(1,2) is drawn in the picture; here the critical (principal) vertices are indicated by big circles, 1-edges by horizontal arrows, and 2-edges by vertical arrows:
(48)In particular, the sail model shows that the numbers of edges of each color in anA2-crystal are the same. This implies a similar property for any An-crystal.


### 5.2.A3-Crystal K(1,1,1)

Next we illustrate theA3-crystal K=K(1,1,1). It has 64 vertices and 102 edges, is rather puzzling, and drawing it in full would be cumbersome and take too much space; for this reason, we expose it by fragments; namely, we demonstrate all of its upper and lower subcrystals. We abbreviate notation v˘[(i,j,k)] for principal vertices to (i,j,k) for short. So the principal lattice consists of eight vertices (0,0,0),…,(1,1,1), as drawn in the picture (where the arrows indicate moves by principal operator strings S3,k as in  (12)):
(49)Thus,K has eight upper subcrystals K↑[i,j,k] and eight lower subcrystals K↓[i,j,k] (writing K•[i,j,k] for K•[(i,j,k)]); they are drawn in Figures 2 and 3. Here the directions of edges of colors 1,2,3 are as indicated in the upper left corner. In each subcrystal, we indicate its critical vertices by black circles and the unique principal vertex of K occurring in it (the heart) by a big white circle. K has 30 middle subcrystals (paths of color 2), which are labeled as A,…,Z,Γ,Δ,Φ,Ψ (note that B,F,G,N,P,T,V,andΦ consist of single vertices).Figure 2
The upper subcrystals inK(1,1,1) (see Section 5).Figure 3
The lower subcrystals inK(1,1,1) (see Section 5).For each upper subcrystalK↑[i,j,k], its parameter c↑ and heart locus ℏ↑, computed by use of  (15) and  (16), are as follows (where K~,s~,andz denote the current subcrystal, its source, and its heart, resp.):(i)
forK↑[0,0,0]: c1↑=1-0+0=1, c2↑=1-0+0=1, and ℏ1↑=ℏ2↑=0 (so K~ is isomorphic to K(1,1) and z coincides with s~);(ii)
forK↑[1,0,0]: c1↑=1-1+0=0, c2↑=1-0+0=1, and ℏ1↑=ℏ2↑=0;(iii)
forK↑[0,1,0]: c1↑=1-0+1=2, c2↑=1-1+0=0, ℏ1↑=1, and ℏ2↑=0 (so K~≃K(2,0) and z is located at S2,1(s~)=F2F1(s~));(iv)
forK↑[0,0,1]: c1↑=1-0+0=1, c2↑=1-0+1=2, ℏ1↑=0, and ℏ2↑=1 (so K~≃K(1,2) and z is located at S2,2(s~)=F1F2(s~));(v)
forK↑[1,1,0]: c1↑=1-1+1=1, c2↑=1-1+0=0, ℏ1↑=1, and ℏ2↑=0;(vi)
forK↑[1,0,1]: c1↑=1-1+0=0, c2↑=1-0+1=2, ℏ1↑=0, and ℏ2↑=1;(vii)
forK↑[0,1,1]: c1↑=1-0+1=2, c2↑=1-1+1=1, and ℏ1↑=ℏ2↑=1 (so K~≃K(2,1) and z is located at S2,2S2,1(s~)=F1F2F2F1(s~));(viii)
forK↑[1,1,1]: c1↑=1-1+1=1, c2↑=1-1+1=1, and ℏ1↑=ℏ2↑=1.SinceK(1,1,1) is “symmetric,” so are its upper and lower subcrystals; that is, each K↓[i,j,k] is obtained from K↑[k,j,i] by replacing color 1 by 3. In Figure 3, when writing K↓[i,j,k]≃K(α,β), the parameters α,β concern colors 3 and 2, respectively.Now the desiredK(1,1,1) is assembled by gluing the fragments in Figures 2 and 3 along the 2-paths A,…,Ψ.


## 5.1.A2-Crystals

The subcrystals structure becomes simpler when we deal with anA2-crystal K=K(c1,c2). In this case the roles of upper, lower, and middle subcrystals are played by 1-paths, 2-paths, and vertices of K, respectively, where by an i-path we mean a maximal path of color i.Consider an upper subcrystal inK. This is a 1-path P=(v0,v1,…,vp) containing exactly one principal vertex v˘[a] of K (the heart of P); here vi stands for ith vertex in P,  a=(a1,a2)∈ℤ+2, and a≤c. Let v˘[a]=vh. Formulas  (15) and  (16) give
(46)|P|=p=c1-a1+a2,h=a2.
Fix a vertex v=vi of P. It belongs to some 2-path (lower subcrystal) Q=(u1,u2,…,uq). Let v=uj and let v˘[b]=uh- be the principal vertex of K occurring in Q (the heart of Q). The vertex v forms a middle subcrystal of K; its deviations from the heart of P and from the heart of Q are equal to i-h=:δ and j-h-=:δ-, respectively. By  (20) in Theorem 7, we have δ-=-δ. Then we can compute the coordinates b by the use of  (21) and, further, apply  (17) and  (18) to compute the length of Q and the locus of its heart. This gives the following:
(47)(i)ifδ≥0(i.e.,a2≤i≤c1-a1+a2),thenb1=a1+δ=a1+i-a2,b2=a2,|Q|=c2-b2+b1=c2-2a2+a1+i,and|Q|-h-=|Q|-b1=c2-a2;(ii)ifδ≤0(i.e.,0≤i≤a2),thenb1=a1,b2=a2+δ=a2+(i-a2)=i,|Q|=c2-b2+b1=c2-i+a1,andh-=b1=a1.Using  (46) and  (47), one can enumerate the sets of 1-paths and 2-paths and properly intersect corresponding pairs, obtaining the A2-crystal K(c). It is rather routine to check that the resulting graph coincides with the one generated by the sail model from [3]. Next we outline that construction.Givenc∈ℤ+2, the A2-crystal K(c) is produced from two particular two-colored graphs R and L, called the right sail of size c1 and the left sail of size c2, respectively. The vertices of R correspond to the vectors (i,j)∈ℤ2 such that 0≤j≤i≤c1, and the vertices of L to the vectors (i,j)∈ℤ2 such that 0≤i≤j≤c2. In both R and L, the edges of color 1 are all possible pairs of the form ((i,j),(i+1,j)), and the edges of color 2 are all possible pairs of the form ((i,j),(i,j+1)). (Observe that both R and L satisfy axioms (A1)–(A4), R is isomorphic to K(c1,0),  L is isomorphic to K(0,c2), and their critical vertices are the “diagonal vertices” (i,i).)In order to produceK(c), take c2 disjoint copies R1,…,Rc2 of R and c1 disjoint copies L1,…,Lc1 of L, referring to Rj as jth right sail and to Li as ith left sail. Let D(Rj) and D(Li) denote the sets of diagonal vertices in Rj and Li, respectively. For all i=1,…,c1 and j=1,…,c2, we identify the diagonal vertices (i,i)∈D(Rj) and (j,j)∈D(Li). The resulting graph is just the desired K(c). The edge colors of K(c) are inherited from L and R. One checks that K(c) has (c1+1)×(c2+1) critical vertices; they coincide with the diagonal vertices of the sails. The principal lattice of K(c) is just constituted by the critical vertices.The case(c1,c2)=(1,2) is drawn in the picture; here the critical (principal) vertices are indicated by big circles, 1-edges by horizontal arrows, and 2-edges by vertical arrows:
(48)In particular, the sail model shows that the numbers of edges of each color in anA2-crystal are the same. This implies a similar property for any An-crystal.


## 5.2.A3-Crystal K(1,1,1)

Next we illustrate theA3-crystal K=K(1,1,1). It has 64 vertices and 102 edges, is rather puzzling, and drawing it in full would be cumbersome and take too much space; for this reason, we expose it by fragments; namely, we demonstrate all of its upper and lower subcrystals. We abbreviate notation v˘[(i,j,k)] for principal vertices to (i,j,k) for short. So the principal lattice consists of eight vertices (0,0,0),…,(1,1,1), as drawn in the picture (where the arrows indicate moves by principal operator strings S3,k as in  (12)):
(49)Thus,K has eight upper subcrystals K↑[i,j,k] and eight lower subcrystals K↓[i,j,k] (writing K•[i,j,k] for K•[(i,j,k)]); they are drawn in Figures 2 and 3. Here the directions of edges of colors 1,2,3 are as indicated in the upper left corner. In each subcrystal, we indicate its critical vertices by black circles and the unique principal vertex of K occurring in it (the heart) by a big white circle. K has 30 middle subcrystals (paths of color 2), which are labeled as A,…,Z,Γ,Δ,Φ,Ψ (note that B,F,G,N,P,T,V,andΦ consist of single vertices).Figure 2
The upper subcrystals inK(1,1,1) (see Section 5).Figure 3
The lower subcrystals inK(1,1,1) (see Section 5).For each upper subcrystalK↑[i,j,k], its parameter c↑ and heart locus ℏ↑, computed by use of  (15) and  (16), are as follows (where K~,s~,andz denote the current subcrystal, its source, and its heart, resp.):(i)
forK↑[0,0,0]: c1↑=1-0+0=1, c2↑=1-0+0=1, and ℏ1↑=ℏ2↑=0 (so K~ is isomorphic to K(1,1) and z coincides with s~);(ii)
forK↑[1,0,0]: c1↑=1-1+0=0, c2↑=1-0+0=1, and ℏ1↑=ℏ2↑=0;(iii)
forK↑[0,1,0]: c1↑=1-0+1=2, c2↑=1-1+0=0, ℏ1↑=1, and ℏ2↑=0 (so K~≃K(2,0) and z is located at S2,1(s~)=F2F1(s~));(iv)
forK↑[0,0,1]: c1↑=1-0+0=1, c2↑=1-0+1=2, ℏ1↑=0, and ℏ2↑=1 (so K~≃K(1,2) and z is located at S2,2(s~)=F1F2(s~));(v)
forK↑[1,1,0]: c1↑=1-1+1=1, c2↑=1-1+0=0, ℏ1↑=1, and ℏ2↑=0;(vi)
forK↑[1,0,1]: c1↑=1-1+0=0, c2↑=1-0+1=2, ℏ1↑=0, and ℏ2↑=1;(vii)
forK↑[0,1,1]: c1↑=1-0+1=2, c2↑=1-1+1=1, and ℏ1↑=ℏ2↑=1 (so K~≃K(2,1) and z is located at S2,2S2,1(s~)=F1F2F2F1(s~));(viii)
forK↑[1,1,1]: c1↑=1-1+1=1, c2↑=1-1+1=1, and ℏ1↑=ℏ2↑=1.SinceK(1,1,1) is “symmetric,” so are its upper and lower subcrystals; that is, each K↓[i,j,k] is obtained from K↑[k,j,i] by replacing color 1 by 3. In Figure 3, when writing K↓[i,j,k]≃K(α,β), the parameters α,β concern colors 3 and 2, respectively.Now the desiredK(1,1,1) is assembled by gluing the fragments in Figures 2 and 3 along the 2-paths A,…,Ψ.



---

*Source: 483949-2013-03-20.xml*