# Diagrammatics for Soergel Categories

Authors: Ben Elias; Mikhail Khovanov
Journal: International Journal of Mathematics and Mathematical Sciences
 (2010)

---

## Abstract

The monoidal category of Soergel bimodules can be thought of as a categorification of the Hecke algebra of a finite Weyl group. We present this category, when the Weyl group is the symmetric group, in the language of planar diagrams with local generators and local defining relations.


---

## Body

## 1. Introduction

In this paper [1], Soergel gave a combinatorial description of a certain category of Harish-Chandra bimodules over a simple Lie algebra 𝔤. This category was and continues to be of primary interest in the infinite-dimensional representation theory of simple Lie algebras. Soergel discovered a functor from this category to a full subcategory of bimodules over a certain ring R, the objects of which are now commonly called Soergel bimodules. The category of Soergel bimodules is additive and monoidal, unlike the original category which is abelian, but it still has sufficient information to describe the original category. Soergel constructed an isomorphism between the Grothendieck ring of his category and the integral form of the Hecke algebra of the Weyl group W of 𝔤. Hence, Soergel's construction provides a categorification of the Hecke algebra.Given ak-dimensional 𝕔-vector space V and a generic q∈𝕔, there are commuting actions of the quantum group Uq(𝔰𝔩k) and the Hecke algebra H of the symmetric group Sn on V⊗n. These actions turn the quotient Uq(𝔰𝔩k)/J1 of the quantum group and H/J2 of the Hecke algebra by the kernels of these action into a dual pair. A categorical realization of the triple (V⊗n,Uq(𝔰𝔩k)/J1,H/J2) was given by Grojnowski and Lusztig [2] via categories of perverse sheaves on products of flag and partial flag varieties, also see [3–6].Many foundational ideas about categorification were put forward by Igor Frenkel in the early 90s (a small fraction of these ideas formed a part of the paper [7]). In particular, Frenkel conjectured [8] that quantum groups and not just their finite-dimensional quotients Uq(𝔰𝔩k)/J1 can be categorified. These conjectures remained open until recently, when categorifications of quantum 𝔰𝔩2 and 𝔰𝔩k were discovered in [9, 10], with a related but different approach developed in [11, 12]. In the categorifications [9, 10] of quantum groups, 2 morphisms are given by linear combinations of planar diagrams, modulo local relations.The parallel objective would be to categorify the Hecke algebra in the same spirit, using planar diagrams. Soergel had already provided a categorification, so it remains to ask whether his category can be rephrased diagrammatically. Diagrammatics should also provide a presentation of the category by generators and relations. A similar question was recently posed by Libedinsky [13], who essentially produced such a description for categorifications of Hecke algebras associated to “right-angled” Coxeter systems.Here, we answer this question positively in the case of the Hecke algebra associated to the symmetric group. This is, of course, the Hecke algebra that appears in the Schur-Weyl duality forV⊗n. For notational convenience, we use n+1, not n, as our parameter and define a diagrammatical version 𝒟𝒞 of the category of Soergel bimodules that categorifies the Hecke algebra of the symmetric group Sn+1.In some sense, diagrammatic categorifications are very “low-tech,” in that they can be described easily and do not rely on heavy machinery. While one can prove that Soergel bimodules categorify the Hecke algebra using only elaborate commutative algebra (see [14], although it is never stated explicitly), showing that indecomposable bimodules descend to the Kazhdan-Lusztig basis of the Hecke algebra utilizes Kazhdan-Lusztig theory [15, 16]. This, in turn, is related to fundamental developments in geometric representation theory like D-modules on flag manifolds [17, 18] and perverse sheaves [19]. One hopes that a diagrammatic approach will help to visualize and work with these sophisticated constructions, in the same way that the categorifications of quantum groups [9, 10] have led to an improved understanding of perverse sheaves on quiver varieties (see [20]). One also hopes that this approach can shed light on categorifications of representations of the Hecke algebra coming from the context of category 𝒪 (see [21]).We start with an intermediate category𝒟𝒞1 whose objects are finite sequences i̲=i1⋯id of numbers between 1 and n. An object is represented graphically by marking d points in the standard position (say, having coordinates 1,…,d) on the x-axis and assigning labels i1,…,id to marked points from left to right. Morphisms between i̲ and j̲ are given by linear combinations (with coefficients in a ground field 𝕜) of planar diagrams embedded in the strip ℝ×[0,1]. These diagrams are decorated planar graphs, where edges may extend to the boundary ℝ×{0,1}. Each edge carries a label between 1 and n, so that the induced labellings of the lower and upper boundaries are i̲ and j̲, respectively. In the interior of the strip, we allow (1)
vertices of valence 1,(2)
vertices of valence 3 with all 3 edges carrying the same label,(3)
vertices of valence 4 seen as intersections ofi and j-labelled lines with |i-j|>1,(4)
vertices of valence 6 with the edge labellingi, i+1, i, i+1, i, i+1, reading clockwise around the vertex,(5)
boxes labelled by numbers between 1 andn+1 which float in the regions of the graph.We impose a set of local relations on linear combinations of these diagrams, including invariance of diagrams under all isotopies. A subset of the relations says thati is a Frobenius object in the category 𝒟𝒞1.The space of morphisms in𝒟𝒞1 between i̲ and j̲ is naturally a graded vector space. Allowing grading shifts and direct sums of objects, then restricting to grading-preserving morphisms, and finally passing to the Karoubian closure of the category results in a graded 𝕜-linear additive monoidal category 𝒟𝒞. Our main result (Theorem 4.22 in Section 4) is an explicit equivalence between this category and the category 𝒮𝒞 of Soergel bimodules.The category𝒟𝒞 is monoidal, and can be viewed as a 2-category with a single object. It may be easier to tackle the diagrammatics after reading an introductory reference on diagrammatics for 2-categories. Such an introduction can be found in [9]. This may make it easier to explore similarities with the categorifications of quantum groups in [9, 10], where regions of diagrams are labelled by integers in [9] and integral weights of 𝔰𝔩n in [10]. Boxes floating in regions are superficially analogous to floating bubbles of [9, 10]. Unlike the diagrammatic categorifications in [9, 10], our lines do not carry dots and are not oriented.There is another way to view our diagrammatics, which is not developed in this paper. Rouquier [22, 23] defined an action of the Coxeter braid group associated to W on the category of complexes of Soergel bimodules up to homotopies, which is related to a braid group action using Harish-Chandra bimodules that had been known for some time. These complexes were later used in an alternative construction [24] of a triply graded link homology theory [25] categorifying the HOMFLY-PT polynomial [25–28]. In this approach, a product Soergel bimodule Bi1⊗⋯⊗Bid is depicted by a planar diagram given by concatening elementary planar diagrams lying in the xy-plane that consist of n+1 strands going up, with i and i+1-st strands merging and splitting, see [24, Figures 2 and 3]. Morphisms between product bimodules can be realized by linear combinations of foams—decorated two-dimensional CW-complexes embedded in ℝ3 with suitable boundary conditions. Foams have been implicit throughout papers on triply graded link homology (see [29] for instance, where various arrows between planar diagrams can be implemented by foams), and explicitly appear in the papers on their doubly-graded cousins, see [30, 31] and references therein.Foams are 3-dimensional objects; they are two-dimensional CW-complexes embedded inℝ3 that produce cobordisms along the z-axis direction between planar objects corresponding to product Soergel bimodules. The planar diagrams of our paper are two-dimensional encodings of these foams, essentially projections of the foams onto the yz-plane along the x-axis.It was shown in [32] that the action of the braid group on the homotopy category of Soergel bimodules extends to a (projective) action of the category of braid cobordisms. Thus, the homotopy category of 𝒟𝒞 produces invariants of braid cobordisms, so that our planar diagrammatics carry information about four-dimensional objects. This informational density indicates the efficiency of such encodings.Addendum 1.
Since this paper first appeared, the diagrammatics developed here have led to several developments which we briefly mention here. In [33] it is shown that Rouquier's braid group action lifts functorially to the braid cobordism category. In [34, 35], a functor is given from the category 𝒟𝒞 to categories of foams used in link homology. Together, these papers show that the encodings mentioned above are more than simply heuristic. In [36], the Temperley-Lieb algebra is categorified as a quotient of 𝒟𝒞. Additional statements relating this paper to either newer papers or to previous versions of this paper are found sparsely under a similar “Addendum” heading.


## 2. Preliminaries

Henceforth, we will fix a positive integern. Indices i, j, and k will range over 1,…,n if not otherwise specified. Finite ordered sequences of such indices (allowing repetition) will be denoted i̲=i1⋯id, as well as j̲ and k̲. The length of the sequence will be denoted d=d(i̲). For sequences of length d=1 where the single entry is i, we use i and i̲ interchangeably. Occasionally i+1 will also be used as an index, and whenever this occurs we make the tacit assumption that i≤n-1, so that all indices used remain between 1 and n. The same goes for i-1, i+2, and the like. We denote the length 0 sequence by the empty set symbol ∅.We work over a field𝕜, usually assuming that Char 𝕜≠2, and sometimes specializing it to 𝕔.Given a noetherian ringR, the category R-molf-R is the full subcategory of R-bimodules consisting of objects which are finitely generated as left R-modules. If R is graded, the category R-molfℤ-R is the analogous subcategory of graded R-bimodules and grading-preserving homomorphisms.


### 2.1. Hecke Algebra

Let(W,𝒮) be a Coxeter system of a finite Weyl group W, with length function l:W→𝕟={0,1,2,…}, and let e∈W be the identity. The Hecke algebra H is an algebra over ℤ[v,v-1] (we follow Soergel's use [37] of the variable v; related variables are denoted in the literature by t=v-1 and q=t2), which is free as a module with basis Tw,w∈W. Multiplication in this basis is given by TxTw=Txw when l(v)+l(w)=l(vw), and Ts2=(v-2-1)Ts+v-2Te for s∈𝒮. Te is the identity element in H and will often be written as 1.In the case we are interested in presently,W=Sn+1, and 𝒮 consists of the transpositions si=(i,i+1) for i=1,…,n. The element Tsi will be denoted Ti. The Hecke algebra has a presentation over ℤ[v,v-1], being generated by Ti subject to the relations (2.1)Ti2=(v-2-1)Ti+v-2,TiTj=TjTifor|i-j|≥2,TiTi+1Ti=Ti+1TiTi+1.
Clearly then, H is also generated as an algebra by bi=defCsi′=v(Ti+1), 1≤i≤n, and the relations above transform into(2.2)bi2=(v+v-1)bi,bibj=bjbifor|i-j|≥2,bibi+1bi+bi+1=bi+1bibi+1+bi.
We often write the monomial bi1bi2⋯bid as bi̲ where i̲=i1⋯id. Notice that b∅=1.Leta↦a¯ be the involution of ℤ[v,v-1] determined by v¯=v-1. It extends to an involution of H given by (2.3)∑awTw¯=∑aw¯Tw-1-1.
In particular, Ti¯=Ti-1=v2Ti+v2-1.Kazhdan and Lusztig [15] defined a pair of bases {Cw}w∈W and {Cw′}w∈W for H, which immediately proved to be of fundamental importance for representation theory and combinatorics. The two bases are related via a suitable involution of H, and the elements of the second Kazhdan-Lusztig basis {Cw′}w are determined by the two properties (2.4)Cw′¯=Cw′,Cw′=vl(w)∑y≤wPy,wTy,
where Py,w∈ℤ[v-2] has negative v-degree strictly less than l(w)-l(y) for y<w and Pw,w=1. There is no simple formula expressing Cw′ in terms of Ty, but observe that Ce′=1 and Csi′=bi=v(Ti+1). For a good introduction to the Kazhdan-Lusztig basis, see [37].Letε:H→ℤ[v,v-1] be the ℤ[v,v-1]-linear map given by ε(Te)=1 and ε(Tw)=0 if w≠e. Thus, ε simply picks up the coefficient of Te in x. The easily checked property ε(Tix)=ε(xTi) for any x∈H implies that ε(xy)=ε(yx), for all x,y∈H, so that ε is a trace map and turns H into a symmetric Frobenius ℤ[v,v-1]-algebra.Denote byω a v-antilinear anti-involution ω:H→H defined uniquely by ω(bi)=bi. The anti-involution and v-antilinearity conditions say that ω(xy)=ω(y)ω(x) and ω(ax)=a¯ω(x), for x,y∈H and a∈ℤ[v,v-1].Consider the pairing(,):H×H→ℤ[v,v-1] of ℤ-modules given by (2.5)(x,y)=ε(ω(x)y).It satisfies the following properties:(1)
the pairing issemi-linear, that is, (ax,y)=a¯(x,y) while (x,ay)=a(x,y), for a∈ℤ[v,v-1],(2)
bi is self-adjoint, that is, (x,biy)=(bix,y) and (x,ybi)=(xbi,y),(3)
ifi̲=i1⋯id with i1<i2<⋯<id then (1,bi̲)=vd. Such a monomial bi̲ is called an increasing monomial, and i̲ an increasing sequence. When d=0, the sequence i̲ is empty and (1,1)=1.Remark 2.1.
It is not difficult to observe that(,) is the unique form satisfying these three properties. This is because the Hecke algebra has a spanning set over ℤ[t,t-1] consisting of monomials bi̲, and every monomial may be reduced, by cycling the last bi to the beginning and by applying the Hecke algebra relations, to an increasing monomial. This is a simple combinatorial argument that we leave to the reader.


### 2.2. Soergel Bimodules

In [1], Soergel introduced a category of bimodules which categorified the Hecke algebra, and later generalized his construction to any Coxeter group W [14]. Within the category R-molfℤ-R, for R a certain graded 𝕜-algebra (𝕜 an infinite field of characteristic ≠2), he identified indecomposable modules Bw for w∈W, such that the only indecomposable summands of tensor products of Bw's are Bw′ for w′∈W. Thus, the subcategory of R-molfℤ-R generated additively by the Bw has a tensor product, and its Grothendieck ring is isomorphic to H, under the isomorphism sending Cs′ to [Bs]. Moreover, every Bw shows up as a summand of some tensor product of various Bs for s∈𝒮. While the general Bw may be difficult to describe, Bs has an easy description.It is conjectured in [14] that this isomorphism sends [Bw] to Cw′ for all w∈W, and it is proven for 𝕜=𝕔 and W a Weyl group in [1], using geometric methods.Henceforth we specialize to the case whereW=Sn+1 and 𝒮={si}. We also make one additional change from Soergel's conventions.Remark 2.2.
Soergel definesR to be the coordinate ring of the n-dimensional reflection representation V of Sn+1, while we find it easier to consider R′, the coordinate ring of the n+1-dimensional standard representation V′. This is akin to treating 𝔤𝔩n instead of 𝔰𝔩n, and a similar convention is adopted in [24]. The bimodules Bw are defined in [14] to be the coordinate rings of unions of “twisted diagonals” in V×V, and Bw′ can be defined analogously for V′. Now R′≅R⊗𝕜𝕜[y] and the entire story of Bw translates to Bw′ by base extension. Conversely, R is a quotient of R′ by the first elementary symmetric polynomial e1, which is a central element of our category, so that the entire story of Bw′ translates easily to Bw under the quotient. We will interest ourselves with the Bw′ story below because the ring R′ is slightly more intuitive, and mention briefly the changes required to deal with R in Section 4.6. Since we only use Bw′ and R′ below, we will denote them as Bw and R instead to avoid an apostrophe catastrophe.With these conventions, we now make the story explicit.Notation 2.3.
LetR=𝕜[x1,x2,…,xn+1] be the ring of polynomials in n+1 variables, with the natural action of Sn+1. The ring R is graded, with deg(xi)=2. If W is the subgroup of Sn+1 generated by transpositions {si1,…,sir}, then we denote the ring of invariants under W as Ri1,…,ir or RW. Thus Ri are the invariants under the transposition (i,i+1).SinceR is an RW-algebra, ⊗RW is a bifunctor sending two R-bimodules to an R-bimodule. Henceforth, ⊗ with no subscript denotes tensoring over R, while ⊗i1,…,ir denotes tensoring over the subring Ri1,…,ir. Most commonly we will just use ⊗i for various indices i.Definition 2.4.
The Soergel bimoduleBi is R⊗iR{-1}, where {m} denotes a grading shift.Notation 2.5.
We denote byBi̲ the tensor product Bi1⊗Bi2⊗⋯⊗Bid.Note thatB∅=R and(2.6)Bi̲=(R⊗i1R{-1})⊗(R⊗i2R{-1})⊗⋯=R⊗i1R⊗i2⋯⊗idR{-d}.
We reiterate this important point: a typical element of a tensor product of d generators Bi can be expressed (up to linear combination) by a choice of d+1 polynomials, one in each slot separated by the tensors. Multiplication by an element of R in any particular slot is an R-bimodule endomorphism.For eachi there is a map of graded vector spaces ∂i:R→Ri{2}, called the Demazure operator, sending f↦(f-si(f))/(xi-xi+1). This map is Ri-linear. Since ∂i(f) is si-invariant, it is not hard to see that Pi(f)=f-xi∂i(f) is also si-invariant. Since f=Pi(f)+xi∂i(f), this implies that R is a free graded Ri-module of rank two, with homogeneous generators 1 and xi. In other words, there is an isomorphism R≅Ri⊕Ri{2} of graded Ri-modules, sending f↦(Pi(f),∂i(f)), with inverse (f,g)↦f+gxi.From the isomorphismR≅Ri⊕Ri{2} of graded Ri-modules just illustrated, one can deduce other isomorphisms. For instance, Bi=R⊗iR{-1}≅R{-1}⊕R{1} as graded left (or right) R-modules. Repeating this, we see that Bi̲ is a free left R-module of rank 2d(i̲), and properly belongs in R-molfℤ-R. Finally, we can deduce an isomorphism Bi⊗iBi≅Bi{1}⊕Bi{-1}, which unlike the previous isomorphisms is actually an isomorphism of R-bimodules.Remark 2.6.
Let us make this slightly more explicit. To give the isomorphism of leftR-modules Bi≅R{-1}⊕R{1}, note that
(2.7)f⊗g=f⊗Pi(g)+f⊗xi∂i(g)=Pi(g)f⊗1+∂i(g)f⊗xi.
Rewriting a term 1⊗g as a sum of terms like above will happen often, and we refer to it as forcing the polynomial g across the tensor. If g is si-invariant then it may be slid across leaving nothing behind, while an arbitrary g when forced leaves terms with either 1 or xi behind (alternatively, we may choose to leave 1 and xi+1 behind, if it is more convenient). We consistently use the term “slide” instead of “force” when the polynomial g is invariant so it can be moved across without any ado.
InsideBi⊗Bi, taking an element f⊗g⊗h and forcing g to the left (or right) is now an R-bilinear operation, since multiplication on the left or right will only affect f or h, not g. This gives the isomorphism Bi⊗Bi≅Bi{1}⊕Bi{-1} of R-bimodules, via f⊗g⊗h↦(fPi(g)⊗h,f∂i(g)⊗h) with inverse (f1⊗h1,f2⊗h2)↦f1⊗1⊗h1+f2⊗xi⊗h2. These maps are R-bimodule morphisms, since the only polynomials which can slide from fi to hi in both the source and the target of the map are those polynomials in Ri.Remark 2.7.
We also remark on spanning sets forBi̲ as R-bimodules. For instance, we've seen that Bi⊗Bi has a spanning set {1⊗1⊗1,1⊗xi⊗1}. The bimodule Bi⊗Bj for j≠i has a spanning set {1⊗1⊗1}, since any polynomial in the middle can be forced to the left leaving at most xi behind (or xi+1, which we choose when j=i-1), and that can be slid to the right; thus 1⊗1⊗1 generates it as a R-bimodule. The bimodule Bi⊗Bj⊗Bk⊗Bi has a spanning set {1⊗1⊗1⊗1⊗1,1⊗xi⊗1⊗1⊗1}. This is because all polynomials anywhere between the two i tensors may be slid out, leaving xi somewhere in-between. As an exercise, the reader may generalize this argument to an arbitrary Bi̲ and find a spanning set as a R-bimodule, consisting of 2m(i̲) terms, where m(i̲) is the number of pairs 1≤r<s≤d such that ir=is and it≠is for t between r and s. Between such a pair, one either places a linear “unslideable” term like xir, or just 1. Note that  m(i̲) is equal to d(i̲) minus the number of distinct indices in i̲.For more information on Soergel bimodules and their applications we refer the reader to [1, 22, 24, 38–44] and references therein.


### 2.3. The Soergel Categorification

Let us summarize the Soergel categorification of the Hecke algebraH of the symmetric group Sn+1 and the various structures on it, following [1, 14, 22, 38, 41].Several subcategories ofR-molf-R and R-molfℤ-R will play a role in what follows. Let 𝒮𝒞1 be the full subcategory of R-molf-R whose objects consist of Bi̲ for all sequences of indices i̲; these are called Bott-Samelson bimodules. Since R is a commutative ring, the Hom spaces in 𝒮𝒞1 are in fact enriched in R-molfℤ-R. Let 𝒮𝒞2 be the subcategory of R-molfℤ-R whose objects are finite direct sums of various graded shifts of objects in 𝒮𝒞1 and the morphisms are all grading-preserving bimodule homomorphisms. Finally, let 𝒮𝒞 be the Karoubi envelope of 𝒮𝒞2, a category equivalent to the full subcategory of R-molfℤ-R which contains all summands of objects of 𝒮𝒞2(2.8)SC1→GradingshiftsanddirectsumsSC2→KaroubienvelopeSC.In general, the Karoubi envelope is the category which formally includes all “summands,” where a summand of an objectM is identified by an idempotent p∈End(M) corresponding to projection to that summand. Since R-molfℤ-R is abelian, it is idempotent-closed, and the Karoubi envelope of 𝒮𝒞2 can be realized as a subcategory in R-molfℤ-R. We refer the reader to [45] for basic information about Karoubi envelopes.This final category𝒮𝒞 (the category of Soergel bimodules) is a 𝕜-linear additive monoidal category with the Krull-Schmidt property. Soergel showed that, when 𝕜 is an infinite field of characteristic other than 2, the indecomposable bimodules in this category are enumerated by elements of the Weyl group and grading shifts (Theorem 6.16 in [14]). They are denoted by Bw{j} for w∈W and j∈ℤ. An indecomposable Bw is determined by the condition that it appears as a direct summand of Bi̲, where i̲=i1⋯id and si1⋯sid is a reduced presentation of w, and does not appear as direct summand of any Bi̲, for sequences i̲ of length less than l(w).The Hecke algebraH is canonically isomorphic to K0(𝒮𝒞), the Grothendieck group of 𝒮𝒞. Multiplication by v corresponds to the grading shift: [M{d}]=vd[M]. Multiplication in the Hecke algebra corresponds to the tensor product of bimodules: (2.9)[M]⋅[N]:=[M⊗RN].
The isomorphism takes [Bi] to bi and [Bi̲] to bi̲.Remark 2.8.
Nothing prevents one from defining a category𝒮𝒞ℤ where the field 𝕜 is replaced with ℤ in the definitions of the previous section. Thus one could define the category for any ring. However, one does not have control over the size of the Grothendieck group in this instance. When defined over a field 𝕜 of characteristic ≠2, we may use Theorem 6.16 of [14] to classify indecomposables and get results about the Grothendieck group. When 𝕜=𝕔, Soergel has shown that the Kazhdan-Lusztig basis {Cw′} satisfies Cw′=[Bw]. This is unknown in general.Relation (2.2) lifts to isomorphisms of graded bimodules in 𝒮𝒞(2.10)Bi⊗Bi≅Bi{1}⊕Bi{-1},(2.11)Bi⊗Bj≅Bj⊗Bifor|i-j|≥2,(2.12)(Bi⊗Bi+1⊗Bi)⊕Bi+1≅(Bi+1⊗Bi⊗Bi+1)⊕Bi.It is important to note that these isomorphisms take place in𝒮𝒞2, not 𝒮𝒞1, since the latter does not have grading shifts or direct sums of objects. However, the same information can be encapsulated in inclusion and projection morphisms of various degrees, which do live in 𝒮𝒞1. This will be explored in Section 4.5.The first isomorphism has already been made explicit in Remark2.6. We have chosen a specific isomorphism; other choices were possible. The second and third isomorphisms come from the following isomorphisms in R-molfℤ-R:(2.13)Bi⊗Bj≅R⊗i,jR{-2}≅Bj⊗Bifor|i-j|≥2,(2.14)Bi⊗Bi+1⊗Bi≅Bi⊕(R⊗i,i+1R{-3}),(2.15)Bi+1⊗Bi⊗Bi+1≅Bi+1⊕(R⊗i,i+1R{-3}).These isomorphisms will be made explicit in Section4.5.The ringℤ[v,v-1] is canonically isomorphic to the Grothendieck group of the category R-fmod of finitely generated graded free R-modules. Under this isomorphism (2.16)K0(R-fmod)≅Z[v,v-1][R] goes to 1 and [R{d}] to vd. In particular, given any graded free R-module M, its image in the Grothendieck group will be its graded rank, calculated by choosing a homogeneous R-basis {yj} of M and letting grkM=def∑jvdegyj. The bar involution on ℤ[v,v-1] lifts to the contravariant equivalence that takes M∈R-fmod to HomR(M,R), the latter naturally viewed as an R-module.In the category𝒮𝒞1, given any objects M,N, the space Hom𝒮𝒞1(M,N) is a graded free finitely generated left R-module. By extension, the same is true of the module ⊕m∈ℤHom𝒮𝒞(M{m},N). Shifting the grading of N will shift the grading of this Hom space in the same direction, while shifting M will shift the Hom space in the opposite direction. Therefore, the bifunctor (2.17)HomSC(⋅,⋅):SCop×SC⟶R-fmod
categorifies a semilinear form H×H→ℤ[v,v-1] which sends (2.18)([M],[N])⟼grk(⊕m∈ZHomSC(M{m},N)).The bimoduleBi self-biadjoint, that is, that Hom𝒮𝒞1(M⊗Bi,N)=Hom𝒮𝒞1(M,N⊗Bi) and Hom𝒮𝒞1(Bi⊗M,N)=Hom𝒮𝒞1(M,Bi⊗N) via some adjunction maps. This will become explicit in Section 3.1. In fact, every bimodule M in 𝒮𝒞 has a biadjoint bimodule Ω(M) such that tensoring with M on the left (resp., right) is biadjoint to tensoring with Ω(M) on the left (resp., right). Due to a cyclicity property (see the next section) any homomorphism f:M→N of bimodules dualizes to a canonical homomorphism Ω(f):Ω(N)→Ω(M), so that Ω can be made into an antiequivalence of 𝒮𝒞, lifting the anti-involution ω. Notice that Ω takes Bi to itself and Bi̲ to Bj̲ where j̲ is given by reading i̲ from right to left.Unsurprisingly, the semilinear product onH above (induced by the Hom bifunctor) agrees with the one defined in Section 2.1. To check this, following Remark 2.1 and using the self-biadjointness of Bi, we only need to show the following claim.Claim 2.9.
Wheni̲ is an increasing sequence, Hom𝒮𝒞1(R,Bi̲) is a free left R-module of rank 1, generated by a morphism of degree d, the length of i̲.Proof.
We only sketch this result. AnR-bimodule map from R to Bi is clearly determined by an element of Bi on which right and left multiplication by polynomials in R are identical. Any element of Bi is of the form m=f⊗1+g⊗xi, and clearly xjm=mxj for j≠i,i+1, and (xi+xi+1)m=m(xi+xi+1). Hence m can be the image of 1 under a bimodule map from R if and only if xim=mxi.
(2.19)mxi=f⊗xi+g⊗xi2=f⊗xi+g(xi+xi+1)⊗xi-g(xixi+1)⊗1.
Thus m can be an image if and only if g(xixi+1)=-fxi and f+g(xi+xi+1)=gxi, if and only if f=-gxi+1. Such elements form a left R-module generated by the case g=1, f=-xi+1, or in other words by m=1⊗xi-xi+1⊗1. The element m has degree 1 in Bi, so we deduce that (R,Bi)=v. Let us call φi the corresponding map R→Bi, 1↦m.
One may use the same argument for the general case. Supposei̲ is increasing and has length d, then Bi̲ is a free left R-module of degree 2d, with generators {1⊗iif1⋯⊗ikfk} ranging over terms where either fl=1 or fl=xil. As an exercise, the reader may find the criteria for a general element to be ad-invariant under xi, and verify that the only possible bimodule maps R→Bi̲ are R-multiples of the following iterated version of φi: (2.20)R⟶Bi1≅Bi1⊗R⟶Bi1⊗Bi2≅⋯.
The first map is φi1, the second map is Id⊗φi2, and so forth. This generator is a map of degree d, so that Hom𝒮𝒞1(R,Bi̲)=R{d} and ([R],[Bi̲])=vd.Remark 2.10.
We have swept the calculation under the rug, so the dependence of this claim on the fact thati̲ is increasing is unclear. In general, when i̲ has a repeated index there will be additional maps from R to Bi̲. Roughly speaking, certain symmetry conditions are placed upon polynomials in order for them to slide across certain tensors. The duplication of an index will yield a redundant symmetry condition that places fewer constraints on an ad-invariant element than would be expected from the length of the sequence. We suggest the reader try to find all the maps from R to Bi̲ in the length 2 case, first when i̲=ij has no repeated index and then when i̲=ii has a repeated index. This should illustrate the main idea.Because it is a crucial statement which we use again and again, we restate the overall result and give a reference.Proposition 2.11.
Given two sequencesi̲ and j̲, Hom𝒮𝒞(Bi̲,Bj̲) is a free graded left (or right) R-module of rank ε(ω(bi̲)bj̲), where ε is the standard trace on H defined in Section 2.1.Proof.
This is deduced from the above discussion. For Soergel's proof, see [14], although it is somewhat obscured. Theorem 5.15 in that paper and especially its proof together state this result, once one unravels exactly what hΔ means. Propositions 5.7 and 5.9 state that hΔ(Bi̲)=bi̲, since hΔ sends Bi⊗· to bi· and sends R to 1.The facts below will not be used in this paper.For a Soergel bimoduleM the space of bimodule homomorphisms Hom𝒮𝒞1(R,M) is just the 0th Hochschild cohomology HH0(R,M) of M. Thus, unraveling the definitions, (2.21)ε([M]):=grk(HH0(R,M)).
Calculations in Hochschild cohomology can be used to provide a proof of the claim above. One could also define a trace map τ(x)=ε(ω(x))¯ which is the decategorification of the functor HH0 of taking the 0th Hochschild homology.Hecke algebraH has a trace more sophisticated than ε or τ, called the Ocneanu trace [46], which describes the HOMFLY-PT polynomial. The categorification of the Ocneanu trace utilizes all Hochschild homology groups rather than just HH0, see [24, 43, 47].The Rouquier complexes mentioned in the introduction are described here. Invertible elementsTi that satisfy the braid relations become [22] invertible complexes (2.22)0⟶R⟶Bi{-1}⟶0,
in the homotopy category of the Soergel category (with R sitting in cohomological degree −1). This aligns with the fact that Ti=v-1bi-1 in the Hecke quotient of the braid group. Their inverses Ti-1 become inverse complexes (2.23)0⟶Bi{1}⟶R⟶0,
with R in cohomological degree 1, agreeing with Ti-1=vbi-1. The homomorphism from the braid group into the Hecke algebra is categorified by a projective functor from the category of braid cobordisms between (n+1)-stranded braids to the category of endofunctors of the homotopy category of the Soergel category [32].Remark 2.12.
Note that this convention for Rouquier complexes is opposite that found in [22], which is to say that we have flipped Ti with Ti-1. Presumably this arises because we are using v as a parameter for the grading shift, and not t=v-1. The choice of v is more natural for the calculation of graded ranks of Hom spaces.


### 2.4. Diagrammatic Calculus for Bimodule Maps

We follow the standard rules for the diagrammatic calculus of bimodules, or more generally for the diagrammatic calculus of a monoidal category. An excellent and thorough explanation of these rules can be found in [9], so we will provide a quick summary. A planar diagram will represent a morphism of R-bimodules, with the following conventions. A horizontal slice or line segment in this diagram will represent an object (an R-bimodule). A rectangle inside the plane will represent a morphism from its bottom horizontal line segment to its top horizontal line segment.TheR-bimodule Bi is denoted by a point (on a horizontal line segment) labelled i. The tensor product of bimodules is depicted by a sequence of labelled points on a horizontal line segment, so that tensor products are formed “horizontally”. A vertical line labelled i denotes the identity endomorphism of Bi, and similarly labelled lines placed side by side denote the identity endomorphism of the tensor product. More general bimodule maps are represented by some symbols connecting the appropriate lines, and are composed “vertically”, and tensored “horizontally”. All diagrams are read from bottom to top, so that the following diagram represents a bimodule map from Bk to Bi⊗Bi⊗Bj:A horizontal line segment which does not contain any marked points representsR as a bimodule over itself, the monoidal identity. The empty rectangle represents the identity endomorphism of R. Planar diagrams without top and bottom endpoints (without boundary) represent more general endomorphisms of R.The structure of bimodule categories (or more generally strict 2-categories) guarantees that a planar diagram will unambiguously denote a morphism of bimodules.We will be using so many such pictures that it will become cumbersome to continuously label each line by an index. Generally, the calculations we do will work independently for eachi, and can be expressed with diagrams that use lines labelled i, i+1 and the like. In these circumstances, when there is no ambiguity, we will fix an index i and draw a line labelled i with one style, a line labelled i+1 with a different style, and so forth, maintaining the same conventions throughout the paper. We use different styles of lines because most printers are black and white, but we recommend that you do your calculations at home in colored pen or pencils instead; we even refer to the labels as “colors” throughout this paper.We use the styles above when referring to indicesi, i+1, i-1, and j, where j will be used unambiguously for any index which is “far away” from any other indices in the picture (in other words, when drawing a picture only involving i-colored strands, we require |i-j|>1, while for a picture involving both i and i+1 we require j<i-1 or j>i+2).


### 2.5. Methodology

Proposition 2.13.
Suppose one chooses the subset of the morphisms in𝒮𝒞1, including the identity morphism of each object, as well as the following morphisms: (1)
the generating morphism fromR to Bi,(2)
some isomorphisms that yield the Hecke algebra relations, as well as the respective projections to and inclusions from each summand in (2.10) and (2.12),(3)
the unit and counit of adjunction that makeBi into a self-biadjoint bimodule.
Consider𝒞 the subcategory generated monoidally over the left action of R by these morphisms, that is, it includes left R-linear combinations, compositions, and tensors of all its morphisms, then 𝒞 is a full subcategory, and thus it is actually 𝒮𝒞1.Proof.
For any objectsM,N in 𝒮𝒞1, there is an inclusion Hom𝒞(M,N)⊂Hom𝒮𝒞1(M,N) of graded left R-modules (since it is clearly an inclusion of R-modules, and all generating morphisms are homogeneous). One can define grk for any graded left R-module M by choosing generators of M/(R+M), where R+ is the ideal of positively graded elements, and it is a simple argument that a submodule of a free graded R-module with the same graded rank is in fact the entire module. So we need only show that Hom spaces in 𝒞 have the same graded rank.
We can define a semilinear form on the freeℤ[v,v-1]-algebra generated by bi by the formula (bi̲,bj̲)=grkHom𝒞(Bi̲,Bj̲). The existence of isomorphisms and projection maps will give us the direct sum decompositions (2.10)–(2.12) in 𝒞, with the resulting implications for Hom spaces. Therefore the Hecke algebra relation (2.2) are in the kernel of this semilinear form, so it descends to a form on the Hecke algebra. Each bi will be self-adjoint. When i̲ is increasing, Hom𝒞(R,Bi̲) contains the generator of the free rank one R-module Hom𝒮𝒞1(R,Bi̲), since that generator is the tensor of the generating morphisms from R to various Bi (see the proof of Claim 2.9). Hence it is in fact the entire module, so Hom𝒞(R,Bi̲)≅R{d}, and (1,bi̲)=vd.
By unicity, this inner product agrees with our earlier inner product on the Hecke algebra. In particular, the graded ranks agree, and the inclusion is full.Below we will construct a category𝒟𝒞1 of diagrams via generators and local relations, where the Hom spaces will be graded R-bimodules. We will construct a functor F1 from 𝒟𝒞1 to 𝒮𝒞1, showing that our diagrams give graphical presentation of morphisms in 𝒮𝒞1. The morphisms in the image of F1 will include all the morphisms enumerated in Proposition 2.13, hence the functor will be full. Calculating the Hom spaces in 𝒟𝒞1 between certain objects (corresponding to R, Bi̲ for i̲ increasing), we may use a similar argument to the above proposition to show that they are free R-modules of the same graded rank as the Hom spaces in 𝒮𝒞1, then the functor F1 will be faithful, and an equivalence of categories. This describes 𝒮𝒞1 in terms of generators and relations.Let𝒟𝒞2 be the category whose objects are finite direct sums of formal grading shifts of objects in 𝒟𝒞1, but whose morphisms only include degree 0 maps. Finally, let 𝒟𝒞=Kar(𝒟𝒞2) be the Karoubi envelope of 𝒟𝒞2. The functor F1 lifts to functors F2 and F, as in the picture below, with all three horizontal arrows being equivalences of categories.(2.24)We will define the category𝒟𝒞1 originally without reference to isotopy, in order to make the definition of the functor F1 entirely straightforward, using the standard rules for diagrammatics for bimodules. The category would be entirely unchanged if one used different pictures to represent each morphism. However, when the “correct” pictures are chosen for the generators, then every morphism can actually be viewed as a planar graph, and moreover two embedded graphs linked by isotopy represent the same morphism. One could very well define 𝒟𝒞1 originally using graphs, but this would obscure the definition of F1.The most difficult part of the proof will be showing the faithfulness ofF1, which involves a calculation of certain Hom spaces in the diagrammatic category. This calculation will be made possible by the planar graphs interpretation of 𝒟𝒞1, wherein some relatively simple graph theory can be applied to simplify pictures.


## 2.1. Hecke Algebra

Let(W,𝒮) be a Coxeter system of a finite Weyl group W, with length function l:W→𝕟={0,1,2,…}, and let e∈W be the identity. The Hecke algebra H is an algebra over ℤ[v,v-1] (we follow Soergel's use [37] of the variable v; related variables are denoted in the literature by t=v-1 and q=t2), which is free as a module with basis Tw,w∈W. Multiplication in this basis is given by TxTw=Txw when l(v)+l(w)=l(vw), and Ts2=(v-2-1)Ts+v-2Te for s∈𝒮. Te is the identity element in H and will often be written as 1.In the case we are interested in presently,W=Sn+1, and 𝒮 consists of the transpositions si=(i,i+1) for i=1,…,n. The element Tsi will be denoted Ti. The Hecke algebra has a presentation over ℤ[v,v-1], being generated by Ti subject to the relations (2.1)Ti2=(v-2-1)Ti+v-2,TiTj=TjTifor|i-j|≥2,TiTi+1Ti=Ti+1TiTi+1.
Clearly then, H is also generated as an algebra by bi=defCsi′=v(Ti+1), 1≤i≤n, and the relations above transform into(2.2)bi2=(v+v-1)bi,bibj=bjbifor|i-j|≥2,bibi+1bi+bi+1=bi+1bibi+1+bi.
We often write the monomial bi1bi2⋯bid as bi̲ where i̲=i1⋯id. Notice that b∅=1.Leta↦a¯ be the involution of ℤ[v,v-1] determined by v¯=v-1. It extends to an involution of H given by (2.3)∑awTw¯=∑aw¯Tw-1-1.
In particular, Ti¯=Ti-1=v2Ti+v2-1.Kazhdan and Lusztig [15] defined a pair of bases {Cw}w∈W and {Cw′}w∈W for H, which immediately proved to be of fundamental importance for representation theory and combinatorics. The two bases are related via a suitable involution of H, and the elements of the second Kazhdan-Lusztig basis {Cw′}w are determined by the two properties (2.4)Cw′¯=Cw′,Cw′=vl(w)∑y≤wPy,wTy,
where Py,w∈ℤ[v-2] has negative v-degree strictly less than l(w)-l(y) for y<w and Pw,w=1. There is no simple formula expressing Cw′ in terms of Ty, but observe that Ce′=1 and Csi′=bi=v(Ti+1). For a good introduction to the Kazhdan-Lusztig basis, see [37].Letε:H→ℤ[v,v-1] be the ℤ[v,v-1]-linear map given by ε(Te)=1 and ε(Tw)=0 if w≠e. Thus, ε simply picks up the coefficient of Te in x. The easily checked property ε(Tix)=ε(xTi) for any x∈H implies that ε(xy)=ε(yx), for all x,y∈H, so that ε is a trace map and turns H into a symmetric Frobenius ℤ[v,v-1]-algebra.Denote byω a v-antilinear anti-involution ω:H→H defined uniquely by ω(bi)=bi. The anti-involution and v-antilinearity conditions say that ω(xy)=ω(y)ω(x) and ω(ax)=a¯ω(x), for x,y∈H and a∈ℤ[v,v-1].Consider the pairing(,):H×H→ℤ[v,v-1] of ℤ-modules given by (2.5)(x,y)=ε(ω(x)y).It satisfies the following properties:(1)
the pairing issemi-linear, that is, (ax,y)=a¯(x,y) while (x,ay)=a(x,y), for a∈ℤ[v,v-1],(2)
bi is self-adjoint, that is, (x,biy)=(bix,y) and (x,ybi)=(xbi,y),(3)
ifi̲=i1⋯id with i1<i2<⋯<id then (1,bi̲)=vd. Such a monomial bi̲ is called an increasing monomial, and i̲ an increasing sequence. When d=0, the sequence i̲ is empty and (1,1)=1.Remark 2.1.
It is not difficult to observe that(,) is the unique form satisfying these three properties. This is because the Hecke algebra has a spanning set over ℤ[t,t-1] consisting of monomials bi̲, and every monomial may be reduced, by cycling the last bi to the beginning and by applying the Hecke algebra relations, to an increasing monomial. This is a simple combinatorial argument that we leave to the reader.


## 2.2. Soergel Bimodules

In [1], Soergel introduced a category of bimodules which categorified the Hecke algebra, and later generalized his construction to any Coxeter group W [14]. Within the category R-molfℤ-R, for R a certain graded 𝕜-algebra (𝕜 an infinite field of characteristic ≠2), he identified indecomposable modules Bw for w∈W, such that the only indecomposable summands of tensor products of Bw's are Bw′ for w′∈W. Thus, the subcategory of R-molfℤ-R generated additively by the Bw has a tensor product, and its Grothendieck ring is isomorphic to H, under the isomorphism sending Cs′ to [Bs]. Moreover, every Bw shows up as a summand of some tensor product of various Bs for s∈𝒮. While the general Bw may be difficult to describe, Bs has an easy description.It is conjectured in [14] that this isomorphism sends [Bw] to Cw′ for all w∈W, and it is proven for 𝕜=𝕔 and W a Weyl group in [1], using geometric methods.Henceforth we specialize to the case whereW=Sn+1 and 𝒮={si}. We also make one additional change from Soergel's conventions.Remark 2.2.
Soergel definesR to be the coordinate ring of the n-dimensional reflection representation V of Sn+1, while we find it easier to consider R′, the coordinate ring of the n+1-dimensional standard representation V′. This is akin to treating 𝔤𝔩n instead of 𝔰𝔩n, and a similar convention is adopted in [24]. The bimodules Bw are defined in [14] to be the coordinate rings of unions of “twisted diagonals” in V×V, and Bw′ can be defined analogously for V′. Now R′≅R⊗𝕜𝕜[y] and the entire story of Bw translates to Bw′ by base extension. Conversely, R is a quotient of R′ by the first elementary symmetric polynomial e1, which is a central element of our category, so that the entire story of Bw′ translates easily to Bw under the quotient. We will interest ourselves with the Bw′ story below because the ring R′ is slightly more intuitive, and mention briefly the changes required to deal with R in Section 4.6. Since we only use Bw′ and R′ below, we will denote them as Bw and R instead to avoid an apostrophe catastrophe.With these conventions, we now make the story explicit.Notation 2.3.
LetR=𝕜[x1,x2,…,xn+1] be the ring of polynomials in n+1 variables, with the natural action of Sn+1. The ring R is graded, with deg(xi)=2. If W is the subgroup of Sn+1 generated by transpositions {si1,…,sir}, then we denote the ring of invariants under W as Ri1,…,ir or RW. Thus Ri are the invariants under the transposition (i,i+1).SinceR is an RW-algebra, ⊗RW is a bifunctor sending two R-bimodules to an R-bimodule. Henceforth, ⊗ with no subscript denotes tensoring over R, while ⊗i1,…,ir denotes tensoring over the subring Ri1,…,ir. Most commonly we will just use ⊗i for various indices i.Definition 2.4.
The Soergel bimoduleBi is R⊗iR{-1}, where {m} denotes a grading shift.Notation 2.5.
We denote byBi̲ the tensor product Bi1⊗Bi2⊗⋯⊗Bid.Note thatB∅=R and(2.6)Bi̲=(R⊗i1R{-1})⊗(R⊗i2R{-1})⊗⋯=R⊗i1R⊗i2⋯⊗idR{-d}.
We reiterate this important point: a typical element of a tensor product of d generators Bi can be expressed (up to linear combination) by a choice of d+1 polynomials, one in each slot separated by the tensors. Multiplication by an element of R in any particular slot is an R-bimodule endomorphism.For eachi there is a map of graded vector spaces ∂i:R→Ri{2}, called the Demazure operator, sending f↦(f-si(f))/(xi-xi+1). This map is Ri-linear. Since ∂i(f) is si-invariant, it is not hard to see that Pi(f)=f-xi∂i(f) is also si-invariant. Since f=Pi(f)+xi∂i(f), this implies that R is a free graded Ri-module of rank two, with homogeneous generators 1 and xi. In other words, there is an isomorphism R≅Ri⊕Ri{2} of graded Ri-modules, sending f↦(Pi(f),∂i(f)), with inverse (f,g)↦f+gxi.From the isomorphismR≅Ri⊕Ri{2} of graded Ri-modules just illustrated, one can deduce other isomorphisms. For instance, Bi=R⊗iR{-1}≅R{-1}⊕R{1} as graded left (or right) R-modules. Repeating this, we see that Bi̲ is a free left R-module of rank 2d(i̲), and properly belongs in R-molfℤ-R. Finally, we can deduce an isomorphism Bi⊗iBi≅Bi{1}⊕Bi{-1}, which unlike the previous isomorphisms is actually an isomorphism of R-bimodules.Remark 2.6.
Let us make this slightly more explicit. To give the isomorphism of leftR-modules Bi≅R{-1}⊕R{1}, note that
(2.7)f⊗g=f⊗Pi(g)+f⊗xi∂i(g)=Pi(g)f⊗1+∂i(g)f⊗xi.
Rewriting a term 1⊗g as a sum of terms like above will happen often, and we refer to it as forcing the polynomial g across the tensor. If g is si-invariant then it may be slid across leaving nothing behind, while an arbitrary g when forced leaves terms with either 1 or xi behind (alternatively, we may choose to leave 1 and xi+1 behind, if it is more convenient). We consistently use the term “slide” instead of “force” when the polynomial g is invariant so it can be moved across without any ado.
InsideBi⊗Bi, taking an element f⊗g⊗h and forcing g to the left (or right) is now an R-bilinear operation, since multiplication on the left or right will only affect f or h, not g. This gives the isomorphism Bi⊗Bi≅Bi{1}⊕Bi{-1} of R-bimodules, via f⊗g⊗h↦(fPi(g)⊗h,f∂i(g)⊗h) with inverse (f1⊗h1,f2⊗h2)↦f1⊗1⊗h1+f2⊗xi⊗h2. These maps are R-bimodule morphisms, since the only polynomials which can slide from fi to hi in both the source and the target of the map are those polynomials in Ri.Remark 2.7.
We also remark on spanning sets forBi̲ as R-bimodules. For instance, we've seen that Bi⊗Bi has a spanning set {1⊗1⊗1,1⊗xi⊗1}. The bimodule Bi⊗Bj for j≠i has a spanning set {1⊗1⊗1}, since any polynomial in the middle can be forced to the left leaving at most xi behind (or xi+1, which we choose when j=i-1), and that can be slid to the right; thus 1⊗1⊗1 generates it as a R-bimodule. The bimodule Bi⊗Bj⊗Bk⊗Bi has a spanning set {1⊗1⊗1⊗1⊗1,1⊗xi⊗1⊗1⊗1}. This is because all polynomials anywhere between the two i tensors may be slid out, leaving xi somewhere in-between. As an exercise, the reader may generalize this argument to an arbitrary Bi̲ and find a spanning set as a R-bimodule, consisting of 2m(i̲) terms, where m(i̲) is the number of pairs 1≤r<s≤d such that ir=is and it≠is for t between r and s. Between such a pair, one either places a linear “unslideable” term like xir, or just 1. Note that  m(i̲) is equal to d(i̲) minus the number of distinct indices in i̲.For more information on Soergel bimodules and their applications we refer the reader to [1, 22, 24, 38–44] and references therein.


## 2.3. The Soergel Categorification

Let us summarize the Soergel categorification of the Hecke algebraH of the symmetric group Sn+1 and the various structures on it, following [1, 14, 22, 38, 41].Several subcategories ofR-molf-R and R-molfℤ-R will play a role in what follows. Let 𝒮𝒞1 be the full subcategory of R-molf-R whose objects consist of Bi̲ for all sequences of indices i̲; these are called Bott-Samelson bimodules. Since R is a commutative ring, the Hom spaces in 𝒮𝒞1 are in fact enriched in R-molfℤ-R. Let 𝒮𝒞2 be the subcategory of R-molfℤ-R whose objects are finite direct sums of various graded shifts of objects in 𝒮𝒞1 and the morphisms are all grading-preserving bimodule homomorphisms. Finally, let 𝒮𝒞 be the Karoubi envelope of 𝒮𝒞2, a category equivalent to the full subcategory of R-molfℤ-R which contains all summands of objects of 𝒮𝒞2(2.8)SC1→GradingshiftsanddirectsumsSC2→KaroubienvelopeSC.In general, the Karoubi envelope is the category which formally includes all “summands,” where a summand of an objectM is identified by an idempotent p∈End(M) corresponding to projection to that summand. Since R-molfℤ-R is abelian, it is idempotent-closed, and the Karoubi envelope of 𝒮𝒞2 can be realized as a subcategory in R-molfℤ-R. We refer the reader to [45] for basic information about Karoubi envelopes.This final category𝒮𝒞 (the category of Soergel bimodules) is a 𝕜-linear additive monoidal category with the Krull-Schmidt property. Soergel showed that, when 𝕜 is an infinite field of characteristic other than 2, the indecomposable bimodules in this category are enumerated by elements of the Weyl group and grading shifts (Theorem 6.16 in [14]). They are denoted by Bw{j} for w∈W and j∈ℤ. An indecomposable Bw is determined by the condition that it appears as a direct summand of Bi̲, where i̲=i1⋯id and si1⋯sid is a reduced presentation of w, and does not appear as direct summand of any Bi̲, for sequences i̲ of length less than l(w).The Hecke algebraH is canonically isomorphic to K0(𝒮𝒞), the Grothendieck group of 𝒮𝒞. Multiplication by v corresponds to the grading shift: [M{d}]=vd[M]. Multiplication in the Hecke algebra corresponds to the tensor product of bimodules: (2.9)[M]⋅[N]:=[M⊗RN].
The isomorphism takes [Bi] to bi and [Bi̲] to bi̲.Remark 2.8.
Nothing prevents one from defining a category𝒮𝒞ℤ where the field 𝕜 is replaced with ℤ in the definitions of the previous section. Thus one could define the category for any ring. However, one does not have control over the size of the Grothendieck group in this instance. When defined over a field 𝕜 of characteristic ≠2, we may use Theorem 6.16 of [14] to classify indecomposables and get results about the Grothendieck group. When 𝕜=𝕔, Soergel has shown that the Kazhdan-Lusztig basis {Cw′} satisfies Cw′=[Bw]. This is unknown in general.Relation (2.2) lifts to isomorphisms of graded bimodules in 𝒮𝒞(2.10)Bi⊗Bi≅Bi{1}⊕Bi{-1},(2.11)Bi⊗Bj≅Bj⊗Bifor|i-j|≥2,(2.12)(Bi⊗Bi+1⊗Bi)⊕Bi+1≅(Bi+1⊗Bi⊗Bi+1)⊕Bi.It is important to note that these isomorphisms take place in𝒮𝒞2, not 𝒮𝒞1, since the latter does not have grading shifts or direct sums of objects. However, the same information can be encapsulated in inclusion and projection morphisms of various degrees, which do live in 𝒮𝒞1. This will be explored in Section 4.5.The first isomorphism has already been made explicit in Remark2.6. We have chosen a specific isomorphism; other choices were possible. The second and third isomorphisms come from the following isomorphisms in R-molfℤ-R:(2.13)Bi⊗Bj≅R⊗i,jR{-2}≅Bj⊗Bifor|i-j|≥2,(2.14)Bi⊗Bi+1⊗Bi≅Bi⊕(R⊗i,i+1R{-3}),(2.15)Bi+1⊗Bi⊗Bi+1≅Bi+1⊕(R⊗i,i+1R{-3}).These isomorphisms will be made explicit in Section4.5.The ringℤ[v,v-1] is canonically isomorphic to the Grothendieck group of the category R-fmod of finitely generated graded free R-modules. Under this isomorphism (2.16)K0(R-fmod)≅Z[v,v-1][R] goes to 1 and [R{d}] to vd. In particular, given any graded free R-module M, its image in the Grothendieck group will be its graded rank, calculated by choosing a homogeneous R-basis {yj} of M and letting grkM=def∑jvdegyj. The bar involution on ℤ[v,v-1] lifts to the contravariant equivalence that takes M∈R-fmod to HomR(M,R), the latter naturally viewed as an R-module.In the category𝒮𝒞1, given any objects M,N, the space Hom𝒮𝒞1(M,N) is a graded free finitely generated left R-module. By extension, the same is true of the module ⊕m∈ℤHom𝒮𝒞(M{m},N). Shifting the grading of N will shift the grading of this Hom space in the same direction, while shifting M will shift the Hom space in the opposite direction. Therefore, the bifunctor (2.17)HomSC(⋅,⋅):SCop×SC⟶R-fmod
categorifies a semilinear form H×H→ℤ[v,v-1] which sends (2.18)([M],[N])⟼grk(⊕m∈ZHomSC(M{m},N)).The bimoduleBi self-biadjoint, that is, that Hom𝒮𝒞1(M⊗Bi,N)=Hom𝒮𝒞1(M,N⊗Bi) and Hom𝒮𝒞1(Bi⊗M,N)=Hom𝒮𝒞1(M,Bi⊗N) via some adjunction maps. This will become explicit in Section 3.1. In fact, every bimodule M in 𝒮𝒞 has a biadjoint bimodule Ω(M) such that tensoring with M on the left (resp., right) is biadjoint to tensoring with Ω(M) on the left (resp., right). Due to a cyclicity property (see the next section) any homomorphism f:M→N of bimodules dualizes to a canonical homomorphism Ω(f):Ω(N)→Ω(M), so that Ω can be made into an antiequivalence of 𝒮𝒞, lifting the anti-involution ω. Notice that Ω takes Bi to itself and Bi̲ to Bj̲ where j̲ is given by reading i̲ from right to left.Unsurprisingly, the semilinear product onH above (induced by the Hom bifunctor) agrees with the one defined in Section 2.1. To check this, following Remark 2.1 and using the self-biadjointness of Bi, we only need to show the following claim.Claim 2.9.
Wheni̲ is an increasing sequence, Hom𝒮𝒞1(R,Bi̲) is a free left R-module of rank 1, generated by a morphism of degree d, the length of i̲.Proof.
We only sketch this result. AnR-bimodule map from R to Bi is clearly determined by an element of Bi on which right and left multiplication by polynomials in R are identical. Any element of Bi is of the form m=f⊗1+g⊗xi, and clearly xjm=mxj for j≠i,i+1, and (xi+xi+1)m=m(xi+xi+1). Hence m can be the image of 1 under a bimodule map from R if and only if xim=mxi.
(2.19)mxi=f⊗xi+g⊗xi2=f⊗xi+g(xi+xi+1)⊗xi-g(xixi+1)⊗1.
Thus m can be an image if and only if g(xixi+1)=-fxi and f+g(xi+xi+1)=gxi, if and only if f=-gxi+1. Such elements form a left R-module generated by the case g=1, f=-xi+1, or in other words by m=1⊗xi-xi+1⊗1. The element m has degree 1 in Bi, so we deduce that (R,Bi)=v. Let us call φi the corresponding map R→Bi, 1↦m.
One may use the same argument for the general case. Supposei̲ is increasing and has length d, then Bi̲ is a free left R-module of degree 2d, with generators {1⊗iif1⋯⊗ikfk} ranging over terms where either fl=1 or fl=xil. As an exercise, the reader may find the criteria for a general element to be ad-invariant under xi, and verify that the only possible bimodule maps R→Bi̲ are R-multiples of the following iterated version of φi: (2.20)R⟶Bi1≅Bi1⊗R⟶Bi1⊗Bi2≅⋯.
The first map is φi1, the second map is Id⊗φi2, and so forth. This generator is a map of degree d, so that Hom𝒮𝒞1(R,Bi̲)=R{d} and ([R],[Bi̲])=vd.Remark 2.10.
We have swept the calculation under the rug, so the dependence of this claim on the fact thati̲ is increasing is unclear. In general, when i̲ has a repeated index there will be additional maps from R to Bi̲. Roughly speaking, certain symmetry conditions are placed upon polynomials in order for them to slide across certain tensors. The duplication of an index will yield a redundant symmetry condition that places fewer constraints on an ad-invariant element than would be expected from the length of the sequence. We suggest the reader try to find all the maps from R to Bi̲ in the length 2 case, first when i̲=ij has no repeated index and then when i̲=ii has a repeated index. This should illustrate the main idea.Because it is a crucial statement which we use again and again, we restate the overall result and give a reference.Proposition 2.11.
Given two sequencesi̲ and j̲, Hom𝒮𝒞(Bi̲,Bj̲) is a free graded left (or right) R-module of rank ε(ω(bi̲)bj̲), where ε is the standard trace on H defined in Section 2.1.Proof.
This is deduced from the above discussion. For Soergel's proof, see [14], although it is somewhat obscured. Theorem 5.15 in that paper and especially its proof together state this result, once one unravels exactly what hΔ means. Propositions 5.7 and 5.9 state that hΔ(Bi̲)=bi̲, since hΔ sends Bi⊗· to bi· and sends R to 1.The facts below will not be used in this paper.For a Soergel bimoduleM the space of bimodule homomorphisms Hom𝒮𝒞1(R,M) is just the 0th Hochschild cohomology HH0(R,M) of M. Thus, unraveling the definitions, (2.21)ε([M]):=grk(HH0(R,M)).
Calculations in Hochschild cohomology can be used to provide a proof of the claim above. One could also define a trace map τ(x)=ε(ω(x))¯ which is the decategorification of the functor HH0 of taking the 0th Hochschild homology.Hecke algebraH has a trace more sophisticated than ε or τ, called the Ocneanu trace [46], which describes the HOMFLY-PT polynomial. The categorification of the Ocneanu trace utilizes all Hochschild homology groups rather than just HH0, see [24, 43, 47].The Rouquier complexes mentioned in the introduction are described here. Invertible elementsTi that satisfy the braid relations become [22] invertible complexes (2.22)0⟶R⟶Bi{-1}⟶0,
in the homotopy category of the Soergel category (with R sitting in cohomological degree −1). This aligns with the fact that Ti=v-1bi-1 in the Hecke quotient of the braid group. Their inverses Ti-1 become inverse complexes (2.23)0⟶Bi{1}⟶R⟶0,
with R in cohomological degree 1, agreeing with Ti-1=vbi-1. The homomorphism from the braid group into the Hecke algebra is categorified by a projective functor from the category of braid cobordisms between (n+1)-stranded braids to the category of endofunctors of the homotopy category of the Soergel category [32].Remark 2.12.
Note that this convention for Rouquier complexes is opposite that found in [22], which is to say that we have flipped Ti with Ti-1. Presumably this arises because we are using v as a parameter for the grading shift, and not t=v-1. The choice of v is more natural for the calculation of graded ranks of Hom spaces.


## 2.4. Diagrammatic Calculus for Bimodule Maps

We follow the standard rules for the diagrammatic calculus of bimodules, or more generally for the diagrammatic calculus of a monoidal category. An excellent and thorough explanation of these rules can be found in [9], so we will provide a quick summary. A planar diagram will represent a morphism of R-bimodules, with the following conventions. A horizontal slice or line segment in this diagram will represent an object (an R-bimodule). A rectangle inside the plane will represent a morphism from its bottom horizontal line segment to its top horizontal line segment.TheR-bimodule Bi is denoted by a point (on a horizontal line segment) labelled i. The tensor product of bimodules is depicted by a sequence of labelled points on a horizontal line segment, so that tensor products are formed “horizontally”. A vertical line labelled i denotes the identity endomorphism of Bi, and similarly labelled lines placed side by side denote the identity endomorphism of the tensor product. More general bimodule maps are represented by some symbols connecting the appropriate lines, and are composed “vertically”, and tensored “horizontally”. All diagrams are read from bottom to top, so that the following diagram represents a bimodule map from Bk to Bi⊗Bi⊗Bj:A horizontal line segment which does not contain any marked points representsR as a bimodule over itself, the monoidal identity. The empty rectangle represents the identity endomorphism of R. Planar diagrams without top and bottom endpoints (without boundary) represent more general endomorphisms of R.The structure of bimodule categories (or more generally strict 2-categories) guarantees that a planar diagram will unambiguously denote a morphism of bimodules.We will be using so many such pictures that it will become cumbersome to continuously label each line by an index. Generally, the calculations we do will work independently for eachi, and can be expressed with diagrams that use lines labelled i, i+1 and the like. In these circumstances, when there is no ambiguity, we will fix an index i and draw a line labelled i with one style, a line labelled i+1 with a different style, and so forth, maintaining the same conventions throughout the paper. We use different styles of lines because most printers are black and white, but we recommend that you do your calculations at home in colored pen or pencils instead; we even refer to the labels as “colors” throughout this paper.We use the styles above when referring to indicesi, i+1, i-1, and j, where j will be used unambiguously for any index which is “far away” from any other indices in the picture (in other words, when drawing a picture only involving i-colored strands, we require |i-j|>1, while for a picture involving both i and i+1 we require j<i-1 or j>i+2).


## 2.5. Methodology

Proposition 2.13.
Suppose one chooses the subset of the morphisms in𝒮𝒞1, including the identity morphism of each object, as well as the following morphisms: (1)
the generating morphism fromR to Bi,(2)
some isomorphisms that yield the Hecke algebra relations, as well as the respective projections to and inclusions from each summand in (2.10) and (2.12),(3)
the unit and counit of adjunction that makeBi into a self-biadjoint bimodule.
Consider𝒞 the subcategory generated monoidally over the left action of R by these morphisms, that is, it includes left R-linear combinations, compositions, and tensors of all its morphisms, then 𝒞 is a full subcategory, and thus it is actually 𝒮𝒞1.Proof.
For any objectsM,N in 𝒮𝒞1, there is an inclusion Hom𝒞(M,N)⊂Hom𝒮𝒞1(M,N) of graded left R-modules (since it is clearly an inclusion of R-modules, and all generating morphisms are homogeneous). One can define grk for any graded left R-module M by choosing generators of M/(R+M), where R+ is the ideal of positively graded elements, and it is a simple argument that a submodule of a free graded R-module with the same graded rank is in fact the entire module. So we need only show that Hom spaces in 𝒞 have the same graded rank.
We can define a semilinear form on the freeℤ[v,v-1]-algebra generated by bi by the formula (bi̲,bj̲)=grkHom𝒞(Bi̲,Bj̲). The existence of isomorphisms and projection maps will give us the direct sum decompositions (2.10)–(2.12) in 𝒞, with the resulting implications for Hom spaces. Therefore the Hecke algebra relation (2.2) are in the kernel of this semilinear form, so it descends to a form on the Hecke algebra. Each bi will be self-adjoint. When i̲ is increasing, Hom𝒞(R,Bi̲) contains the generator of the free rank one R-module Hom𝒮𝒞1(R,Bi̲), since that generator is the tensor of the generating morphisms from R to various Bi (see the proof of Claim 2.9). Hence it is in fact the entire module, so Hom𝒞(R,Bi̲)≅R{d}, and (1,bi̲)=vd.
By unicity, this inner product agrees with our earlier inner product on the Hecke algebra. In particular, the graded ranks agree, and the inclusion is full.Below we will construct a category𝒟𝒞1 of diagrams via generators and local relations, where the Hom spaces will be graded R-bimodules. We will construct a functor F1 from 𝒟𝒞1 to 𝒮𝒞1, showing that our diagrams give graphical presentation of morphisms in 𝒮𝒞1. The morphisms in the image of F1 will include all the morphisms enumerated in Proposition 2.13, hence the functor will be full. Calculating the Hom spaces in 𝒟𝒞1 between certain objects (corresponding to R, Bi̲ for i̲ increasing), we may use a similar argument to the above proposition to show that they are free R-modules of the same graded rank as the Hom spaces in 𝒮𝒞1, then the functor F1 will be faithful, and an equivalence of categories. This describes 𝒮𝒞1 in terms of generators and relations.Let𝒟𝒞2 be the category whose objects are finite direct sums of formal grading shifts of objects in 𝒟𝒞1, but whose morphisms only include degree 0 maps. Finally, let 𝒟𝒞=Kar(𝒟𝒞2) be the Karoubi envelope of 𝒟𝒞2. The functor F1 lifts to functors F2 and F, as in the picture below, with all three horizontal arrows being equivalences of categories.(2.24)We will define the category𝒟𝒞1 originally without reference to isotopy, in order to make the definition of the functor F1 entirely straightforward, using the standard rules for diagrammatics for bimodules. The category would be entirely unchanged if one used different pictures to represent each morphism. However, when the “correct” pictures are chosen for the generators, then every morphism can actually be viewed as a planar graph, and moreover two embedded graphs linked by isotopy represent the same morphism. One could very well define 𝒟𝒞1 originally using graphs, but this would obscure the definition of F1.The most difficult part of the proof will be showing the faithfulness ofF1, which involves a calculation of certain Hom spaces in the diagrammatic category. This calculation will be made possible by the planar graphs interpretation of 𝒟𝒞1, wherein some relatively simple graph theory can be applied to simplify pictures.


## 3. Definition of𝒟𝒞

This section contains a piecemeal definition of𝒟𝒞 and 𝒟𝒞1. For pedagogical reasons, we prefer to provide commentary as we go, instead of defining the category all at once (in fact, some relations do not make sense without the commentary). We also provide some redundant relations in the first pass, because they help make the category more intuitive. However, we repeat the definition all in one place in Section 3.4, without redundant relations, where we also explicitly define the functor F1.


### 3.1. The Category𝒟𝒞1: Zero Colors and One Color

This section and the next several will hold the definition of the category𝒟𝒞1, which will be a 𝕜-linear additive monoidal category, with ℤ-graded Hom spaces. Shortly it will become clear that Hom spaces are actually graded R-bimodules. It is generated monoidally by n objects i=1,…,n, whose tensor products will be denoted i̲=i1⋯id.Morphisms will be given by (linear combinations of) diagrams inside the stripℝ×[0,1], constructed out of lines colored by an index i, and certain other planar diagrams, modulo local relations. The intersection of the diagram with ℝ×{0}, called the lower boundary, will be a sequence i̲ of colored endpoints, the source of the map, and the upper boundaryj̲ will be the target. A vertical line colored i represents the identity map from i to i. The monoidal structure consists of placing diagrams side by side, and composition consists of placing diagrams one above the other, in the standard fashion for diagrammatic categories.We present the generators and relations in an order based on the number of colors they use. The one-color generators and relations will be sufficient to describe the category forn=1, the two-color ones for n=2, and the three-color ones for the general case. The set of all relations is invariant under all color changes that preserve adjacency, so we only display each generator for a single color i, using the conventions described in Section 2.4. However, the generator exists for each index i.All the relations we will give are homogeneous with respect to the grading on generators stated.The first class of generators, which use no colors, are the following endomorphisms of the monoidal identity∅:There is one such generator for eachi=1,…,n+1. It is a map of degree 2, which we call multiplication byxi. After we apply the functor F1, this will actually correspond to the endomorphism of R given by multiplication by xi. Together, these generators are called boxes. A morphism from ∅ to ∅ consisting of a sum of disjoint unions of boxes will be called a polynomial. Since the composition of multiplication by xi and multiplication by xj is multiplication by xixj, such a sum of products of boxes will obviously correspond under the functor to multiplication by an element f∈R. As a shorthand we draw such a morphism as a box with the corresponding element f inside. As a map from ∅ to ∅, and thus a closed diagram, a polynomial may be placed in any region of another diagram. Placing boxes in the rightmost and leftmost regions of a diagram will define the R-bimodule structure on Hom spaces in 𝒟𝒞1.The generating morphisms which use only one color areFor the beginner, the maps are, respectively, a map fromi to ∅, a map from ∅ to i, a map from ii to i, a map from i to ii.Remember, there is one such set of generators for each colori. We give these maps names, but the names are temporary. Once we explore the meaning of isotopy invariance, we will stop distinguishing between Merge and Split, and call them both trivalent vertices. Similarly we will stop distinguishing between StartDot and EndDot, and call them both dots.We also use a shorthand for the following compositions:We now list a series of relations using only one color, theone-color relations, dividing them into several types of relations for ease of reference. The first set we refer to as the Frobenius relations, since they imply that i is a Frobenius object in 𝒟𝒞1 (see [48, 49] for more on Frobenius algebras). Once we define the functor F1, this will imply that Bi is a Frobenius object in 𝒮𝒞1. Remember that the cups and caps appearing below can actually be rewritten in terms of the generators.(3.1)(3.2)(3.3)(3.4)(3.5)(3.6)(3.7)(3.8)(3.9)For quick reference, we refer to these relations by their Frobenius algebra names. The first two are the associativity of Merge and the coassociativity of Split. The next two are the unit and counit relations. Relation (3.5) is the biadjunction relation, and the final four are cyclicity relations.Remark 3.1.
For readers not well versed in cyclicity properties and their implications towards isotopy invariance, let us quickly discuss the topic, using the easily visualized notion of atwist. Given a morphism, one can twist it by taking a line which goes to the upper boundary and adding a cap, letting the line go to the other boundary instead. An example is given below,
One can also twist a downward line back up, or twist lines on the left as well. Two morphisms are twists of each other if they are related by a series of these simple twists, using cups and caps on the right and left side. For instance, relations (3.6) and (3.7) state that the Merge is a simple twist of the Split, twisting on the left or right. If one applies the same twist to every term in a relation, one gets a twist of that relation. For instance, relation (3.4) is actually a twist of the definition of the cup.
Because of biadjointness (3.5), twisting a line down and then back up will do nothing to the morphism. Once biadjointness is shown, all twists of a relation are equivalent, because twisting in the reverse direction we get the original relation back. When a morphism has a total of m inputs and outputs, twisting a single strand will often be referred to as rotation by 180/m degrees.
The above relations imply that twisting any of the above generators by 360 degrees will do nothing. A morphism is said to becyclic with respect to a fixed set of adjunctions (i.e., cups and caps) if 360 rotation does not change the morphism. Cyclicity is useful because of the following proposition.Proposition 3.2.
Fix adjunctions of each object, which are drawn as caps and cups. If every generating morphism in a diagram is cyclic with respect to those adjunctions, then so is the entire diagram, and the morphism represented by that diagram is invariant under isotopy of the diagram.For more on diagrammatics of biadjointness and the cyclicity property we refer the reader to [9, 48, 50–52].Merge and Split are 60 rotations of each other, and each is invariant under 120 degree rotation, so we may represent them isotopy-unambiguously with pictures that satisfy the same properties. A similar statement holds for StartDot and EndDot. We will refer to these morphisms as dots and trivalent vertices from now on, because these terms encapsulate the picture up to rotation.Remark 3.3.
Henceforth, we can take more liberties in our drawings. We can draw a horizontal line coloredi, and even though this can not be constructed using our generators, it is isotopy equivalent to a cup or cap which can be so constructed. We can allow a diagram to have a boundary not just on the top or bottom, but also on the side. While this does not represent a morphism in our category, the line running to the side boundary can be twisted either up or down to represent a genuine morphism. A relation drawn using diagrams with side boundaries does unambiguously give a relation in 𝒟𝒞1.Associativity and coassociativity are twists of each other. This relation is written in a rotation-invariant form below, and will be crucial in the sequel. We refer to this relation, which permits one to “slide” one trivalent vertex over another, asone-color associativity.(3.10)We refer to either picture above as an “H”. The horizontal line in the right picture is exactly such a liberty as in Remark 3.3.Note that relations (3.1), (3.5), (3.6), and (3.8) are sufficient to imply the other Frobenius relations, because of the remarks about twisting made above. Here is the proof of half of (3.7) using (3.6), as an illustrative example.The next set of relations are known aspolynomial slides, which have obvious analogies in the definitions of the modules Bi.(3.11)(3.12)(3.13)Thej appearing in the box in the last relation can be any index not equal to i or i+1. Together, these relations imply precisely that any polynomial which is invariant under si can be slid across a line colored i, since Ri is generated by xi+xi+1, xixi+1, and xj for j≠i,i+1. Therefore, for an arbitrary polynomial f, we have the following immediate consequence (see Remark 2.6).Proposition 3.4.
One may force a polynomial to the other side of a line, leaving at mostxi behind, as follows:
(3.14)(3.15)Proof.
This is proven in the same way as (2.7).Now these are  the final one-color relations. First, thedot relations(3.16)(3.17)The second equality in (3.16) is just the relation (3.11). Now, is the needle relation:(3.18)It is important to realize that such a relation doesnot apply if there is anything inside the eye of the needle, as can be seen in the following examples.Example 3.5.
Combining these relations, we have a number of simple but important consequences, which we leave as easy exercises to get the reader used to the diagrammatic calculus(3.19)Use the first dot relation, then the needle relation and the unit relation
(3.20)Use the needle relation and associativity
(3.21)As above, with the unit relation This is effectively the same example again, with more uses of associativity.As the examples demonstrate, and the following proposition proves, we may remove cycles of this nice form from a one-color graph.Proposition 3.6.
The following relations hold:(3.22)(3.23)
More generally, for any polynomialf, one has(3.24)Proof.
This is a simple consequence of (3.4), along with the needle, associativity, and unit relations.There is another relation which is equivalent (given the others) to the first equality in (3.16)(3.25)This relation quickly leads to the decompositionBi⊗Bi=Bi{1}⊕Bi{-1}, see Section 4.5.For a single color and two variablesx1,x2, the category above, modulo the relation x1=x2, is equivalent to the category considered by Libedinsky [13] in the case of a single label r. Morphisms given by dot, Merge, Split, and Cap correspond to morphisms εr̂, m̂r, p̂r, ĵr, and α̂r in [13, section 2.4]. Planar graphical notation, of paramount importance to us, is implicit in [13]. From here on, we diverge from Libedinsky's work, by generalizing to the case of the Weyl group Sn+1, while Libedinsky [13] investigates the right-angled case.


### 3.2. The Category𝒟𝒞1: Adjacent Colors

We now add some generators which mix adjacent colors, which we call6-valent vertices. Remember that the thick lines represent i+1, and the thin lines represent i,For the beginner, these maps are, respectively, a map fromi(i+1)i to (i+1)i(i+1), a map from (i+1)i(i+1) to i(i+1)i.Below are the relations which deal with our new generators. In addition to the relations below, we also impose the same relations with the colors switched. The two color variants in general do not imply each other. However, it is better to think of the two colors as being arbitrary adjacent colors, rather than one beingi and the other i+1; then one views these relations as generic for adjacent colors(3.26)(3.27)(3.28)(3.29)(3.30)It will be shown in Section4.5 that the first relation is related to the isomorphism (Bi⊗Bi+1⊗Bi)⊕Bi+1≅(Bi+1⊗Bi⊗Bi+1)⊕Bi.The second relation shows that the 6-valent vertex is cyclic, that drawing it as a 6-valent vertex is unambiguous, and that isotopy classes of diagrams built out of our local generators will still unambiguously designate a morphism. See Remark3.1 for details. Because of this, we have used the liberties of Remark 3.3 when writing the last two relations. Note that (3.27) does in fact imply the color-switched version of that same relation, using (3.5).The relation (3.29) contains a number of equalities, and it is clear that the last equality is merely a rotation of the color switch of the first equality. In fact, there are numerous redundancies amongst (3.29) and (3.30). It is a worthwhile exercise for the reader at this point to check the following statement.Example 3.7.
Assume the relation (3.28) and those before it, then any pair of equalities from (3.29) will imply both color variants of (3.30) as well as the remainder of the equalities from (3.29). Hint: adding a dot to the relation (3.29) allows one to recover (3.30), while the latter may be applied twice within the former.An important feature to notice is that the 6-valent vertex can be visualized as two trivalent vertices, one of each color, that overlap. If one takes a graph constructed out of dots, trivalent vertices, and 6-valent vertices (our generators so far), then the subgraph formed by all edges of a specific colori will have only univalent and trivalent vertices. We use the term two-color (overlap) associativity fori+1 to refer to the transformation performed by either (3.30) or the first equality of (3.29), because when viewed as an operation on the “thick”-colored graph, these operations mimic one-color associativity (3.10). Note that, under the same transformations, the “thin”-colored graph (labelled i) is transformed in a different way. However, the color-switched relations will give two-color associativity for i instead.


### 3.3. The Category𝒟𝒞1: Distant Colors

Fixj, an index which is not adjacent to i. In pictures involving both i and i+1, we also assume j is not adjacent to i+1. Remember that j is represented by a dashed line. This new generator is called a 4-valent vertex, or a crossing.Note that this definition also covers the same picture with the colors reversed. The colorsi and j can be switched freely since the only requirement was that they were distant from each other.Now, for relations involving the new generator.(3.31)(3.32)(3.33)(3.34)(3.35)(3.36)Relation (3.35) holds when you switch i and i+1, but one color variant will follow quickly from the other by twisting and applying the first relation. In the final relation, the new color represents an index k which is distant from both i and j. We will refer to (3.32) and (3.36) as the R2 and R3 moves, respectively, because of the obvious analogy to knot theory. The R2 relation is essentially the isomorphism Bi⊗Bj≅Bj⊗Bi, see Section 4.5.The same statements about cyclicity and drawing diagrams with sideways boundaries apply from before (see Remarks3.1 and 3.3). Once again, the 4-valent vertices are drawn so that morphisms are isotopy invariant.The relations (3.32)–(3.36) imply that a j-colored strand can just be pulled underneath any morphism only using colors distant from j, since it can be pulled under any generating morphism, whether it be a line, a dot, a trivalent vertex, or a 6-valent vertex. In fact, thanks to (3.4), the R2 move follows from (3.33) and (3.34).We have now listed all the generators of our subcategory: trivalent, 4-valent, and 6-valent vertices, and dots. There is one final relation, coming from the fact thati+1 and i-1 may not interact, but they do jointly interact with i. The final relation will be called three-color (overlap) associativity fori±1:(3.37)In the above diagram, dotted lines carry labeli-1, thick lines i+1 and thin solid lines i. Rotating this relation by 90 degrees, we get the same relation except with i+1 and i-1 switched, so that only color variant is needed to imply both. The “thick”-colored graph undergoes the associativity transformation. The same is true (symmetrically) with the “dotted”-colored graph.This concludes the definition of the category𝒟𝒞1.


### 3.4. The Complete Definition and the Functorℱ1

In order to put everything in one place with no redundancy, let us define the category again.Definition 3.8.
The category𝒟𝒞1 has objects given by sequences i̲ of indices in {1,…,n}, with a monoidal structure given by concatenation. Fix two sequences i̲ and j̲. Consider the set of all diagrams in ℝ×[0,1], constructed out of vertical lines colored by indices, and out of the generating pictures below, such that the intersection of the diagram with ℝ×{0} is the sequence of points i̲, and the intersection with ℝ×{1} is j̲. This set is graded, where the generators have the degree indicated, then the space Hom𝒟𝒞1(i̲,j̲) is defined to be the 𝕜-linear span of this set of diagrams, modulo the homogeneous local relations below,Generators:Relations:Some relations are drawn using the liberties of Remark3.3. We also use the definition of the cap and cup,For each color,Here,i is the color of the line, and j is a color ≠i,i+1,For any two adjacent colors,For any two distant colors,For two adjacent colors and a third, distant to both,For three mutually distant colors,For three colors with the same adjacency as{1,2,3},Definition 3.9.
LetF1 be the functor from 𝒟𝒞1 to 𝒮𝒞1 specified as follows. On objects,  F1(i̲)=Bi̲. We define the functor on generating morphisms and extend it monoidally to all morphisms.
In doing so, wealways use the isomorphism (2.6) to identify Bi̲ with the R-bimodule spanned by a choice of d(i̲)+1 polynomials. If one thinks of Bi̲ diagrammatically as d vertical lines, then a spanning element of Bi̲ is a choice of polynomial for each empty region delineated by the lines (and polynomials with the appropriate symmetry may slide across the lines). We write the map explicitly for a general element when it is easy enough to do so, or we write it for a spanning set as an R-bimodule (see Remark 2.7).
For a line coloredi,
For lines coloredi and j distant,
For a thin line coloredi and a thick line colored i+1,
For any1≤i≤n+1,Claim 3.10.
The above maps areR-bimodule maps.Proof.
This is obviously true for EndDot, since the resulting map is no more than multiplication. StartDot is sent precisely to the generatorφi of Hom(R,Bi) discussed in Section 2.3. Split and Merge have already been seen as inclusion and projection maps in the isomorphism Bi⊗Bi≅Bi{1}⊕Bi{-1}, see Remark 2.6. For the 4-valent vertex, the only polynomials which slide all the way across Bi⊗Bj or Bj⊗Bi are in Ri,j, so that the map f⊗1⊗g→f⊗1⊗g is a bimodule map (that f⊗1⊗g spans it was observed in Remark 2.7).
Only the 6-valent vertices remain to be checked. Consider the first of the two variants. The generating set{1⊗1⊗1⊗1,1⊗xi⊗1⊗1} as an R-bimodule was chosen because xi can be slid freely between the second and third slots. We have defined the R-bimodule map on generators before showing that the map is an R-bimodule map at all, which is akin to putting the cart before the horse. Let us explicitly define the map on a 𝕜 spanning set by the following algorithm: given f⊗g⊗h⊗k∈Bi⊗Bi+1⊗Bi, first we force h to the right and slide the “remainder" to the left, that is f⊗g⊗h⊗k=f⊗g⊗1⊗kPi(h)+f⊗gxi⊗1⊗k∂i(h); then we force the terms in the second slot to the left, yielding fPi(g)⊗1⊗1⊗kPi(h)+f∂i(g)⊗xi⊗1⊗kPi(h)+fPi(gxi)⊗1⊗1⊗k∂i(h)+f∂i(gxi)⊗xi⊗1⊗k∂i(h). Finally, each term can be evaluated using the given definition of F1 on generators. This gives an explicit formula for the image of f⊗g⊗h⊗k, which we only need check is invariant under: sliding an element of Ri from f to g, or from h to k; sliding an element of Ri+1 from g to h. Sliding elements of Ri does not pose a problem, since we defined the map by forcing h to k and g to f, which fully respects such slides. Checking invariance under slides from g to h is nontrivial. However, the bulk of the work is encapsulated in the following discussion, which is useful for calculations in general.
By adding and subtractingxi+2, the image of 1⊗xi⊗1⊗1 under the first 6-valent vertex (see above) can be written more symmetrically as (xi+xi+1+xi+2)(1⊗1⊗1⊗1)-xi+2⊗1⊗1⊗1-1⊗1⊗1⊗xi+2. The first term is a polynomial symmetric in all the relevant variables and thus can be slid anywhere. In the other two terms, xi+2 can not be slid freely under a line labelled  i+1, so it is stuck in its respective position. In contrast, 1⊗xi+1⊗1⊗1 and 1⊗1⊗xi+1⊗1 are not equal, since xi+1 can not be slid over a line labelled i+1, but the images of both these elements are easier to remember, and are shown below,
The way to remember these formulae is that the variable which cannot be slid is sent to the variable which cannot be slid, from the middle on one side to the exterior on the other. It is easy to see that these calculations were done according to the algorithm above, forcingxi+1 to the outside first and then evaluating on the leftover xi.
Now, we do the consistency check for the simplest cases. We wish to show that1⊗(xi+1+xi+2)⊗1⊗1 and 1⊗1⊗(xi+1+xi+2)⊗1 are sent to the same element by the algorithm. However, this is rather easy, for in both cases, the xi+2 term slides immediately to the exterior, and the xi+1 term is evaluated as above, so both are sent to xi+2⊗1⊗1⊗1+1⊗1⊗1⊗xi+2. Similarly, both 1⊗xi+1xi+2⊗1⊗1 and 1⊗1⊗xi+1xi+2⊗1 are sent to xi+2⊗1⊗1⊗xi+2. The general case is not significantly more difficult than this; we leave the details to the reader.Proposition 3.11.
The functorF1 is well-defined. That is, the relations of 𝒟𝒞1 hold between morphisms of R-bimodules in 𝒮𝒞1.Checking that the relations hold is a series of simple but tedious calculations that is postponed until Section5.1. We assume this result henceforth. In addition, we note once and for all that (as one can easily check) all relations in the definition of 𝒟𝒞1 are homogeneous, and F1 preserves the degree of the generators.Addendum 2.
It may strike the reader as unusual that the definition of the functor seems lopsided, while the definition of𝒟𝒞1 is invariant under right-left reflection, or under reversing the order of the colors n, n-1,…,1. For instance, F1 applied to StartDot yields the element xi⊗1-1⊗xi+1, which is actually invariant under right-left reflection but not immediately so. Had this element been rewritten as (xi-xi+1)/2⊗1+1⊗(xi-xi+1)/2, perhaps the calculations would be more natural despite having more fractions. A worse offender is the forcing rule 1⊗g=(g-∂i(g)xi)⊗1+∂i(g)⊗xi, which should be rewritten 1⊗g=(g+si(g))/2⊗1+∂i(g)⊗(xi-xi+1)/2. In general, the elements xi-xi+1 are more natural than xi or xi+1, coming from the reflection representation rather than the standard representation of Sn+1 (see Remark 2.2 and Section 4.6).
Previous versions of this paper, however, used the style above, and so we feel compelled to stick with it to maintain consistency. Also, checking thatF1 is a functor may be easier with the current notation.


## 3.1. The Category𝒟𝒞1: Zero Colors and One Color

This section and the next several will hold the definition of the category𝒟𝒞1, which will be a 𝕜-linear additive monoidal category, with ℤ-graded Hom spaces. Shortly it will become clear that Hom spaces are actually graded R-bimodules. It is generated monoidally by n objects i=1,…,n, whose tensor products will be denoted i̲=i1⋯id.Morphisms will be given by (linear combinations of) diagrams inside the stripℝ×[0,1], constructed out of lines colored by an index i, and certain other planar diagrams, modulo local relations. The intersection of the diagram with ℝ×{0}, called the lower boundary, will be a sequence i̲ of colored endpoints, the source of the map, and the upper boundaryj̲ will be the target. A vertical line colored i represents the identity map from i to i. The monoidal structure consists of placing diagrams side by side, and composition consists of placing diagrams one above the other, in the standard fashion for diagrammatic categories.We present the generators and relations in an order based on the number of colors they use. The one-color generators and relations will be sufficient to describe the category forn=1, the two-color ones for n=2, and the three-color ones for the general case. The set of all relations is invariant under all color changes that preserve adjacency, so we only display each generator for a single color i, using the conventions described in Section 2.4. However, the generator exists for each index i.All the relations we will give are homogeneous with respect to the grading on generators stated.The first class of generators, which use no colors, are the following endomorphisms of the monoidal identity∅:There is one such generator for eachi=1,…,n+1. It is a map of degree 2, which we call multiplication byxi. After we apply the functor F1, this will actually correspond to the endomorphism of R given by multiplication by xi. Together, these generators are called boxes. A morphism from ∅ to ∅ consisting of a sum of disjoint unions of boxes will be called a polynomial. Since the composition of multiplication by xi and multiplication by xj is multiplication by xixj, such a sum of products of boxes will obviously correspond under the functor to multiplication by an element f∈R. As a shorthand we draw such a morphism as a box with the corresponding element f inside. As a map from ∅ to ∅, and thus a closed diagram, a polynomial may be placed in any region of another diagram. Placing boxes in the rightmost and leftmost regions of a diagram will define the R-bimodule structure on Hom spaces in 𝒟𝒞1.The generating morphisms which use only one color areFor the beginner, the maps are, respectively, a map fromi to ∅, a map from ∅ to i, a map from ii to i, a map from i to ii.Remember, there is one such set of generators for each colori. We give these maps names, but the names are temporary. Once we explore the meaning of isotopy invariance, we will stop distinguishing between Merge and Split, and call them both trivalent vertices. Similarly we will stop distinguishing between StartDot and EndDot, and call them both dots.We also use a shorthand for the following compositions:We now list a series of relations using only one color, theone-color relations, dividing them into several types of relations for ease of reference. The first set we refer to as the Frobenius relations, since they imply that i is a Frobenius object in 𝒟𝒞1 (see [48, 49] for more on Frobenius algebras). Once we define the functor F1, this will imply that Bi is a Frobenius object in 𝒮𝒞1. Remember that the cups and caps appearing below can actually be rewritten in terms of the generators.(3.1)(3.2)(3.3)(3.4)(3.5)(3.6)(3.7)(3.8)(3.9)For quick reference, we refer to these relations by their Frobenius algebra names. The first two are the associativity of Merge and the coassociativity of Split. The next two are the unit and counit relations. Relation (3.5) is the biadjunction relation, and the final four are cyclicity relations.Remark 3.1.
For readers not well versed in cyclicity properties and their implications towards isotopy invariance, let us quickly discuss the topic, using the easily visualized notion of atwist. Given a morphism, one can twist it by taking a line which goes to the upper boundary and adding a cap, letting the line go to the other boundary instead. An example is given below,
One can also twist a downward line back up, or twist lines on the left as well. Two morphisms are twists of each other if they are related by a series of these simple twists, using cups and caps on the right and left side. For instance, relations (3.6) and (3.7) state that the Merge is a simple twist of the Split, twisting on the left or right. If one applies the same twist to every term in a relation, one gets a twist of that relation. For instance, relation (3.4) is actually a twist of the definition of the cup.
Because of biadjointness (3.5), twisting a line down and then back up will do nothing to the morphism. Once biadjointness is shown, all twists of a relation are equivalent, because twisting in the reverse direction we get the original relation back. When a morphism has a total of m inputs and outputs, twisting a single strand will often be referred to as rotation by 180/m degrees.
The above relations imply that twisting any of the above generators by 360 degrees will do nothing. A morphism is said to becyclic with respect to a fixed set of adjunctions (i.e., cups and caps) if 360 rotation does not change the morphism. Cyclicity is useful because of the following proposition.Proposition 3.2.
Fix adjunctions of each object, which are drawn as caps and cups. If every generating morphism in a diagram is cyclic with respect to those adjunctions, then so is the entire diagram, and the morphism represented by that diagram is invariant under isotopy of the diagram.For more on diagrammatics of biadjointness and the cyclicity property we refer the reader to [9, 48, 50–52].Merge and Split are 60 rotations of each other, and each is invariant under 120 degree rotation, so we may represent them isotopy-unambiguously with pictures that satisfy the same properties. A similar statement holds for StartDot and EndDot. We will refer to these morphisms as dots and trivalent vertices from now on, because these terms encapsulate the picture up to rotation.Remark 3.3.
Henceforth, we can take more liberties in our drawings. We can draw a horizontal line coloredi, and even though this can not be constructed using our generators, it is isotopy equivalent to a cup or cap which can be so constructed. We can allow a diagram to have a boundary not just on the top or bottom, but also on the side. While this does not represent a morphism in our category, the line running to the side boundary can be twisted either up or down to represent a genuine morphism. A relation drawn using diagrams with side boundaries does unambiguously give a relation in 𝒟𝒞1.Associativity and coassociativity are twists of each other. This relation is written in a rotation-invariant form below, and will be crucial in the sequel. We refer to this relation, which permits one to “slide” one trivalent vertex over another, asone-color associativity.(3.10)We refer to either picture above as an “H”. The horizontal line in the right picture is exactly such a liberty as in Remark 3.3.Note that relations (3.1), (3.5), (3.6), and (3.8) are sufficient to imply the other Frobenius relations, because of the remarks about twisting made above. Here is the proof of half of (3.7) using (3.6), as an illustrative example.The next set of relations are known aspolynomial slides, which have obvious analogies in the definitions of the modules Bi.(3.11)(3.12)(3.13)Thej appearing in the box in the last relation can be any index not equal to i or i+1. Together, these relations imply precisely that any polynomial which is invariant under si can be slid across a line colored i, since Ri is generated by xi+xi+1, xixi+1, and xj for j≠i,i+1. Therefore, for an arbitrary polynomial f, we have the following immediate consequence (see Remark 2.6).Proposition 3.4.
One may force a polynomial to the other side of a line, leaving at mostxi behind, as follows:
(3.14)(3.15)Proof.
This is proven in the same way as (2.7).Now these are  the final one-color relations. First, thedot relations(3.16)(3.17)The second equality in (3.16) is just the relation (3.11). Now, is the needle relation:(3.18)It is important to realize that such a relation doesnot apply if there is anything inside the eye of the needle, as can be seen in the following examples.Example 3.5.
Combining these relations, we have a number of simple but important consequences, which we leave as easy exercises to get the reader used to the diagrammatic calculus(3.19)Use the first dot relation, then the needle relation and the unit relation
(3.20)Use the needle relation and associativity
(3.21)As above, with the unit relation This is effectively the same example again, with more uses of associativity.As the examples demonstrate, and the following proposition proves, we may remove cycles of this nice form from a one-color graph.Proposition 3.6.
The following relations hold:(3.22)(3.23)
More generally, for any polynomialf, one has(3.24)Proof.
This is a simple consequence of (3.4), along with the needle, associativity, and unit relations.There is another relation which is equivalent (given the others) to the first equality in (3.16)(3.25)This relation quickly leads to the decompositionBi⊗Bi=Bi{1}⊕Bi{-1}, see Section 4.5.For a single color and two variablesx1,x2, the category above, modulo the relation x1=x2, is equivalent to the category considered by Libedinsky [13] in the case of a single label r. Morphisms given by dot, Merge, Split, and Cap correspond to morphisms εr̂, m̂r, p̂r, ĵr, and α̂r in [13, section 2.4]. Planar graphical notation, of paramount importance to us, is implicit in [13]. From here on, we diverge from Libedinsky's work, by generalizing to the case of the Weyl group Sn+1, while Libedinsky [13] investigates the right-angled case.


## 3.2. The Category𝒟𝒞1: Adjacent Colors

We now add some generators which mix adjacent colors, which we call6-valent vertices. Remember that the thick lines represent i+1, and the thin lines represent i,For the beginner, these maps are, respectively, a map fromi(i+1)i to (i+1)i(i+1), a map from (i+1)i(i+1) to i(i+1)i.Below are the relations which deal with our new generators. In addition to the relations below, we also impose the same relations with the colors switched. The two color variants in general do not imply each other. However, it is better to think of the two colors as being arbitrary adjacent colors, rather than one beingi and the other i+1; then one views these relations as generic for adjacent colors(3.26)(3.27)(3.28)(3.29)(3.30)It will be shown in Section4.5 that the first relation is related to the isomorphism (Bi⊗Bi+1⊗Bi)⊕Bi+1≅(Bi+1⊗Bi⊗Bi+1)⊕Bi.The second relation shows that the 6-valent vertex is cyclic, that drawing it as a 6-valent vertex is unambiguous, and that isotopy classes of diagrams built out of our local generators will still unambiguously designate a morphism. See Remark3.1 for details. Because of this, we have used the liberties of Remark 3.3 when writing the last two relations. Note that (3.27) does in fact imply the color-switched version of that same relation, using (3.5).The relation (3.29) contains a number of equalities, and it is clear that the last equality is merely a rotation of the color switch of the first equality. In fact, there are numerous redundancies amongst (3.29) and (3.30). It is a worthwhile exercise for the reader at this point to check the following statement.Example 3.7.
Assume the relation (3.28) and those before it, then any pair of equalities from (3.29) will imply both color variants of (3.30) as well as the remainder of the equalities from (3.29). Hint: adding a dot to the relation (3.29) allows one to recover (3.30), while the latter may be applied twice within the former.An important feature to notice is that the 6-valent vertex can be visualized as two trivalent vertices, one of each color, that overlap. If one takes a graph constructed out of dots, trivalent vertices, and 6-valent vertices (our generators so far), then the subgraph formed by all edges of a specific colori will have only univalent and trivalent vertices. We use the term two-color (overlap) associativity fori+1 to refer to the transformation performed by either (3.30) or the first equality of (3.29), because when viewed as an operation on the “thick”-colored graph, these operations mimic one-color associativity (3.10). Note that, under the same transformations, the “thin”-colored graph (labelled i) is transformed in a different way. However, the color-switched relations will give two-color associativity for i instead.


## 3.3. The Category𝒟𝒞1: Distant Colors

Fixj, an index which is not adjacent to i. In pictures involving both i and i+1, we also assume j is not adjacent to i+1. Remember that j is represented by a dashed line. This new generator is called a 4-valent vertex, or a crossing.Note that this definition also covers the same picture with the colors reversed. The colorsi and j can be switched freely since the only requirement was that they were distant from each other.Now, for relations involving the new generator.(3.31)(3.32)(3.33)(3.34)(3.35)(3.36)Relation (3.35) holds when you switch i and i+1, but one color variant will follow quickly from the other by twisting and applying the first relation. In the final relation, the new color represents an index k which is distant from both i and j. We will refer to (3.32) and (3.36) as the R2 and R3 moves, respectively, because of the obvious analogy to knot theory. The R2 relation is essentially the isomorphism Bi⊗Bj≅Bj⊗Bi, see Section 4.5.The same statements about cyclicity and drawing diagrams with sideways boundaries apply from before (see Remarks3.1 and 3.3). Once again, the 4-valent vertices are drawn so that morphisms are isotopy invariant.The relations (3.32)–(3.36) imply that a j-colored strand can just be pulled underneath any morphism only using colors distant from j, since it can be pulled under any generating morphism, whether it be a line, a dot, a trivalent vertex, or a 6-valent vertex. In fact, thanks to (3.4), the R2 move follows from (3.33) and (3.34).We have now listed all the generators of our subcategory: trivalent, 4-valent, and 6-valent vertices, and dots. There is one final relation, coming from the fact thati+1 and i-1 may not interact, but they do jointly interact with i. The final relation will be called three-color (overlap) associativity fori±1:(3.37)In the above diagram, dotted lines carry labeli-1, thick lines i+1 and thin solid lines i. Rotating this relation by 90 degrees, we get the same relation except with i+1 and i-1 switched, so that only color variant is needed to imply both. The “thick”-colored graph undergoes the associativity transformation. The same is true (symmetrically) with the “dotted”-colored graph.This concludes the definition of the category𝒟𝒞1.


## 3.4. The Complete Definition and the Functorℱ1

In order to put everything in one place with no redundancy, let us define the category again.Definition 3.8.
The category𝒟𝒞1 has objects given by sequences i̲ of indices in {1,…,n}, with a monoidal structure given by concatenation. Fix two sequences i̲ and j̲. Consider the set of all diagrams in ℝ×[0,1], constructed out of vertical lines colored by indices, and out of the generating pictures below, such that the intersection of the diagram with ℝ×{0} is the sequence of points i̲, and the intersection with ℝ×{1} is j̲. This set is graded, where the generators have the degree indicated, then the space Hom𝒟𝒞1(i̲,j̲) is defined to be the 𝕜-linear span of this set of diagrams, modulo the homogeneous local relations below,Generators:Relations:Some relations are drawn using the liberties of Remark3.3. We also use the definition of the cap and cup,For each color,Here,i is the color of the line, and j is a color ≠i,i+1,For any two adjacent colors,For any two distant colors,For two adjacent colors and a third, distant to both,For three mutually distant colors,For three colors with the same adjacency as{1,2,3},Definition 3.9.
LetF1 be the functor from 𝒟𝒞1 to 𝒮𝒞1 specified as follows. On objects,  F1(i̲)=Bi̲. We define the functor on generating morphisms and extend it monoidally to all morphisms.
In doing so, wealways use the isomorphism (2.6) to identify Bi̲ with the R-bimodule spanned by a choice of d(i̲)+1 polynomials. If one thinks of Bi̲ diagrammatically as d vertical lines, then a spanning element of Bi̲ is a choice of polynomial for each empty region delineated by the lines (and polynomials with the appropriate symmetry may slide across the lines). We write the map explicitly for a general element when it is easy enough to do so, or we write it for a spanning set as an R-bimodule (see Remark 2.7).
For a line coloredi,
For lines coloredi and j distant,
For a thin line coloredi and a thick line colored i+1,
For any1≤i≤n+1,Claim 3.10.
The above maps areR-bimodule maps.Proof.
This is obviously true for EndDot, since the resulting map is no more than multiplication. StartDot is sent precisely to the generatorφi of Hom(R,Bi) discussed in Section 2.3. Split and Merge have already been seen as inclusion and projection maps in the isomorphism Bi⊗Bi≅Bi{1}⊕Bi{-1}, see Remark 2.6. For the 4-valent vertex, the only polynomials which slide all the way across Bi⊗Bj or Bj⊗Bi are in Ri,j, so that the map f⊗1⊗g→f⊗1⊗g is a bimodule map (that f⊗1⊗g spans it was observed in Remark 2.7).
Only the 6-valent vertices remain to be checked. Consider the first of the two variants. The generating set{1⊗1⊗1⊗1,1⊗xi⊗1⊗1} as an R-bimodule was chosen because xi can be slid freely between the second and third slots. We have defined the R-bimodule map on generators before showing that the map is an R-bimodule map at all, which is akin to putting the cart before the horse. Let us explicitly define the map on a 𝕜 spanning set by the following algorithm: given f⊗g⊗h⊗k∈Bi⊗Bi+1⊗Bi, first we force h to the right and slide the “remainder" to the left, that is f⊗g⊗h⊗k=f⊗g⊗1⊗kPi(h)+f⊗gxi⊗1⊗k∂i(h); then we force the terms in the second slot to the left, yielding fPi(g)⊗1⊗1⊗kPi(h)+f∂i(g)⊗xi⊗1⊗kPi(h)+fPi(gxi)⊗1⊗1⊗k∂i(h)+f∂i(gxi)⊗xi⊗1⊗k∂i(h). Finally, each term can be evaluated using the given definition of F1 on generators. This gives an explicit formula for the image of f⊗g⊗h⊗k, which we only need check is invariant under: sliding an element of Ri from f to g, or from h to k; sliding an element of Ri+1 from g to h. Sliding elements of Ri does not pose a problem, since we defined the map by forcing h to k and g to f, which fully respects such slides. Checking invariance under slides from g to h is nontrivial. However, the bulk of the work is encapsulated in the following discussion, which is useful for calculations in general.
By adding and subtractingxi+2, the image of 1⊗xi⊗1⊗1 under the first 6-valent vertex (see above) can be written more symmetrically as (xi+xi+1+xi+2)(1⊗1⊗1⊗1)-xi+2⊗1⊗1⊗1-1⊗1⊗1⊗xi+2. The first term is a polynomial symmetric in all the relevant variables and thus can be slid anywhere. In the other two terms, xi+2 can not be slid freely under a line labelled  i+1, so it is stuck in its respective position. In contrast, 1⊗xi+1⊗1⊗1 and 1⊗1⊗xi+1⊗1 are not equal, since xi+1 can not be slid over a line labelled i+1, but the images of both these elements are easier to remember, and are shown below,
The way to remember these formulae is that the variable which cannot be slid is sent to the variable which cannot be slid, from the middle on one side to the exterior on the other. It is easy to see that these calculations were done according to the algorithm above, forcingxi+1 to the outside first and then evaluating on the leftover xi.
Now, we do the consistency check for the simplest cases. We wish to show that1⊗(xi+1+xi+2)⊗1⊗1 and 1⊗1⊗(xi+1+xi+2)⊗1 are sent to the same element by the algorithm. However, this is rather easy, for in both cases, the xi+2 term slides immediately to the exterior, and the xi+1 term is evaluated as above, so both are sent to xi+2⊗1⊗1⊗1+1⊗1⊗1⊗xi+2. Similarly, both 1⊗xi+1xi+2⊗1⊗1 and 1⊗1⊗xi+1xi+2⊗1 are sent to xi+2⊗1⊗1⊗xi+2. The general case is not significantly more difficult than this; we leave the details to the reader.Proposition 3.11.
The functorF1 is well-defined. That is, the relations of 𝒟𝒞1 hold between morphisms of R-bimodules in 𝒮𝒞1.Checking that the relations hold is a series of simple but tedious calculations that is postponed until Section5.1. We assume this result henceforth. In addition, we note once and for all that (as one can easily check) all relations in the definition of 𝒟𝒞1 are homogeneous, and F1 preserves the degree of the generators.Addendum 2.
It may strike the reader as unusual that the definition of the functor seems lopsided, while the definition of𝒟𝒞1 is invariant under right-left reflection, or under reversing the order of the colors n, n-1,…,1. For instance, F1 applied to StartDot yields the element xi⊗1-1⊗xi+1, which is actually invariant under right-left reflection but not immediately so. Had this element been rewritten as (xi-xi+1)/2⊗1+1⊗(xi-xi+1)/2, perhaps the calculations would be more natural despite having more fractions. A worse offender is the forcing rule 1⊗g=(g-∂i(g)xi)⊗1+∂i(g)⊗xi, which should be rewritten 1⊗g=(g+si(g))/2⊗1+∂i(g)⊗(xi-xi+1)/2. In general, the elements xi-xi+1 are more natural than xi or xi+1, coming from the reflection representation rather than the standard representation of Sn+1 (see Remark 2.2 and Section 4.6).
Previous versions of this paper, however, used the style above, and so we feel compelled to stick with it to maintain consistency. Also, checking thatF1 is a functor may be easier with the current notation.


## 4. Consequences

### 4.1. Terminology

We will spend the next few sections classifying the homomorphisms in𝒟𝒞1. For many of the results, proofs will be postponed until Section 5.2.We will we using the fact, extensively discussed in the previous sections, that a morphism can be viewed unambiguously as an isotopy class of graphs with polynomials in the regions (or rather, a linear combination of these). Henceforth, the termgraph only refers to colored finite graphs with boundary (embedded in the planar strip) which can be constructed out of univalent, trivalent, 4-valent, and 6-valent vertices as above. Remember that these graphs do have edges which run to the boundary, which we call boundary lines, and may have edges which meet neither the boundary nor any vertex, and thus must necessarily form a circle. We say a graph has a boundary if it has at least one boundary line. A graph divides the planar strip into regions, and there are two distinguished regions: the lefthand and righthand regions, which contain -∞ and ∞, respectively.We call aboundary dot any connected component of a graph which consists entirely of an edge starting at the boundary and ending in a dot. We call a double dot any connected component of a graph which consists entirely of an edge with a dot on both ends. Cutting an edge in a diagram and replacing it with two dots we call breaking the edge (see, for instance, relation (3.16)).Given a setS of graphs and a morphism φ in 𝒟𝒞1, we say that S  underliesφ if φ can be written as a linear combination of morphisms, each of which is given by a graph Γ∈S with polynomials in regions. We say that a graph Γreduces to S if S underlies every morphism that Γ underlies. Clearly reduction is transitive, in that if Γ reduces to S, and every graph in S reduces to S′, then Γ reduces to S′. Our goal will be to find a nice set of graphs to which all other graphs reduce. We will do this by finding reduction moves, which are local moves on graphs, sending a graph to a set of graphs to which it reduces.Example 4.1.
The relation (3.25) implies that  reduces to . In other words,  underlies both the terms on the right side of (3.25). This can be applied as a local reduction move within any graph.LetT be a subset of {1,…,n}. The T-graph of a graph will be the subgraph consisting of all edges colored i for i∈T. Some 6-valent vertices in the original graph may become trivalent vertices in the T-graph. Similarly, some 4-valent vertices in the original graph may become 2-valent vertices in the T-graph, which we ignore, connecting the incoming edges into a single edge. The T-graph is itself a graph by our above definition. Most often we will just consider the i-graph for a single color (i.e., T={i}). Typically, our reduction moves will be designed to simplify the i-graph for a particular i, allowing us to simplify the graph one color at a time.Remark 4.2.
The rest of this paper will have numerous calculations, but they will mostly be calculations with the underlying graphs, not keeping track of polynomials, so they do not reflect how morphisms actually behave in𝒟𝒞1. For lots of examples of computations in the graphical calculus, see [33].


### 4.2. One Color Reductions

In this section, we assume all graphs consist of a single colori.Definition 4.3.
Consider the following “moves", or transformations. They take a subdiagram looking like Start, and replace that subdiagram with Finish. We call these thebasic moves.Remember, these are moves on graphs, not graphs with polynomials. Note that the needle move, by adding a dot on the bottom, yields a reduction from the circle to a double dot. The only moves which change the connectivity of a graph are double dot removal, which deletes a connected component, and the connecting move, which has the potential to link two components into one.Claim 4.4.
All of these moves are reduction moves in𝒟𝒞1.Proof.
The associativity move follows from (3.10). That is, even if there are polynomials in the regions of the graph, the relation (3.10) can still be applied. These polynomials, being in external regions, do not interfere with the application of relations. Similarly, dot contraction/extension follow from (3.4), dot removal follows from (3.17), and the connecting move follows from (3.25).
The needle move remains. Suppose we have an arbitrary polynomialf in the eye of the needle. We may use (3.24), generalizing (3.19), to replace the diagram with a dot accompanied by ∂i(f).The following example of reduction should be familiar.Example 4.5.
In order, this is done with associativity, associativity, needle, and dot contraction moves.Example 4.6.
This is meant to indicate an arbitrary length cycle of this form, and reduction is done with associativity, needle, and dot contraction moves.Definition 4.7.
Asimple treeT with m boundary lines is a connected one-color graph with boundary, whose form depends on m: (1)
ifm≥2, then T is a trivalent tree with m-2 vertices connecting all the boundary lines. Note that any two such trees are equivalent under the associativity move;(2)
ifm=1, then T is a single boundary dot;(3)
ifm=0, then T is the empty graph.Definition 4.8.
Acycle in a one-color graph is either a circle or a path from a vertex to itself which does not repeat any edges. Any cycle splits the plane into two parts, the inside and outside of the cycle. A cycle is minimal if the inside of the cycle consists of a single region.By counting vertices, it is clear that any connected purely trivalent graph with no cycles is a simple tree. Any graph with a cycle has a minimal cycle.We will now give a precise inductive algorithm to reduce a graph to a disjoint union of simple trees, by reducing minimal cycles.Proposition 4.9.
Consider a minimal cycle in a one-color graphΓ. Using the associativity, needle, dot removal, and dot contraction/extension moves, we may reduce a neighborhood of the cycle (including the inside region) to a simple tree (see (4.1)).(4.1)Proposition 4.10.
Using the associativity, needle, dot removal and dot contraction/extension moves, one can reduce any one-color graphΓ to a disjoint union of simple trees. During this process, each component with no boundary lines will be replaced with the empty graph, and after this is done, no further connected components are created or destroyed or merged.We prove both propositions together, in several steps.Proof of Proposition4.10 for a Graph with No Cycles.
Suppose there are no cycles inΓ. If there is a dot, the edge coming from that dot must connect to either the boundary, another dot, or a trivalent vertex. Our simplification algorithm is as follows. (1)
Remove any dot connected to a trivalent vertex, using dot contraction. Repeat Step 1 until no such dots remain. This does not alter the connected components.(2)
Replace any double dot with the empty set, using double dot removal. Because Step 1 did not alter the connected components, this could only be applied to double dots which arose from components which had no boundary lines.
Boundary dots are in their own connected component. Any other connected component is purely trivalent and has no cycles, so it must be a simple tree.Proof of Proposition4.9, Assuming Proposition 4.10 for Graphs with No Cycles.
Letγ denote a minimal cycle of Γ. Consider a neighborhood of γ in Γ, and let Γ′ be the subgraph consisting of the interior of the cycle, as in (4.1). Let us call the boundary lines of Γ′spokes, since they run into γ from the inside, like spokes hitting the wheel of a bicycle. Now Γ′ may not have any cycles, or else γ would not be a minimal cycle. Moreover, the spokes of Γ′ must be in distinct connected components of Γ′, or else they would create additional regions and γ would not be a minimal cycle. Our simplification algorithm is as follows: (1)
Apply Proposition4.10 to Γ′, replacing Γ′ with a disjoint union of boundary dots, one for each spoke.(2)
Use dot contraction to remove all the spokes. We are now in the situation of Example4.6.(3)
Apply associativity as in Example4.5, reducing the length of γ by one. Repeat until γ is a needle or a circle.(4)
Ifγ is a needle, apply the needle move to replace it with a dot. If associativity moves were performed in Step 3, use dot contraction to contract this dot into one of the trivalent vertices, as in Example 4.5.(5)
Ifγ is a circle, apply dot extension to replace it with a needle attached to a dot, then apply needle reduction to obtain a double dot, and double dot removal to obtain the empty graph.
It is a simple observation that the result of this procedure is a simple tree, and that the only alteration of connected components which occurred was the removal of components which had no boundary lines to begin with.Proof of Proposition4.10 in the General Case.
Suppose we have an arbitrary graphΓ. Our simplification algorithm is as follows: (1)
IfΓ has a cycle, apply Proposition 4.9 to replace its neighborhood with a simple tree. Repeat this process until Γ has no cycles.(2)
Apply the procedure for the case of no cycles above.
Note that Step 1 will terminate, which can be shown by induction on the number of internal regions (regions which do not meet the boundary of the planar strip). Each application of Proposition4.9 reduces the number of internal regions by 1.Corollary 4.11.
Using the connecting move in addition, we can reduce the graph to a single simple tree.Proof.
It is an easy observation that when one uses the connecting move on a simple tree withm boundary lines and a simple tree with m′ boundary lines, one gets a simple tree with m+m′ boundary lines, after possibly removing extraneous dots if either m or m′ equals 1.Remark 4.12.
There are two useful sets of one-color graphs withm boundary lines, to which all others reduce. The first set just contains the simple tree with m boundary lines, and the latter is the collection of all disjoint unions of simple trees whose number of boundary lines add up to m. The former is useful because there is a single graph, so we have fewer cases to deal with. The latter is useful because it does not require the connecting move.
More importantly, these sets behave differently when we introduce polynomials into the equation. Let us assume that allm boundary lines are on the top boundary, so that we are looking at a morphism in Hom(∅,i̲) where i̲ is iiiiiiiii (m times). The following statements will not be used in this paper, and can be more easily proven after the calculation of Hom spaces.
Claim 4.13.
Consider diagrams which are a simple tree, with an arbitrary monomial in the lefthand region, and either 1 orxi in each other region. This is a basis for Hom(∅,i̲) over 𝕜.Claim 4.14.
Consider diagrams which are disjoint unions of simple trees, with an arbitrary monomial in the lefthand region, and no other polynomials. These are a spanning set forHom(∅,i̲) over 𝕜.
The second claim is easy to see, given Proposition4.10. Given a disjoint union of simple trees, with arbitrary polynomials, we may use relation (3.16) and the polynomial slides to force all the polynomials to the left, at the cost of potentially breaking some lines. This breakage is not a problem, since one can reduce again to a simple tree without adding more polynomials, using (3.10) and (3.4). We do not get a basis this way: consider the three different ways to break a line in a trivalent vertex diagram; there is a linear dependence relation between these diagrams and the trivalent vertex with a polynomial in the lefthand region.
Relations (3.25) and (3.11) essentially allow us to get from the second spanning set to the first, showing that the first is at least a spanning set. That it is a basis is immediate from counting the graded dimension of the Hom space, one we prove that the dimension of Hom spaces in 𝒟𝒞1 conforms with a certain semilinear form.The connecting move is less important than the others in the proofs, and was introduced primarily to make these remarks. It can generally be ignored below.


### 4.3. Broken One-Color Reductions

The reductions of the previous section do apply, as stated, to any one color graph. However, we would like to apply these moves to thei-colored graph of a multicolor graph, where the moves above do not extend trivially to reduction moves in 𝒟𝒞1. In this section, we quickly generalize the results of the previous section to a weaker set of moves.Definition 4.15.
Consider the following reductions for one-color graphs, which take the graph on the left and replace it with the set of graphs on the right:
We call the moves above (together with the basic moves that have no weak analog) thebroken or weak basic moves.These moves behave like the basic moves of the same name, except that they may also replace the original diagram with a broken version of itself, that is, a version with some edges broken. To distinguish the original basic moves, we may call them thestrict basic moves.What is important is that we have analogs of Propositions4.9 and 4.10, despite only being able to use weak moves.Proposition 4.16.
Consider a minimal cycle in a one-color graphΓ. Using the weak associativity, needle, dot removal, weak dot contraction, and dot extension moves, we may reduce a neighborhood of the cycle (including the inside region) to a disjoint union of simple trees.Proposition 4.17.
Using the weak associativity, needle, dot removal, weak dot contraction, and dot extension moves, one can reduce any one-color graphΓ to a disjoint union of simple trees.Of course, two distinct simple trees are no longer equivalent under the weak associativity move, but this is really irrelevant for us.Proof.
Breaking a line will never create a cycle or increase the number of trivalent vertices. Because of this, the proofs of the previous section go through almost verbatim (ignoring any statements about connected component, and occasionally replacing “a simple tree" with “a disjoint union of simple trees"). The only significant alterations that need to be made come in the proof of Proposition4.9. In Step 4 or Step 5 one may need to remove an additional double dot. In Step 2 or Step 3, weak dot contraction and weak associativity have multiple outcomes, but each outcome that does not agree with strict dot contraction or strict associativity will have broken the cycle already, allowing us to complete the proof using the no-cycle algorithm of Proposition 4.10.
Alternatively, one could also prove these statements by induction on the number of trivalent vertices. Each weak move is equivalent to a strong move modulo diagrams with fewer trivalent vertices. The only part of the proof that ever created additional trivalent vertices was the single use of dot extension in Step 5 of the proof of Proposition4.9. It is easy to see how Step 5 does not actually cause a problem, however, since after dot extension is applied, the needle move and double dot removal will do the trick in the same way regardless.Addendum 3.
The overall proof using weak one-color moves is slightly different than the treatment in previous versions of this paper, but it is cleaner and more straightforward.


### 4.4.i-Colored Moves

Now we list the moves which allow us to simplify multicolor graphs.Definition 4.18.
Consider a graphΓ whose i-graph looks like one of the pictures in the start column of Definition 4.3. Let S be the set of all graphs whose i-graph looks like the corresponding picture in the finish column. Let W be the set of all graphs whose i-graph looks like any of the corresponding pictures in the finish column of definition weakbasicmoves. The stricti-colored move replaces Γ with the set S. The weaki-colored move replaces Γ with the set W.For instance, stricti-colored associativity will replace any graph Γ whose i-graph is  with the set S of graphs whose i-graph is . This set S is enormous, for other colors can interfere, and the j-graph for some other j can be arbitrarily complicated. The i-colored vertices, seemingly trivalent, could come from 6-valent vertices in Γ. In general, an i-colored move will behave nicely on the i-graph, but may significantly complicate the full graph.Proposition 4.19.
The weaki-colored basic moves are reduction moves in 𝒟𝒞1, so long as they are applied to graphs which do not contain either the color i-1 or i+1.A colori will be called extremal for a graph Γ if it appears in Γ but either i-1 or i+1 does not appear. Clearly, any nonempty graph will have an extremal color, such as the minimal color present.The proof of this proposition is found in Section5.2, as well as more precise details on what can be done. The power of the proposition can be seen immediately:Corollary 4.20.
Any graphΓ without boundary lines can be reduced to the empty graph.Proof.
We induct on the set of colors present in the graphΓ. If no colors are present, then Γ is the empty graph and we are done. Else, choose an extremal color i. By Proposition 4.19 we may apply the weak i-colored basic moves and use Proposition 4.17 to replace every connected component of the i-graph with a disjoint union of simple trees with no boundary lines. Since a simple tree with no boundary lines is the empty set, Γ reduces to a set of graphs which do not include the color i. By induction, Γ now reduces to the empty graph.One can apply a similar procedure to a graphΓ with boundary lines. Choose an extremal color i, and reduce the i-graph to a disjoint union of simple trees, then, within each region delimited by the i-graph, the colors i+1 and i-1 are now extremal, and we can reduce those. One can repeat this procedure, however, it will not produce a very simple graph in all cases. If the color i has at least 3 boundary lines, the i-graph may have trivalent vertices, and the graph Γ itself may have 6-valent vertices in their place. These 6-valent vertices will produce more i+1 or i-1 colored boundary lines inside the regions delimited by the i-graph. Nonetheless, we have the following simple case.Corollary 4.21.
Any graph whose boundary has at most one line of each color can be reduced to a disjoint union of boundary dots.Proof.
We know we can reduce thei-graph, for i an extremal color, to a disjoint union of simple trees. A simple tree with at most one boundary line is either the empty set or a boundary dot. Therefore the i-graph is now either the empty set or a boundary dot, depending on whether or not i appears in the boundary. The dot need not be a boundary dot in the entire graph Γ, but it can encounter only 4-valent vertices en route to the boundary. Since a dot can be slid under a 4-valent vertex by relation (3.33), we may turn the dot into a boundary dot (its own connected component). The remaining connected components form a subgraph (also viewable in the planar strip) without the color i. Induction now concludes the proof.


### 4.5.ℱ1 Is Fully Faithful

In this section, modulo the proofs of previous sections which were delayed until Section5, we prove our main theorem.Theorem 4.22.
The functorF1 from 𝒟𝒞1 to 𝒮𝒞1 is an equivalence of 𝕜-linear monoidal categories with Hom spaces enriched in R-molfℤ-R.We knowF1 is a functor by Proposition 3.11, and inspection of the objects in both categories shows immediately that it is essentially surjective. To show F1 is full, we use Proposition 2.13, which motivates the next few statements.Corollary 4.23.
For any indexi, the object i in 𝒟𝒞1 is self-biadjoint. This means that for any sequences j̲ and k̲, there are natural isomorphisms Hom𝒟𝒞1(k̲,j̲i)→Hom𝒟𝒞1(k̲i,j̲) and Hom𝒟𝒞1(k̲,ij̲)→Hom𝒟𝒞1(ik̲,j̲).Proof.
The first isomorphism and its inverse are shown below. That these maps compose to be the identity is exactly the relation (3.5)
The second isomorphism and its inverse are the left-right mirror of the maps above.Note that whenk̲=∅ in the corollary above, these isomorphisms combine to yield an isomorphism Hom𝒟𝒞1(∅,j̲i)→Hom𝒟𝒞1(∅,ij̲), drawn as belowAt this point, one could construct a semilinear product on the free algebra generated bybi, i=1,…,n, via (bi̲,bj̲)=grkHom𝒟𝒞1(i̲,j̲), and bi would be self-adjoint. If we show that the Hecke algebra relations are in the kernel of this semilinear product then it will descend to the Hecke algebra. We have several methods by which we could do this.(1)
Look in𝒟𝒞2, where we have direct sums and grading shifts, and prove the isomorphisms (2.10)–(2.12).(2)
Look in the Karoubi envelope𝒟𝒞, find idempotents corresponding to the auxiliary modules in (2.13) and friends, and show those isomorphisms.(3)
Work entirely within𝒟𝒞1 and show the isomorphisms (2.12) only after applying the Hom functor. For instance, showing that Hom(ii,j̲)≅Hom(i,j̲){1}⊕Hom(i,j̲){-1} will be sufficient.All these tactics are primarily the same. We illustrate the third method, although we do explore the auxiliary modules of the second method.The relation (3.25) precisely descends to Bi⊗Bi≅Bi{1}⊕Bi{-1}. We decompose the identity of ii into the sum of two idempotents, and obtain orthogonal projections from ii to i of degrees 1 and −1, respectively,(4.2)Stated very explicitly, we have two projection mapsp1,p2:ii→i, and two inclusion maps α1, α2:i→ii, as indicated in the diagram above, which is just relation (3.25) divided in half. Include the minus sign on the right picture into the map α2, then one can quickly check p1α1=1i, p2α2=1i, p1α2=0, p2α1=0, and 1ii=α1p1+α2p2. So these must be projections to and inclusions of summands, and they are maps of the correct degree.Now, we look ati and j which are distant. We have the isomorphism Bi⊗Bj≅R⊗Ri,jR{-2}≅Bj⊗Bi. It is clear that we may construct for any k̲ isomorphisms Hom(ij,k̲)→Hom(ji,k̲) or vice versa merely by precomposing with the appropriate 4-valent vertex, and (3.32) shows that these maps are inverses.Because we can, let us discuss how we might extend our diagrammatic calculus to include additional modules fromR-molf-R, like R⊗Ri,jR{-2}. Let us (temporarily) allow a new color of line in our pictures, call it w, and extend the functor F1 so that it sends w to R⊗Ri,jR{-2}. We add new generators to our diagrammatics, and specify the image under the extended functor, as belowThe definition of these bimodule maps, and the proof that they are in fact bimodule maps, is exactly akin to the discussion in Section3.4. It is clear that composing these morphisms to get an endomorphism of ij will yield the identity map, and composing them to get an endomorphism of w will also yield the identity map (these would be relations in the extended diagrammatic calculus). Thus we get isomorphisms ij≅w≅ji in 𝒟𝒞.We now combine these techniques to deal with adjacent colors. We have isomorphismsBi⊗Bi+1⊗Bi≅Bi⊕(R⊗Ri,i+1R{-3}) and Bi+1⊗Bi⊗Bi+1≅Bi+1⊕(R⊗Ri,i+1R{-3}). If we allow the new color of line, again called w, to represent the bimodule R⊗Ri,i+1R{-3}, then we may define the following maps:Again, checking that we have well-defined bimodule maps is akin to Section3.4. Composing the two maps that go through i(i+1)i and w to get an endomorphism of w will yield the identity map of w, and the same is true, respectively, of (i+1)i(i+1).Then the equation (3.26), which is a decomposition of the identity of i(i+1)i, actually follows from this relation in 𝒟𝒞(4.3)There is a more explicit statement to be derived from this relation, completely analogous to the two-line case, with projection and inclusion mapsp1,α1,p2,α2 (include the minus sign on the right picture in α2). Similarly we get a decomposition of (i+1)i(i+1) via the same relation with the colors switched. The auxiliary module used here is in fact the indecomposable Soergel bimodule Bw where w=sisi+1si=si+1sisi+1.To state the result without extending the calculus to the Karoubi envelope, one may merely observe that for anyk̲ there is a map Hom(i(i+1)i,k̲)→Hom((i+1)i(i+1),k̲) and vice versa given by precomposing with the appropriate 6-valent vertex; there is another map Hom(i(i+1)i,k̲)→Hom(i,k̲) given by precomposing with α2, and a map backwards given by precomposing with p2, then (3.26) exactly yields that Hom(i(i+1)i,k̲)⊕Hom((i+1),k̲)≅Hom((i+1)i(i+1),k̲)⊕Hom(i,k̲).Thus we have shown the following claim:Claim 4.24.
The isomorphisms (2.10) through (2.12) hold in 𝒟𝒞1 after applying any Hom functor.We have now satisfied the requirements of Proposition2.13, which implies the fullness of F1.Claim 4.25.
The functorF1 is full.Finally, our graphical reductions give us a classification of certain Hom spaces.Corollary 4.26.
The spaceHom𝒟𝒞1(∅,i̲), where i̲ is a length d increasing sequence, is a free left (or right) R-module of rank 1, generated by a homogeneous morphism of degree d.Proof.
Letφ be the morphism consisting entirely of boundary dots. This corresponds, under the functor, to the generator of degree d discussed in Claim 2.9. By Corollary 4.21, φ viewed as a graph underlies every morphism in 𝒟𝒞1. This graph has a single region, so any morphism that it underlies will be generated by φ under the action of R on the right or left, which puts a polynomial into that single region. This gives a surjective map from R to the Hom space. After applying F1, we know that the morphisms must surject onto Hom𝒮𝒞1(R,Bi̲), which is a free R-module (see Claim 2.9). Therefore, the Hom space in 𝒟𝒞1 must also be free.Corollary 4.27.
The semilinear form onH induced by Hom spaces in 𝒟𝒞1 agrees with the form defined in Section 2.1, so it agrees with the form induced by 𝒮𝒞1. Therefore F1 is faithful.Proof.
This is now immediate, from Remark2.1.In conclusion,F1 is an equivalence of categories, and Theorem 4.22 is proven.We also get for free the following corollary, which is difficult to prove purely diagrammatically.Corollary 4.28.
Hom spaces in𝒟𝒞1 are free as left or right R-modules.Remark 4.29.
It is worth reiterating what is proven diagrammatically, and what is proven using the functorF1 to Soergel's category. Diagrammatically, we can prove Proposition 4.19 and Corollary 4.21, which implies that R surjects onto Hom𝒟𝒞1(∅,i̲) for i̲ increasing. However, without the full functor F1 and the nondiagrammatic knowledge of Hom spaces in Soergel's category, we do not know how to prove that the Hom space is free. We do not have a fully diagrammatic proof that the Hom spaces in 𝒟𝒞1 are what they are, we only have a diagrammatic proof of an upper bound on the size of the Hom spaces.


### 4.6. Thee1 Quotient

In the remainder of this chapter, we provide some sketched statements about generalizations and variations of𝒟𝒞1. We do not use these results elsewhere in the paper, and while the proofs are only sketched, they are fairly obvious and can be fleshed out without too much work.As described in Remark2.2, one usually constructs Soergel bimodules with respect to the n-dimensional fundamental or geometric representation, instead of the n+1-dimensional standard representation. This amounts to working over the ring R1=𝕜[x1,x2,…,xn+1]/(x1+x2+⋯+xn+1), which is a quotient of R by the first elementary symmetric function e1. Since e1 is symmetric, it is in the center of the category 𝒟𝒞1 (it slides freely under all lines, tensor-commuting with all morphisms), and one may easily take the quotient category, setting e1=0, without changing any of the diagrammatics. There is a functor from this quotient category to the appropriate category of Soergel bimodules in R1-molf-R1, which is an equivalence of categories, so this diagrammatical quotient category also categorifies the Hecke algebra.One advantage to passing to the quotiente1=0 is that, after inverting a suitable integer, we may remove the boxes from our list of generators. According to relation (3.17), the double dot colored i is equal to xi-xi+1. Thus linear combinations of double dots of colors i=1,…,n will give us the 𝕜-span of x1-x2,x2-x3,… inside the space of linear polynomials (these are the simple roots). This span will not include xi in R, which is why we require at least one box as an additional generator. However, it is easy to check that, if n+1 is invertible in 𝕜, then xi is in the 𝕜-span after passing to the quotient R1. As an example, when n=1, the double dot is equal to x1-x2, and passing to x1+x2=0, we get x1=(1/2)(x1-x2). Thus, if n+1 is invertible in 𝕜, one can eliminate boxes from the quotient calculus altogether, replacing them with linear combinations of double dots.Addendum 4.
All the relations which involve boxes can be rewritten so that they only involve double dots. This is not done here, but can be found in any of the papers [33, 34, 36].Replacing boxes with double dots is much more natural, since it emphasizes that the boxes themselves should have a color, and that the set of polynomials depends in a natural way upon the coxeter groupSn+1. Viewing them as boxes may help make the proofs in this paper more intuitive, however.


### 4.7. Color Elimination

We have already shown that𝒟𝒞1≅𝒮𝒞1, without needing to investigate in depth any morphisms except those from ∅ to i̲ an increasing sequence. Because this pins down the size of all Hom spaces, we can deduce some additional facts about general morphisms. The following result is not used elsewhere in this paper, but may come in handy when constructing the analogous category for arbitrary Coxeter systems.Proposition 4.30.
LetΓ be a graph where the color j does not appear in the boundary, then Γ can be reduced to graphs not containing the color j at all.We can already show this whenj is extremal, since by Proposition 4.19 we may apply the weak j-colored basic moves and reduce the color j to the empty graph. Unfortunately, as in Remark 4.29, we do not have a diagrammatic result of this proposition in general, but use the known size of Hom spaces to prove it.ForX⊂{1,…,n}, (i.e., for a Coxeter subgraph of An) we let 𝒟𝒞1[X] be the category defined analogously but where edges can only be labelled by colors in X. If colors which do not appear on the boundary are not needed in the graph after reduction, then the natural inclusion of 𝒟𝒞1[X] into 𝒟𝒞1 is fully faithful, which one would expect. The full faithfulness of this inclusion is equivalent to the above proposition.However, as discussed in the previous section, the boxes which are allowed to appear should also depend onX. For the rest of this section, we assume we are working in the e1 quotient. Let 𝒟𝒞1(X) be the category defined analogously, where edges are labelled in X, and where the only polynomials appearing are in the subring R(X) generated by double dots colored in X. This is really the category we should look at. Given a morphism in 𝒟𝒞1[X], we can use polynomial forcing rules to guarantee that the only polynomials not in R(X) appear in the lefthand region. We do not prove it here, 𝒟𝒞1[X] is simply 𝒟𝒞1(X)⊗R(X)R; that is, the objects are unchanged, and morphism spaces undergo base change.Proposition 4.31.
LetX be a Coxeter subgraph of An, and let W(X), H(X), 𝒮𝒞1(X) designate the corresponding constructions for this Coxeter graph, then there is a functor F1(X) from 𝒟𝒞1(X) to 𝒮𝒞1(X) which is an equivalence of categories.Proof.
We will only sketch this result. The setX will be a disjoint union of various subgraphs Xl, each isomorphic to Aml for some ml≤n. For each Xl we know that 𝒟𝒞1(Xl)≅𝒮𝒞1(Xl), and we have all the results aforementioned. Moreover, for any l≠l′ and objects M∈𝒟𝒞1(Xl) and N∈𝒟𝒞1(Xl′), we have natural isomorphisms M⊗N≅N⊗M constructed with 4-valent crossings. Thanks to the distant sliding rules, these natural isomorphisms commute in the proper way with all morphisms in 𝒟𝒞1(Xl) or 𝒟𝒞1(Xl′). The category 𝒟𝒞1(X) can be constructed via some universal “symmetric monoidal product" construction, by taking the product over the categories 𝒟𝒞1(Xl). The same holds true for 𝒮𝒞1(X), which will yield the result.Given the sketchy result above, we can calculate the rank of Hom spaces in𝒟𝒞1(X) by using the standard trace map on H(X). This trace map commutes with the standard trace on H under the inclusion H(X)⊂H. Thus we see that, for objects i̲ and j̲ in 𝒟𝒞1(X), the space Hom𝒟𝒞1(i̲,j̲) is a free R module of some rank r, and the space Hom𝒟𝒞1(X)(i̲,j̲) is a free R(X) module of the same rank r. Therefore Hom𝒟𝒞1[X](i̲,j̲) is a free R module of rank r as well, and the inclusion of 𝒟𝒞1[X] in 𝒟𝒞1 is fully faithful.We quickly sketch an alternative proof of Proposition4.30, which assumes that we know that Hom spaces in 𝒟𝒞1 conform to the standard trace. We can think of any graph with boundary as a morphism in 𝒟𝒞1 from ∅ to j̲. We have already “inductively calculated” the space of such morphisms, along the lines of Remark 2.1 and Proposition 2.13. Namely, if j̲ has no repeated colors, then every morphism is a polynomial with boundary dots. If j̲ has repeated colors, we use idempotent decompositions to consider the Hom space as the sum of the Hom spaces of its summands, or apply biadjunction to cycle the sequence j̲, until we have expressed the Hom space in terms of Hom(∅,k̲) for various k̲ nonrepeating. Since neither biadjunctions nor idempotent decompositions add any new colors to the graph, we have just constructed a generating set of morphisms in a way which does not involve any colors which were not in j̲ to begin with.


## 4.1. Terminology

We will spend the next few sections classifying the homomorphisms in𝒟𝒞1. For many of the results, proofs will be postponed until Section 5.2.We will we using the fact, extensively discussed in the previous sections, that a morphism can be viewed unambiguously as an isotopy class of graphs with polynomials in the regions (or rather, a linear combination of these). Henceforth, the termgraph only refers to colored finite graphs with boundary (embedded in the planar strip) which can be constructed out of univalent, trivalent, 4-valent, and 6-valent vertices as above. Remember that these graphs do have edges which run to the boundary, which we call boundary lines, and may have edges which meet neither the boundary nor any vertex, and thus must necessarily form a circle. We say a graph has a boundary if it has at least one boundary line. A graph divides the planar strip into regions, and there are two distinguished regions: the lefthand and righthand regions, which contain -∞ and ∞, respectively.We call aboundary dot any connected component of a graph which consists entirely of an edge starting at the boundary and ending in a dot. We call a double dot any connected component of a graph which consists entirely of an edge with a dot on both ends. Cutting an edge in a diagram and replacing it with two dots we call breaking the edge (see, for instance, relation (3.16)).Given a setS of graphs and a morphism φ in 𝒟𝒞1, we say that S  underliesφ if φ can be written as a linear combination of morphisms, each of which is given by a graph Γ∈S with polynomials in regions. We say that a graph Γreduces to S if S underlies every morphism that Γ underlies. Clearly reduction is transitive, in that if Γ reduces to S, and every graph in S reduces to S′, then Γ reduces to S′. Our goal will be to find a nice set of graphs to which all other graphs reduce. We will do this by finding reduction moves, which are local moves on graphs, sending a graph to a set of graphs to which it reduces.Example 4.1.
The relation (3.25) implies that  reduces to . In other words,  underlies both the terms on the right side of (3.25). This can be applied as a local reduction move within any graph.LetT be a subset of {1,…,n}. The T-graph of a graph will be the subgraph consisting of all edges colored i for i∈T. Some 6-valent vertices in the original graph may become trivalent vertices in the T-graph. Similarly, some 4-valent vertices in the original graph may become 2-valent vertices in the T-graph, which we ignore, connecting the incoming edges into a single edge. The T-graph is itself a graph by our above definition. Most often we will just consider the i-graph for a single color (i.e., T={i}). Typically, our reduction moves will be designed to simplify the i-graph for a particular i, allowing us to simplify the graph one color at a time.Remark 4.2.
The rest of this paper will have numerous calculations, but they will mostly be calculations with the underlying graphs, not keeping track of polynomials, so they do not reflect how morphisms actually behave in𝒟𝒞1. For lots of examples of computations in the graphical calculus, see [33].


## 4.2. One Color Reductions

In this section, we assume all graphs consist of a single colori.Definition 4.3.
Consider the following “moves", or transformations. They take a subdiagram looking like Start, and replace that subdiagram with Finish. We call these thebasic moves.Remember, these are moves on graphs, not graphs with polynomials. Note that the needle move, by adding a dot on the bottom, yields a reduction from the circle to a double dot. The only moves which change the connectivity of a graph are double dot removal, which deletes a connected component, and the connecting move, which has the potential to link two components into one.Claim 4.4.
All of these moves are reduction moves in𝒟𝒞1.Proof.
The associativity move follows from (3.10). That is, even if there are polynomials in the regions of the graph, the relation (3.10) can still be applied. These polynomials, being in external regions, do not interfere with the application of relations. Similarly, dot contraction/extension follow from (3.4), dot removal follows from (3.17), and the connecting move follows from (3.25).
The needle move remains. Suppose we have an arbitrary polynomialf in the eye of the needle. We may use (3.24), generalizing (3.19), to replace the diagram with a dot accompanied by ∂i(f).The following example of reduction should be familiar.Example 4.5.
In order, this is done with associativity, associativity, needle, and dot contraction moves.Example 4.6.
This is meant to indicate an arbitrary length cycle of this form, and reduction is done with associativity, needle, and dot contraction moves.Definition 4.7.
Asimple treeT with m boundary lines is a connected one-color graph with boundary, whose form depends on m: (1)
ifm≥2, then T is a trivalent tree with m-2 vertices connecting all the boundary lines. Note that any two such trees are equivalent under the associativity move;(2)
ifm=1, then T is a single boundary dot;(3)
ifm=0, then T is the empty graph.Definition 4.8.
Acycle in a one-color graph is either a circle or a path from a vertex to itself which does not repeat any edges. Any cycle splits the plane into two parts, the inside and outside of the cycle. A cycle is minimal if the inside of the cycle consists of a single region.By counting vertices, it is clear that any connected purely trivalent graph with no cycles is a simple tree. Any graph with a cycle has a minimal cycle.We will now give a precise inductive algorithm to reduce a graph to a disjoint union of simple trees, by reducing minimal cycles.Proposition 4.9.
Consider a minimal cycle in a one-color graphΓ. Using the associativity, needle, dot removal, and dot contraction/extension moves, we may reduce a neighborhood of the cycle (including the inside region) to a simple tree (see (4.1)).(4.1)Proposition 4.10.
Using the associativity, needle, dot removal and dot contraction/extension moves, one can reduce any one-color graphΓ to a disjoint union of simple trees. During this process, each component with no boundary lines will be replaced with the empty graph, and after this is done, no further connected components are created or destroyed or merged.We prove both propositions together, in several steps.Proof of Proposition4.10 for a Graph with No Cycles.
Suppose there are no cycles inΓ. If there is a dot, the edge coming from that dot must connect to either the boundary, another dot, or a trivalent vertex. Our simplification algorithm is as follows. (1)
Remove any dot connected to a trivalent vertex, using dot contraction. Repeat Step 1 until no such dots remain. This does not alter the connected components.(2)
Replace any double dot with the empty set, using double dot removal. Because Step 1 did not alter the connected components, this could only be applied to double dots which arose from components which had no boundary lines.
Boundary dots are in their own connected component. Any other connected component is purely trivalent and has no cycles, so it must be a simple tree.Proof of Proposition4.9, Assuming Proposition 4.10 for Graphs with No Cycles.
Letγ denote a minimal cycle of Γ. Consider a neighborhood of γ in Γ, and let Γ′ be the subgraph consisting of the interior of the cycle, as in (4.1). Let us call the boundary lines of Γ′spokes, since they run into γ from the inside, like spokes hitting the wheel of a bicycle. Now Γ′ may not have any cycles, or else γ would not be a minimal cycle. Moreover, the spokes of Γ′ must be in distinct connected components of Γ′, or else they would create additional regions and γ would not be a minimal cycle. Our simplification algorithm is as follows: (1)
Apply Proposition4.10 to Γ′, replacing Γ′ with a disjoint union of boundary dots, one for each spoke.(2)
Use dot contraction to remove all the spokes. We are now in the situation of Example4.6.(3)
Apply associativity as in Example4.5, reducing the length of γ by one. Repeat until γ is a needle or a circle.(4)
Ifγ is a needle, apply the needle move to replace it with a dot. If associativity moves were performed in Step 3, use dot contraction to contract this dot into one of the trivalent vertices, as in Example 4.5.(5)
Ifγ is a circle, apply dot extension to replace it with a needle attached to a dot, then apply needle reduction to obtain a double dot, and double dot removal to obtain the empty graph.
It is a simple observation that the result of this procedure is a simple tree, and that the only alteration of connected components which occurred was the removal of components which had no boundary lines to begin with.Proof of Proposition4.10 in the General Case.
Suppose we have an arbitrary graphΓ. Our simplification algorithm is as follows: (1)
IfΓ has a cycle, apply Proposition 4.9 to replace its neighborhood with a simple tree. Repeat this process until Γ has no cycles.(2)
Apply the procedure for the case of no cycles above.
Note that Step 1 will terminate, which can be shown by induction on the number of internal regions (regions which do not meet the boundary of the planar strip). Each application of Proposition4.9 reduces the number of internal regions by 1.Corollary 4.11.
Using the connecting move in addition, we can reduce the graph to a single simple tree.Proof.
It is an easy observation that when one uses the connecting move on a simple tree withm boundary lines and a simple tree with m′ boundary lines, one gets a simple tree with m+m′ boundary lines, after possibly removing extraneous dots if either m or m′ equals 1.Remark 4.12.
There are two useful sets of one-color graphs withm boundary lines, to which all others reduce. The first set just contains the simple tree with m boundary lines, and the latter is the collection of all disjoint unions of simple trees whose number of boundary lines add up to m. The former is useful because there is a single graph, so we have fewer cases to deal with. The latter is useful because it does not require the connecting move.
More importantly, these sets behave differently when we introduce polynomials into the equation. Let us assume that allm boundary lines are on the top boundary, so that we are looking at a morphism in Hom(∅,i̲) where i̲ is iiiiiiiii (m times). The following statements will not be used in this paper, and can be more easily proven after the calculation of Hom spaces.
Claim 4.13.
Consider diagrams which are a simple tree, with an arbitrary monomial in the lefthand region, and either 1 orxi in each other region. This is a basis for Hom(∅,i̲) over 𝕜.Claim 4.14.
Consider diagrams which are disjoint unions of simple trees, with an arbitrary monomial in the lefthand region, and no other polynomials. These are a spanning set forHom(∅,i̲) over 𝕜.
The second claim is easy to see, given Proposition4.10. Given a disjoint union of simple trees, with arbitrary polynomials, we may use relation (3.16) and the polynomial slides to force all the polynomials to the left, at the cost of potentially breaking some lines. This breakage is not a problem, since one can reduce again to a simple tree without adding more polynomials, using (3.10) and (3.4). We do not get a basis this way: consider the three different ways to break a line in a trivalent vertex diagram; there is a linear dependence relation between these diagrams and the trivalent vertex with a polynomial in the lefthand region.
Relations (3.25) and (3.11) essentially allow us to get from the second spanning set to the first, showing that the first is at least a spanning set. That it is a basis is immediate from counting the graded dimension of the Hom space, one we prove that the dimension of Hom spaces in 𝒟𝒞1 conforms with a certain semilinear form.The connecting move is less important than the others in the proofs, and was introduced primarily to make these remarks. It can generally be ignored below.


## 4.3. Broken One-Color Reductions

The reductions of the previous section do apply, as stated, to any one color graph. However, we would like to apply these moves to thei-colored graph of a multicolor graph, where the moves above do not extend trivially to reduction moves in 𝒟𝒞1. In this section, we quickly generalize the results of the previous section to a weaker set of moves.Definition 4.15.
Consider the following reductions for one-color graphs, which take the graph on the left and replace it with the set of graphs on the right:
We call the moves above (together with the basic moves that have no weak analog) thebroken or weak basic moves.These moves behave like the basic moves of the same name, except that they may also replace the original diagram with a broken version of itself, that is, a version with some edges broken. To distinguish the original basic moves, we may call them thestrict basic moves.What is important is that we have analogs of Propositions4.9 and 4.10, despite only being able to use weak moves.Proposition 4.16.
Consider a minimal cycle in a one-color graphΓ. Using the weak associativity, needle, dot removal, weak dot contraction, and dot extension moves, we may reduce a neighborhood of the cycle (including the inside region) to a disjoint union of simple trees.Proposition 4.17.
Using the weak associativity, needle, dot removal, weak dot contraction, and dot extension moves, one can reduce any one-color graphΓ to a disjoint union of simple trees.Of course, two distinct simple trees are no longer equivalent under the weak associativity move, but this is really irrelevant for us.Proof.
Breaking a line will never create a cycle or increase the number of trivalent vertices. Because of this, the proofs of the previous section go through almost verbatim (ignoring any statements about connected component, and occasionally replacing “a simple tree" with “a disjoint union of simple trees"). The only significant alterations that need to be made come in the proof of Proposition4.9. In Step 4 or Step 5 one may need to remove an additional double dot. In Step 2 or Step 3, weak dot contraction and weak associativity have multiple outcomes, but each outcome that does not agree with strict dot contraction or strict associativity will have broken the cycle already, allowing us to complete the proof using the no-cycle algorithm of Proposition 4.10.
Alternatively, one could also prove these statements by induction on the number of trivalent vertices. Each weak move is equivalent to a strong move modulo diagrams with fewer trivalent vertices. The only part of the proof that ever created additional trivalent vertices was the single use of dot extension in Step 5 of the proof of Proposition4.9. It is easy to see how Step 5 does not actually cause a problem, however, since after dot extension is applied, the needle move and double dot removal will do the trick in the same way regardless.Addendum 3.
The overall proof using weak one-color moves is slightly different than the treatment in previous versions of this paper, but it is cleaner and more straightforward.


## 4.4.i-Colored Moves

Now we list the moves which allow us to simplify multicolor graphs.Definition 4.18.
Consider a graphΓ whose i-graph looks like one of the pictures in the start column of Definition 4.3. Let S be the set of all graphs whose i-graph looks like the corresponding picture in the finish column. Let W be the set of all graphs whose i-graph looks like any of the corresponding pictures in the finish column of definition weakbasicmoves. The stricti-colored move replaces Γ with the set S. The weaki-colored move replaces Γ with the set W.For instance, stricti-colored associativity will replace any graph Γ whose i-graph is  with the set S of graphs whose i-graph is . This set S is enormous, for other colors can interfere, and the j-graph for some other j can be arbitrarily complicated. The i-colored vertices, seemingly trivalent, could come from 6-valent vertices in Γ. In general, an i-colored move will behave nicely on the i-graph, but may significantly complicate the full graph.Proposition 4.19.
The weaki-colored basic moves are reduction moves in 𝒟𝒞1, so long as they are applied to graphs which do not contain either the color i-1 or i+1.A colori will be called extremal for a graph Γ if it appears in Γ but either i-1 or i+1 does not appear. Clearly, any nonempty graph will have an extremal color, such as the minimal color present.The proof of this proposition is found in Section5.2, as well as more precise details on what can be done. The power of the proposition can be seen immediately:Corollary 4.20.
Any graphΓ without boundary lines can be reduced to the empty graph.Proof.
We induct on the set of colors present in the graphΓ. If no colors are present, then Γ is the empty graph and we are done. Else, choose an extremal color i. By Proposition 4.19 we may apply the weak i-colored basic moves and use Proposition 4.17 to replace every connected component of the i-graph with a disjoint union of simple trees with no boundary lines. Since a simple tree with no boundary lines is the empty set, Γ reduces to a set of graphs which do not include the color i. By induction, Γ now reduces to the empty graph.One can apply a similar procedure to a graphΓ with boundary lines. Choose an extremal color i, and reduce the i-graph to a disjoint union of simple trees, then, within each region delimited by the i-graph, the colors i+1 and i-1 are now extremal, and we can reduce those. One can repeat this procedure, however, it will not produce a very simple graph in all cases. If the color i has at least 3 boundary lines, the i-graph may have trivalent vertices, and the graph Γ itself may have 6-valent vertices in their place. These 6-valent vertices will produce more i+1 or i-1 colored boundary lines inside the regions delimited by the i-graph. Nonetheless, we have the following simple case.Corollary 4.21.
Any graph whose boundary has at most one line of each color can be reduced to a disjoint union of boundary dots.Proof.
We know we can reduce thei-graph, for i an extremal color, to a disjoint union of simple trees. A simple tree with at most one boundary line is either the empty set or a boundary dot. Therefore the i-graph is now either the empty set or a boundary dot, depending on whether or not i appears in the boundary. The dot need not be a boundary dot in the entire graph Γ, but it can encounter only 4-valent vertices en route to the boundary. Since a dot can be slid under a 4-valent vertex by relation (3.33), we may turn the dot into a boundary dot (its own connected component). The remaining connected components form a subgraph (also viewable in the planar strip) without the color i. Induction now concludes the proof.


## 4.5.ℱ1 Is Fully Faithful

In this section, modulo the proofs of previous sections which were delayed until Section5, we prove our main theorem.Theorem 4.22.
The functorF1 from 𝒟𝒞1 to 𝒮𝒞1 is an equivalence of 𝕜-linear monoidal categories with Hom spaces enriched in R-molfℤ-R.We knowF1 is a functor by Proposition 3.11, and inspection of the objects in both categories shows immediately that it is essentially surjective. To show F1 is full, we use Proposition 2.13, which motivates the next few statements.Corollary 4.23.
For any indexi, the object i in 𝒟𝒞1 is self-biadjoint. This means that for any sequences j̲ and k̲, there are natural isomorphisms Hom𝒟𝒞1(k̲,j̲i)→Hom𝒟𝒞1(k̲i,j̲) and Hom𝒟𝒞1(k̲,ij̲)→Hom𝒟𝒞1(ik̲,j̲).Proof.
The first isomorphism and its inverse are shown below. That these maps compose to be the identity is exactly the relation (3.5)
The second isomorphism and its inverse are the left-right mirror of the maps above.Note that whenk̲=∅ in the corollary above, these isomorphisms combine to yield an isomorphism Hom𝒟𝒞1(∅,j̲i)→Hom𝒟𝒞1(∅,ij̲), drawn as belowAt this point, one could construct a semilinear product on the free algebra generated bybi, i=1,…,n, via (bi̲,bj̲)=grkHom𝒟𝒞1(i̲,j̲), and bi would be self-adjoint. If we show that the Hecke algebra relations are in the kernel of this semilinear product then it will descend to the Hecke algebra. We have several methods by which we could do this.(1)
Look in𝒟𝒞2, where we have direct sums and grading shifts, and prove the isomorphisms (2.10)–(2.12).(2)
Look in the Karoubi envelope𝒟𝒞, find idempotents corresponding to the auxiliary modules in (2.13) and friends, and show those isomorphisms.(3)
Work entirely within𝒟𝒞1 and show the isomorphisms (2.12) only after applying the Hom functor. For instance, showing that Hom(ii,j̲)≅Hom(i,j̲){1}⊕Hom(i,j̲){-1} will be sufficient.All these tactics are primarily the same. We illustrate the third method, although we do explore the auxiliary modules of the second method.The relation (3.25) precisely descends to Bi⊗Bi≅Bi{1}⊕Bi{-1}. We decompose the identity of ii into the sum of two idempotents, and obtain orthogonal projections from ii to i of degrees 1 and −1, respectively,(4.2)Stated very explicitly, we have two projection mapsp1,p2:ii→i, and two inclusion maps α1, α2:i→ii, as indicated in the diagram above, which is just relation (3.25) divided in half. Include the minus sign on the right picture into the map α2, then one can quickly check p1α1=1i, p2α2=1i, p1α2=0, p2α1=0, and 1ii=α1p1+α2p2. So these must be projections to and inclusions of summands, and they are maps of the correct degree.Now, we look ati and j which are distant. We have the isomorphism Bi⊗Bj≅R⊗Ri,jR{-2}≅Bj⊗Bi. It is clear that we may construct for any k̲ isomorphisms Hom(ij,k̲)→Hom(ji,k̲) or vice versa merely by precomposing with the appropriate 4-valent vertex, and (3.32) shows that these maps are inverses.Because we can, let us discuss how we might extend our diagrammatic calculus to include additional modules fromR-molf-R, like R⊗Ri,jR{-2}. Let us (temporarily) allow a new color of line in our pictures, call it w, and extend the functor F1 so that it sends w to R⊗Ri,jR{-2}. We add new generators to our diagrammatics, and specify the image under the extended functor, as belowThe definition of these bimodule maps, and the proof that they are in fact bimodule maps, is exactly akin to the discussion in Section3.4. It is clear that composing these morphisms to get an endomorphism of ij will yield the identity map, and composing them to get an endomorphism of w will also yield the identity map (these would be relations in the extended diagrammatic calculus). Thus we get isomorphisms ij≅w≅ji in 𝒟𝒞.We now combine these techniques to deal with adjacent colors. We have isomorphismsBi⊗Bi+1⊗Bi≅Bi⊕(R⊗Ri,i+1R{-3}) and Bi+1⊗Bi⊗Bi+1≅Bi+1⊕(R⊗Ri,i+1R{-3}). If we allow the new color of line, again called w, to represent the bimodule R⊗Ri,i+1R{-3}, then we may define the following maps:Again, checking that we have well-defined bimodule maps is akin to Section3.4. Composing the two maps that go through i(i+1)i and w to get an endomorphism of w will yield the identity map of w, and the same is true, respectively, of (i+1)i(i+1).Then the equation (3.26), which is a decomposition of the identity of i(i+1)i, actually follows from this relation in 𝒟𝒞(4.3)There is a more explicit statement to be derived from this relation, completely analogous to the two-line case, with projection and inclusion mapsp1,α1,p2,α2 (include the minus sign on the right picture in α2). Similarly we get a decomposition of (i+1)i(i+1) via the same relation with the colors switched. The auxiliary module used here is in fact the indecomposable Soergel bimodule Bw where w=sisi+1si=si+1sisi+1.To state the result without extending the calculus to the Karoubi envelope, one may merely observe that for anyk̲ there is a map Hom(i(i+1)i,k̲)→Hom((i+1)i(i+1),k̲) and vice versa given by precomposing with the appropriate 6-valent vertex; there is another map Hom(i(i+1)i,k̲)→Hom(i,k̲) given by precomposing with α2, and a map backwards given by precomposing with p2, then (3.26) exactly yields that Hom(i(i+1)i,k̲)⊕Hom((i+1),k̲)≅Hom((i+1)i(i+1),k̲)⊕Hom(i,k̲).Thus we have shown the following claim:Claim 4.24.
The isomorphisms (2.10) through (2.12) hold in 𝒟𝒞1 after applying any Hom functor.We have now satisfied the requirements of Proposition2.13, which implies the fullness of F1.Claim 4.25.
The functorF1 is full.Finally, our graphical reductions give us a classification of certain Hom spaces.Corollary 4.26.
The spaceHom𝒟𝒞1(∅,i̲), where i̲ is a length d increasing sequence, is a free left (or right) R-module of rank 1, generated by a homogeneous morphism of degree d.Proof.
Letφ be the morphism consisting entirely of boundary dots. This corresponds, under the functor, to the generator of degree d discussed in Claim 2.9. By Corollary 4.21, φ viewed as a graph underlies every morphism in 𝒟𝒞1. This graph has a single region, so any morphism that it underlies will be generated by φ under the action of R on the right or left, which puts a polynomial into that single region. This gives a surjective map from R to the Hom space. After applying F1, we know that the morphisms must surject onto Hom𝒮𝒞1(R,Bi̲), which is a free R-module (see Claim 2.9). Therefore, the Hom space in 𝒟𝒞1 must also be free.Corollary 4.27.
The semilinear form onH induced by Hom spaces in 𝒟𝒞1 agrees with the form defined in Section 2.1, so it agrees with the form induced by 𝒮𝒞1. Therefore F1 is faithful.Proof.
This is now immediate, from Remark2.1.In conclusion,F1 is an equivalence of categories, and Theorem 4.22 is proven.We also get for free the following corollary, which is difficult to prove purely diagrammatically.Corollary 4.28.
Hom spaces in𝒟𝒞1 are free as left or right R-modules.Remark 4.29.
It is worth reiterating what is proven diagrammatically, and what is proven using the functorF1 to Soergel's category. Diagrammatically, we can prove Proposition 4.19 and Corollary 4.21, which implies that R surjects onto Hom𝒟𝒞1(∅,i̲) for i̲ increasing. However, without the full functor F1 and the nondiagrammatic knowledge of Hom spaces in Soergel's category, we do not know how to prove that the Hom space is free. We do not have a fully diagrammatic proof that the Hom spaces in 𝒟𝒞1 are what they are, we only have a diagrammatic proof of an upper bound on the size of the Hom spaces.


## 4.6. Thee1 Quotient

In the remainder of this chapter, we provide some sketched statements about generalizations and variations of𝒟𝒞1. We do not use these results elsewhere in the paper, and while the proofs are only sketched, they are fairly obvious and can be fleshed out without too much work.As described in Remark2.2, one usually constructs Soergel bimodules with respect to the n-dimensional fundamental or geometric representation, instead of the n+1-dimensional standard representation. This amounts to working over the ring R1=𝕜[x1,x2,…,xn+1]/(x1+x2+⋯+xn+1), which is a quotient of R by the first elementary symmetric function e1. Since e1 is symmetric, it is in the center of the category 𝒟𝒞1 (it slides freely under all lines, tensor-commuting with all morphisms), and one may easily take the quotient category, setting e1=0, without changing any of the diagrammatics. There is a functor from this quotient category to the appropriate category of Soergel bimodules in R1-molf-R1, which is an equivalence of categories, so this diagrammatical quotient category also categorifies the Hecke algebra.One advantage to passing to the quotiente1=0 is that, after inverting a suitable integer, we may remove the boxes from our list of generators. According to relation (3.17), the double dot colored i is equal to xi-xi+1. Thus linear combinations of double dots of colors i=1,…,n will give us the 𝕜-span of x1-x2,x2-x3,… inside the space of linear polynomials (these are the simple roots). This span will not include xi in R, which is why we require at least one box as an additional generator. However, it is easy to check that, if n+1 is invertible in 𝕜, then xi is in the 𝕜-span after passing to the quotient R1. As an example, when n=1, the double dot is equal to x1-x2, and passing to x1+x2=0, we get x1=(1/2)(x1-x2). Thus, if n+1 is invertible in 𝕜, one can eliminate boxes from the quotient calculus altogether, replacing them with linear combinations of double dots.Addendum 4.
All the relations which involve boxes can be rewritten so that they only involve double dots. This is not done here, but can be found in any of the papers [33, 34, 36].Replacing boxes with double dots is much more natural, since it emphasizes that the boxes themselves should have a color, and that the set of polynomials depends in a natural way upon the coxeter groupSn+1. Viewing them as boxes may help make the proofs in this paper more intuitive, however.


## 4.7. Color Elimination

We have already shown that𝒟𝒞1≅𝒮𝒞1, without needing to investigate in depth any morphisms except those from ∅ to i̲ an increasing sequence. Because this pins down the size of all Hom spaces, we can deduce some additional facts about general morphisms. The following result is not used elsewhere in this paper, but may come in handy when constructing the analogous category for arbitrary Coxeter systems.Proposition 4.30.
LetΓ be a graph where the color j does not appear in the boundary, then Γ can be reduced to graphs not containing the color j at all.We can already show this whenj is extremal, since by Proposition 4.19 we may apply the weak j-colored basic moves and reduce the color j to the empty graph. Unfortunately, as in Remark 4.29, we do not have a diagrammatic result of this proposition in general, but use the known size of Hom spaces to prove it.ForX⊂{1,…,n}, (i.e., for a Coxeter subgraph of An) we let 𝒟𝒞1[X] be the category defined analogously but where edges can only be labelled by colors in X. If colors which do not appear on the boundary are not needed in the graph after reduction, then the natural inclusion of 𝒟𝒞1[X] into 𝒟𝒞1 is fully faithful, which one would expect. The full faithfulness of this inclusion is equivalent to the above proposition.However, as discussed in the previous section, the boxes which are allowed to appear should also depend onX. For the rest of this section, we assume we are working in the e1 quotient. Let 𝒟𝒞1(X) be the category defined analogously, where edges are labelled in X, and where the only polynomials appearing are in the subring R(X) generated by double dots colored in X. This is really the category we should look at. Given a morphism in 𝒟𝒞1[X], we can use polynomial forcing rules to guarantee that the only polynomials not in R(X) appear in the lefthand region. We do not prove it here, 𝒟𝒞1[X] is simply 𝒟𝒞1(X)⊗R(X)R; that is, the objects are unchanged, and morphism spaces undergo base change.Proposition 4.31.
LetX be a Coxeter subgraph of An, and let W(X), H(X), 𝒮𝒞1(X) designate the corresponding constructions for this Coxeter graph, then there is a functor F1(X) from 𝒟𝒞1(X) to 𝒮𝒞1(X) which is an equivalence of categories.Proof.
We will only sketch this result. The setX will be a disjoint union of various subgraphs Xl, each isomorphic to Aml for some ml≤n. For each Xl we know that 𝒟𝒞1(Xl)≅𝒮𝒞1(Xl), and we have all the results aforementioned. Moreover, for any l≠l′ and objects M∈𝒟𝒞1(Xl) and N∈𝒟𝒞1(Xl′), we have natural isomorphisms M⊗N≅N⊗M constructed with 4-valent crossings. Thanks to the distant sliding rules, these natural isomorphisms commute in the proper way with all morphisms in 𝒟𝒞1(Xl) or 𝒟𝒞1(Xl′). The category 𝒟𝒞1(X) can be constructed via some universal “symmetric monoidal product" construction, by taking the product over the categories 𝒟𝒞1(Xl). The same holds true for 𝒮𝒞1(X), which will yield the result.Given the sketchy result above, we can calculate the rank of Hom spaces in𝒟𝒞1(X) by using the standard trace map on H(X). This trace map commutes with the standard trace on H under the inclusion H(X)⊂H. Thus we see that, for objects i̲ and j̲ in 𝒟𝒞1(X), the space Hom𝒟𝒞1(i̲,j̲) is a free R module of some rank r, and the space Hom𝒟𝒞1(X)(i̲,j̲) is a free R(X) module of the same rank r. Therefore Hom𝒟𝒞1[X](i̲,j̲) is a free R module of rank r as well, and the inclusion of 𝒟𝒞1[X] in 𝒟𝒞1 is fully faithful.We quickly sketch an alternative proof of Proposition4.30, which assumes that we know that Hom spaces in 𝒟𝒞1 conform to the standard trace. We can think of any graph with boundary as a morphism in 𝒟𝒞1 from ∅ to j̲. We have already “inductively calculated” the space of such morphisms, along the lines of Remark 2.1 and Proposition 2.13. Namely, if j̲ has no repeated colors, then every morphism is a polynomial with boundary dots. If j̲ has repeated colors, we use idempotent decompositions to consider the Hom space as the sum of the Hom spaces of its summands, or apply biadjunction to cycle the sequence j̲, until we have expressed the Hom space in terms of Hom(∅,k̲) for various k̲ nonrepeating. Since neither biadjunctions nor idempotent decompositions add any new colors to the graph, we have just constructed a generating set of morphisms in a way which does not involve any colors which were not in j̲ to begin with.


## 5. Proofs

It remains to prove Proposition3.11, which we do in the first section, and Proposition 4.19, which we do in the second.


### 5.1.ℱ1 Is a Functor

We need now to check that each of our relations holds true for Soergel bimodules, after application ofF1. The relations are listed in full in Section 3.4. These checks are entirely tedious and straightforward, and require little imagination. With a little imagination, however, there are some tricks which make checking most relations trivial.Again, we always use relation (2.6) to identify elements of Bi̲ with d(i̲)+1 tensors of polynomials.For brevity, we will call any element which is a tensor product1⊗1⊗1⊗⋯ a 1-tensor. EndDot, Split, and the 4-valent and 6-valent vertices all send 1-tensors to 1-tensors. This simple fact is already enough to prove relations (3.1), (3.32), (3.33), (3.34), and (3.36), since the bottom bimodule in each of these pictures is generated by the 1-tensor; we call this the 1-tensor trick. Caps and Merges kill a 1-tensor, while Cups and StartDots send it to a sum of two-linear terms.There are several choices to make when checking the various relations. Once the twisting relations are shown, one is free to prove any twist of the other relations. Also, one may choose which set of generators of the source bimodule to check equality on. Finally, whenever a Cup or a StartDot appears, there are two equivalent ways to write the result, sincexi⊗1-1⊗xi+1=1⊗xi-xi+1⊗1 in Bi, and one might be easier than the other to evaluate.The first trick is to choose the set of generators which makes the calculation the easiest. Let us remind ourselves of the arguments of Remark2.7. An arbitrary module Bi̲ of length d will have 2d-m generators as an R-bimodule, where m is the number of different colors that appear. Let us use the term i-pair to denote two instances of the index i in i̲, separated only by colors ≠i. Let X denote the set of all i-pairs for all i; the size of X is d-m. As we force polynomials to the right or left, a variable xi (or alternatively xi+1) might get stuck between the two i-colored lines of an i-pair, and this independently of each other i-pair or j-pair for j≠i. The following claim is easy to show from the forcing rules.Claim 5.1.
EachBi̲ will be generated as an R-bimodule by any set Y of 2d-m linearly independent tensors, for which we have a bijection between Y and the power set of X, satisfying the following property: If a tensor y∈Y corresponds to a subset Xy⊂X, then each i-pair in Xy corresponds to a distinct linear factor of y which is either xi or xi+1 somewhere inside the i-pair.It is a mouthful, but an example clarifies it. The following is an example of a set of generators forB(i-1)(i+1)i(i+1)(i-1)i, where d-m=3 so we need 8 generators:Each picture represents a tensor, where by convention a blank area is filled with a 1-tensor. Reading across, the first picture corresponds to the empty subset ofX. The second picture corresponds to the i-1-pair, the third to the i+1-pair, and the fourth to the i-pair. Since these three are linearly independent, they take care of all the linear generators. Clearly the fourth picture could have also worked for the i+1-pair, but if we had chosen it as such, we would have had to choose a new linearly independent vector for the i-pair. The fifth generator corresponds to the i-1-pair and the i+1-pair, the sixth generator to the i-1-pair and the i-pair, and the seventh generator to the i-pair and the i+1-pair. These three are also linearly independent. The final generator corresponds to the entire set X.A clever choice of which generators to use may greatly simplify a calculation by reducing the number of terms in intermediate steps. There are two main instances when this occurs. Either 6-valent vertex with strandsi and i+1 will send 1⊗xi+1⊗1⊗1 or 1⊗1⊗xi+1⊗1 to a single tensor, while it may send 1⊗xi⊗1⊗1 to the sum of two tensors, thus doubling the work we need to do in the remainder of the calculation. Also, xixi+1 entering a 6-valent vertex i(i+1)i in the second slot may by moved across the i-strand to the left for a simple calculation, while xi2 leads to a more complicated solution.The second trick will be a useful diagrammatic way of evaluating homomorphisms in𝒮𝒞1, which really only works well when applied to a well-chosen set of generators. In particular, the choice of generators above makes the verification of triple overlap associativity (3.37) rather straightforward. We demonstrate the graphical method in the most difficult case, the highest degree generatorHerex′=xi-1xixi+1.We keep track of the image at every stage in the calculation, which is one term as shown, with all blank spaces being filled by 1-tensors. An arrow indicates either bringing a symmetric polynomial through a line, or applying a 6-valent vertex to a tensor. The lack of an arrow indicates that a 1-tensor is sent to a 1-tensor. This works well only because every intermediate term is a single tensor, not a sum of tensors.We leave it as an exercise to the reader to verify, using this graphical method of calculation, that both sides of the triple overlap associativity relation, as displayed above, send the other 7 generators to the same elements. Precisely, both sides send the 1-tensor to a 1-tensor, and the other generators to 1-tensors with polynomials in various slots: the 2nd and 4th generators toxi+2 in the last slot, the third generator to xi-1 in the last slot, the 5th to xi-1xi+2 in the last slot, the 6th to xixi-1 in the first slot, the 7th to xi+1xi+2 in the first slot, and the 8th as shown above to xixi-1 in the first slot and xi-1 in the last slot. We promise that the graphical method will work for this set of generators.One can extend this graphical method easily to handle other morphisms. As an example, we show the Merge map belowWhenxi+1 enters a Merge, it is sent to −1. Almost the same pictures can be drawn for the Cap. Split and EndDot send 1-tensors to 1-tensors, and no arrows are needed.When there is a cup or a StartDot, a 1-tensor is sent to a sum of two terms, each of which must be evaluated separately. However, the sum can be written as eitherxi⊗1-1⊗xi+1 or 1⊗xi-xi+1⊗1, so we may choose the one whichever is more convenient. Often the problem of having two terms is very temporary. For example, consider what happens to the 1-tensor under the mapThe cup creates two terms, the first with a 1 under the cap and the second withxi under the cap. But the first term is annihilated immediately by the cap, and the cap eats the xi from the other term, to return back a 1-tensor. So long as a cup or a StartDot appears right next to a cap or a merge, one of the two terms is always immediately annihilated. This is the case for (3.5), (3.6), (3.8), which all send 1-tensors to 1-tensors as a result. After a quick polynomial slide, the same is true for (3.31), and using the more convenient choice so the xi+1 ends up underneath the 6-valent vertex, a quick calculation shows it for (3.27) as well. We call this the cupcap trick.We now list and prove the necessary relations, following the same order as in Section3.4. One could print out this list and hold it next to that section, where the relations are and the functor is defined, to make this ordeal easier. (1)
Biadjointness (3.5) follows from the cupcap trick.(2)
Trivalent twisting (3.6) follows from the cupcap trick.(3)
Associativity (3.1) follows from the 1-tensor trick.(4)
Dot twisting (3.8) follows from the cupcap trick.(5)
The needle consists of a split, sending a 1-tensor to a 1-tensor, and a cap, killing a 1-tensor. Hence the needle relation (3.18) follows.(6)
The polynomial slide relations clearly hold for Soergel bimodules, by definition.(7)
For the broken line relation (3.16), both sides clearly send the 1-tensor to xi⊗1-1⊗xi+1.(8)
For the double dot relation (3.17), both sides clearly send the 1-tensor to xi-xi+1.(9)
The three-line decomposition relation (3.26) is a calculation. We need to show it for both color variants, whether thin is i and thick i+1 or vice versa. Let w be the 1-tensor and x=1⊗xi+1⊗1⊗1, regardless of which variant we are in, then it is easy to check that  Consider what happens to x, under the first color variant. The double 6-valent vertex sends x to 1⊗1⊗1⊗xi+2=1⊗1⊗xi+2⊗1, while the rightmost picture sends x to 1⊗xi+1⊗1⊗1-1⊗1⊗xi+2⊗1. The sum of these two is just x again. We leave similarly easy calculations to the reader in the future.(10)
6-valent twisting (3.27) follows from the cupcap trick.(11)
Adding a dot to a 6-valent vertex (3.28) needs to be checked for both color variants. Define w and x as before, and it is easy to check that Here y=xi for one color variant, y=xi+2 for the other.(12)
Two-color associativity (3.29) is a calculation. We recommend using the following twist: and using the four generators: a 1-tensor, 1⊗1⊗xi+1⊗1⊗1, 1⊗xi+1⊗1⊗1⊗1 and 1⊗xi+1⊗1⊗xi+1⊗1. Evaluate using the graphical calculus. The first two generators are killed by both maps thanks to merge maps. The third generator is send to a 1-tensor by both maps. The final generator is also killed by both maps, as symmetric polynomials are slid out of the way and merge maps eat the remaining 1-tensor.(13)
4-valent twisting (3.31) follows from the cupcap trick.(14)
Sliding a dot or a trivalent vertex through a distant line both follow from the 1-tensor trick.(15)
Sliding a 6-valent vertex through a distant line is easily checked on both generators.(16)
Sliding a 4-valent vertex through a distant line follows from the 1-tensor trick.(17)
Three-color associativity will be a calculation, using the generators and pictures described above, that we leave to the reader.


### 5.2. Graphical Proofs

In this section, we provide graphical proofs for a series of propositions which collectively prove Proposition4.19. Recall the definitions of the strict and weak i-colored moves from Section 4.4. Remember that an extremal color i is one which appears in a graph, but for which either i-1 or i+1 does not appear. Each of the results states what reduction moves the relations of 𝒟𝒞1 allow. Because more than three colors may be required for some proofs, we use extra line styles that designate other arbitrary colors, and are very explicit about what colors they are allowed to be. A thin line will still always represent i and a thick line i+1, but we will be lax about other colors.Lemma 5.2.
One may strictly pull a distant line under any other graph, like in the relations (3.32)–(3.36). That is, these relations can be viewed as graph reduction moves.Proof.
The only significant part of this lemma is that we can still apply the relations mentioned, even in the presence of arbitrary polynomials in each region. However, it is an immediate observation that any polynomial inside a region bounded by at least two-lines of distant colors may be slid entirely out of the region, which does not affect the underlying graph.The above lemma highlights the fact that we must deal with polynomials when they appear. However, the only significant polynomials are those which appear in internal regions (regions not touching the boundary of the planar strip) since all our computations will be local, so polynomials in external regions can be moved outside the calculation. We will mention whenever a polynomial is relevant, and the reader can check that whenever we do not mention it, there are only external regions.Proposition 5.3.
One may apply the (strict)i-colored double dot removal move to any graph Γ.Proof.
Suppose thei-graph of Γ contains two dots connected by an edge, then in Γ, the “edge” connecting them can only meet series of 4-valent vertices with various j-strands for j distant from i. Since dots can be slid across distant-colored strands by (3.33), we may slide the dots until they are connected directly by an edge, and just use (3.17) to reduce the graph.Proposition 5.4.
One may apply the weaki-colored dot contraction move to any graph Γ.Proof.
Suppose thei-graph of Γ contains a trivalent vertex connected to a dot. In Γ, the trivalent vertex is either a trivalent or 6-valent vertex v, and the edge connected the dot to the vertex may have numerous 4-valent vertices. Again, in Γ the dot may be slid across distant-colored strands until it is connected directly to v. If v is trivalent then (3.4) allows strict dot contraction, while if v is 6-valent, (3.28) sends Γ to the sum of two graphs allowed by weak dot contraction.Proposition 5.5.
One may apply the (strict)i-colored dot extension move to any graph Γ.Proof.
This is trivial, by (3.4).The following lemma is needed to prove the remainder of the basici-colored moves.Lemma 5.6.
LetΓ be a sequence of lines j̲ (i.e., the identity map of j̲), and let i be an extremal color in j̲, then Γ is equal in 𝒟𝒞1 to a sum of idempotents, such that each idempotent factors through a sequence of lines k̲ where i appears no more than once, and such that the idempotents do not introduce any new colors not present in j̲.Proof.
This proof is akin to the combinatorial argument that the relations defining the Hecke algebra or the symmetric algebra are enough to take any complicated word inbj or sj to a reduced form. We use induction on the length of j̲. If k(k+1)k appears in j̲ for some k, then using (3.26), we may factor through (k+1)k(k+1) instead, modulo morphisms that factor through shorter length sequences. If any color appears twice consecutively in j̲ then we may apply (3.25) to replace the two adjacent lines with an “H”, which factors through a sequence of lines of shorter length. If jk appears for j distant from k, then applying the R2 move we can factor through kj. None of these procedures added any new colors. So if we consider the sequence j̲ as a word in the symmetric group sj1sj2⋯sjd, then any nonreduced words will reduce to smaller length sequences, and any two reduced words for the same element will factor through each other, modulo smaller length sequences.
We may now use the easily observable fact that any element of the symmetric group can be represented by a reduced word which usess1 at most once, or sn at most once (although not both!). It follows from this that any element in a parabolic subgroup of Sn+1 can be represented by a reduced word which uses an extremal index at most once. Thus, by the process above, we can replace j̲ by idempotents factoring through reduced expressions k̲ which use i at most once.The usefulness of this lemma can be seen in the following proof.Proposition 5.7.
One may apply the (strict)i-colored connecting move to any graph Γ, so long as i is extremal.Proof.
Assumei-1 does not appear, although the i+1 case is analogous. Induct on the number of colors present in the graph: the base case of one color is clear, then we are attempting to apply the i-colored connecting move to some region of the graph which looks like this:
Γ′ is some graph composed entirely of the colors 1,…,i-2 and i+1,…,n, so that i+1 is extremal or nonexistent. In some neighborhood Γ′ is just a sequence of lines 1j̲. By the previous lemma, we may replace this sequence of lines with a sum of idempotents factoring through sequences k̲ where i+1 appears at most once, and i-1 appears not at all. Localizing to a neighborhood around 1k̲, we may as well assume that j̲=k̲. Now apply the R2 move to bring the i-strands past all the other colors so that they are separated by either nothing or a single i+1 strand. We have not yet altered the i-graph at all, then equation (3.25) or equation (3.26) (respectively) will allow the strict i-colored connecting move.When we have an edge in ani-graph, a neighborhood of that edge in the full graph will be nothing more than a sequence of 4-valent vertices as the i-strand crosses distant strands. The next corollary allows us to place restrictions on which distant strands the i-strand need cross.Corollary 5.8.
Suppose we are given a graphΓ which is a neighborhood of an i-colored strand consisting only of 4-valent vertices crossing the i-strand (see the picture below), then Γ is equivalent in 𝒟𝒞1 to a linear combination of graphs Γ′ which have the same i-graph, and for which the sequence of lines crossing the i-strand in Γ′ contains i+2 and i-2 each at most once.Proof.
Letj̲ be the sequence of lines crossing the i-strand in Γ; clearly i, i-1, and i+1 do not appear in j̲. According to the above lemma, we may replace 1j̲ with a sum of idempotents which factor through “nice” sequences k̲ where i+2 and i-2 each appear at most once. Moreover, for any idempotent appearing in this sum, i is distant from every color appearing in the idempotent (as well as the polynomials which may appear in the idempotent). So replacing 1j̲ with this sum immediately above the i-strand, we may then slide the i-strand in each idempotent so that it passes through k̲. An example is given below, ignoring polynomials which can also be slid.The last two moves will take the rest of the paper to prove.Proposition 5.9.
One may apply the (strict)i-colored needle move to any graph Γ.Proposition 5.10.
One may apply the weaki-colored associativity move to any i-colored “H ” in any graph Γ, so long as the “H ” does not look like the following picture: where the two vertices are 6-valent in Γ with different colors i+1 and i-1.
In particular, we may apply thei-colored associativity move to any graph Γ when i is extremal.Proof Setup. We apply induction on the set of colors present in the graph to prove these two propositions simultaneously. Both propositions hold when i is the only color in the graph, by (3.10), (3.18), (3.24), where the latter is needed because an arbitrary polynomial may be within the eye of the needle. The inductive hypothesis then implies, with the previous propositions, that for any graph with fewer colors, we may apply all the weak k-colored basic moves for an extremal color k. In this case Proposition 4.17 says that we may reduce the k-graph to a disjoint union of simple trees. Within each region of Γ delimited by the i-graph the color i is absent, so there are fewer total colors and we may reduce both the i-1-graph and the i+1-graph inside this region to a union of simple trees. This application of the inductive hypothesis was the only reason to consider the two propositions together; we now treat them separately.Needle Move: Modulo Induction Hypothesis. Suppose the i-colored graph contains a needle. The trivalent vertex of the needle is either trivalent or 6-valent in Γ, and the edge of the needle may contain a series of 4-valent vertices. So a neighborhood of the needle in Γ looks like one of the pictures below.The lines entering the needle around the top are colored with variousj all distant from i. We assume without loss of generality that, in the second case, the 6-valent vertex has second color i+1.We may now reduce thei+1 and i-1 graph of Γ′, since Γ′ does not contain the color i. In the first case, the i±1 graph has no boundary, so both reduce to the empty graph. In the second case, i+1 has a single boundary line so it reduces to a boundary dot, and i-1 has none so it reduces to the empty graph. Within the reduced Γ′, the possible i+1 dot may be slid under other lines until no 4-valent vertices separate it from the 6-valent vertex (as in the proof of weak dot contraction). Thus we may assume that, after reduction, our neighborhood looks likewhere nowΓ′ does not contain any of the colors i-1, i, i+1. Note that Γ′ may have arbitrary polynomials in its various regions. But then by Lemma 5.2 we can pull the line forming the needle through all of Γ′, thus completely ignoring Γ′ from the picture! There still may be a polynomial in the eye of the needle. We have effectively reduced to the 2-color case on the right, or the one color case on the left. We know the one color case works. To check the 2-color case, we use (3.28) followed by other reduction moves.In these final graphs, thei-graph is a dot, as desired. So we may apply the strict i-colored needle move.Associativity Move: Modulo Induction Hypothesis. We would like to apply associativity to the following subgraph of the i-graph.Each trivalent vertex of thei-graph may be either trivalent or 6-valent in Γ. We are forbidding the case when one is 6-valent with i+1 and the other with i-1, so without loss of generality with assume that a 6-valent vertex has i+1 as the other color. The neighborhood of this subgraph in Γ looks like one of the following cases:All polynomials may be assumed to lie outside the neighborhood. We may use Corollary5.8 to assume that the sequence of lines passing through the middle strand contains at most one instance of i+2 and i-2. In the first two cases, all such lines may be slid one by one to the right over the trivalent vertex, removing them from the neighborhood. In the third case, all lines not labelled i+2 can be slid to the right or to the left, and since there is at most one line labelled i+2, then at most one line remains. (If there had been multiple lines labelled i+2, then additional lines may have been stuck between them, but thankfully Corollary 5.8 eliminates this possibility.) Four cases remain:In the fourth case, the additional line isi+2. So far, the i-graph has been unchanged.Case 1.
One color associativity allows the stricti-colored associativity move.Case 2.
Double overlap associativity (3.30) allows the strict i-colored associativity move.The remaining two cases use the same trick: they replace the interior lines on the top and bottom of the graph with the corresponding sum of idempotents, and then resolve each one with double or triple overlap associativity. The remaining two cases will not allow the strict associativity move, only the weak one.Case 3.
We rewrite equation (3.25), using (3.16), so that there is no polynomial on the bottom.Applying this to the thick edges on top of Case3, and symmetrically to the bottom, we get a difference of graphs of two kinds.For terms which do not involve a dot, we get a graph which looks like the following, withno polynomial in any interior region:We may apply double overlap associativity (3.29) to a subgraph of this diagram (ignoring the top and bottom thick trivalent vertices), which will apply associativity to the i-graph.Consider a term where a dot connects to a 6-valent vertex. Resolving the dot using (3.28), we get a difference of two further terms: one which looks like Case 2, and the other which is one of the alternate graphs allowed by the weak associativity move.Thus we may apply weaki-colored associativity to each term.Case 4.
Applying equation (3.26) to the i+1, i+2, i+1 sequence on top of the graph, we get the differenceNow we need to show that we can apply associativity to each of these.For the second picture, we may drag the dot oni+2 through the i-strand, and then a smaller neighborhood of the X looks like Case 3.For the first picture, we once again apply (3.26) to the bottom of the graph to get the differenceAgain, for the second picture we may drag the dot through and reduce using Case3.For the first picture, there areno polynomials in any internal region, because these internal regions were just created by relations. We may now apply triple overlap associativity (3.37) to the subgraph of the this picture which ignores the top and bottom 6-valent vertices. This has the effect of applying weak i-colored associativity.Remark 5.11.
It does not seem possible to applyi-colored associativity to the following graph.
Consider switching thei-graph to the other version of an “H", and look at the triangular region delimited by the i-graph on top. It has at most one 6-valent vertex on its perimeter, so that its boundary lines consist of an i-1 line, an i+1 line, and at most one other i±1 line. This means that one of the two colors i-1 or i+1 must reduce to a boundary dot. It is not possible to obtain a degree 0 morphism if this happens.
Because of the failure ofi-colored associativity in this context, our algorithm towards reducing graphs has always been to treat extremal colors and use induction. Despite this pessimism, Proposition 4.30 (color elimination) implies that we can still do a lot. However, any purely graphical proof of color elimination is complicated by the failure of i-colored associativity for nonextremal colors.


## 5.1.ℱ1 Is a Functor

We need now to check that each of our relations holds true for Soergel bimodules, after application ofF1. The relations are listed in full in Section 3.4. These checks are entirely tedious and straightforward, and require little imagination. With a little imagination, however, there are some tricks which make checking most relations trivial.Again, we always use relation (2.6) to identify elements of Bi̲ with d(i̲)+1 tensors of polynomials.For brevity, we will call any element which is a tensor product1⊗1⊗1⊗⋯ a 1-tensor. EndDot, Split, and the 4-valent and 6-valent vertices all send 1-tensors to 1-tensors. This simple fact is already enough to prove relations (3.1), (3.32), (3.33), (3.34), and (3.36), since the bottom bimodule in each of these pictures is generated by the 1-tensor; we call this the 1-tensor trick. Caps and Merges kill a 1-tensor, while Cups and StartDots send it to a sum of two-linear terms.There are several choices to make when checking the various relations. Once the twisting relations are shown, one is free to prove any twist of the other relations. Also, one may choose which set of generators of the source bimodule to check equality on. Finally, whenever a Cup or a StartDot appears, there are two equivalent ways to write the result, sincexi⊗1-1⊗xi+1=1⊗xi-xi+1⊗1 in Bi, and one might be easier than the other to evaluate.The first trick is to choose the set of generators which makes the calculation the easiest. Let us remind ourselves of the arguments of Remark2.7. An arbitrary module Bi̲ of length d will have 2d-m generators as an R-bimodule, where m is the number of different colors that appear. Let us use the term i-pair to denote two instances of the index i in i̲, separated only by colors ≠i. Let X denote the set of all i-pairs for all i; the size of X is d-m. As we force polynomials to the right or left, a variable xi (or alternatively xi+1) might get stuck between the two i-colored lines of an i-pair, and this independently of each other i-pair or j-pair for j≠i. The following claim is easy to show from the forcing rules.Claim 5.1.
EachBi̲ will be generated as an R-bimodule by any set Y of 2d-m linearly independent tensors, for which we have a bijection between Y and the power set of X, satisfying the following property: If a tensor y∈Y corresponds to a subset Xy⊂X, then each i-pair in Xy corresponds to a distinct linear factor of y which is either xi or xi+1 somewhere inside the i-pair.It is a mouthful, but an example clarifies it. The following is an example of a set of generators forB(i-1)(i+1)i(i+1)(i-1)i, where d-m=3 so we need 8 generators:Each picture represents a tensor, where by convention a blank area is filled with a 1-tensor. Reading across, the first picture corresponds to the empty subset ofX. The second picture corresponds to the i-1-pair, the third to the i+1-pair, and the fourth to the i-pair. Since these three are linearly independent, they take care of all the linear generators. Clearly the fourth picture could have also worked for the i+1-pair, but if we had chosen it as such, we would have had to choose a new linearly independent vector for the i-pair. The fifth generator corresponds to the i-1-pair and the i+1-pair, the sixth generator to the i-1-pair and the i-pair, and the seventh generator to the i-pair and the i+1-pair. These three are also linearly independent. The final generator corresponds to the entire set X.A clever choice of which generators to use may greatly simplify a calculation by reducing the number of terms in intermediate steps. There are two main instances when this occurs. Either 6-valent vertex with strandsi and i+1 will send 1⊗xi+1⊗1⊗1 or 1⊗1⊗xi+1⊗1 to a single tensor, while it may send 1⊗xi⊗1⊗1 to the sum of two tensors, thus doubling the work we need to do in the remainder of the calculation. Also, xixi+1 entering a 6-valent vertex i(i+1)i in the second slot may by moved across the i-strand to the left for a simple calculation, while xi2 leads to a more complicated solution.The second trick will be a useful diagrammatic way of evaluating homomorphisms in𝒮𝒞1, which really only works well when applied to a well-chosen set of generators. In particular, the choice of generators above makes the verification of triple overlap associativity (3.37) rather straightforward. We demonstrate the graphical method in the most difficult case, the highest degree generatorHerex′=xi-1xixi+1.We keep track of the image at every stage in the calculation, which is one term as shown, with all blank spaces being filled by 1-tensors. An arrow indicates either bringing a symmetric polynomial through a line, or applying a 6-valent vertex to a tensor. The lack of an arrow indicates that a 1-tensor is sent to a 1-tensor. This works well only because every intermediate term is a single tensor, not a sum of tensors.We leave it as an exercise to the reader to verify, using this graphical method of calculation, that both sides of the triple overlap associativity relation, as displayed above, send the other 7 generators to the same elements. Precisely, both sides send the 1-tensor to a 1-tensor, and the other generators to 1-tensors with polynomials in various slots: the 2nd and 4th generators toxi+2 in the last slot, the third generator to xi-1 in the last slot, the 5th to xi-1xi+2 in the last slot, the 6th to xixi-1 in the first slot, the 7th to xi+1xi+2 in the first slot, and the 8th as shown above to xixi-1 in the first slot and xi-1 in the last slot. We promise that the graphical method will work for this set of generators.One can extend this graphical method easily to handle other morphisms. As an example, we show the Merge map belowWhenxi+1 enters a Merge, it is sent to −1. Almost the same pictures can be drawn for the Cap. Split and EndDot send 1-tensors to 1-tensors, and no arrows are needed.When there is a cup or a StartDot, a 1-tensor is sent to a sum of two terms, each of which must be evaluated separately. However, the sum can be written as eitherxi⊗1-1⊗xi+1 or 1⊗xi-xi+1⊗1, so we may choose the one whichever is more convenient. Often the problem of having two terms is very temporary. For example, consider what happens to the 1-tensor under the mapThe cup creates two terms, the first with a 1 under the cap and the second withxi under the cap. But the first term is annihilated immediately by the cap, and the cap eats the xi from the other term, to return back a 1-tensor. So long as a cup or a StartDot appears right next to a cap or a merge, one of the two terms is always immediately annihilated. This is the case for (3.5), (3.6), (3.8), which all send 1-tensors to 1-tensors as a result. After a quick polynomial slide, the same is true for (3.31), and using the more convenient choice so the xi+1 ends up underneath the 6-valent vertex, a quick calculation shows it for (3.27) as well. We call this the cupcap trick.We now list and prove the necessary relations, following the same order as in Section3.4. One could print out this list and hold it next to that section, where the relations are and the functor is defined, to make this ordeal easier. (1)
Biadjointness (3.5) follows from the cupcap trick.(2)
Trivalent twisting (3.6) follows from the cupcap trick.(3)
Associativity (3.1) follows from the 1-tensor trick.(4)
Dot twisting (3.8) follows from the cupcap trick.(5)
The needle consists of a split, sending a 1-tensor to a 1-tensor, and a cap, killing a 1-tensor. Hence the needle relation (3.18) follows.(6)
The polynomial slide relations clearly hold for Soergel bimodules, by definition.(7)
For the broken line relation (3.16), both sides clearly send the 1-tensor to xi⊗1-1⊗xi+1.(8)
For the double dot relation (3.17), both sides clearly send the 1-tensor to xi-xi+1.(9)
The three-line decomposition relation (3.26) is a calculation. We need to show it for both color variants, whether thin is i and thick i+1 or vice versa. Let w be the 1-tensor and x=1⊗xi+1⊗1⊗1, regardless of which variant we are in, then it is easy to check that  Consider what happens to x, under the first color variant. The double 6-valent vertex sends x to 1⊗1⊗1⊗xi+2=1⊗1⊗xi+2⊗1, while the rightmost picture sends x to 1⊗xi+1⊗1⊗1-1⊗1⊗xi+2⊗1. The sum of these two is just x again. We leave similarly easy calculations to the reader in the future.(10)
6-valent twisting (3.27) follows from the cupcap trick.(11)
Adding a dot to a 6-valent vertex (3.28) needs to be checked for both color variants. Define w and x as before, and it is easy to check that Here y=xi for one color variant, y=xi+2 for the other.(12)
Two-color associativity (3.29) is a calculation. We recommend using the following twist: and using the four generators: a 1-tensor, 1⊗1⊗xi+1⊗1⊗1, 1⊗xi+1⊗1⊗1⊗1 and 1⊗xi+1⊗1⊗xi+1⊗1. Evaluate using the graphical calculus. The first two generators are killed by both maps thanks to merge maps. The third generator is send to a 1-tensor by both maps. The final generator is also killed by both maps, as symmetric polynomials are slid out of the way and merge maps eat the remaining 1-tensor.(13)
4-valent twisting (3.31) follows from the cupcap trick.(14)
Sliding a dot or a trivalent vertex through a distant line both follow from the 1-tensor trick.(15)
Sliding a 6-valent vertex through a distant line is easily checked on both generators.(16)
Sliding a 4-valent vertex through a distant line follows from the 1-tensor trick.(17)
Three-color associativity will be a calculation, using the generators and pictures described above, that we leave to the reader.


## 5.2. Graphical Proofs

In this section, we provide graphical proofs for a series of propositions which collectively prove Proposition4.19. Recall the definitions of the strict and weak i-colored moves from Section 4.4. Remember that an extremal color i is one which appears in a graph, but for which either i-1 or i+1 does not appear. Each of the results states what reduction moves the relations of 𝒟𝒞1 allow. Because more than three colors may be required for some proofs, we use extra line styles that designate other arbitrary colors, and are very explicit about what colors they are allowed to be. A thin line will still always represent i and a thick line i+1, but we will be lax about other colors.Lemma 5.2.
One may strictly pull a distant line under any other graph, like in the relations (3.32)–(3.36). That is, these relations can be viewed as graph reduction moves.Proof.
The only significant part of this lemma is that we can still apply the relations mentioned, even in the presence of arbitrary polynomials in each region. However, it is an immediate observation that any polynomial inside a region bounded by at least two-lines of distant colors may be slid entirely out of the region, which does not affect the underlying graph.The above lemma highlights the fact that we must deal with polynomials when they appear. However, the only significant polynomials are those which appear in internal regions (regions not touching the boundary of the planar strip) since all our computations will be local, so polynomials in external regions can be moved outside the calculation. We will mention whenever a polynomial is relevant, and the reader can check that whenever we do not mention it, there are only external regions.Proposition 5.3.
One may apply the (strict)i-colored double dot removal move to any graph Γ.Proof.
Suppose thei-graph of Γ contains two dots connected by an edge, then in Γ, the “edge” connecting them can only meet series of 4-valent vertices with various j-strands for j distant from i. Since dots can be slid across distant-colored strands by (3.33), we may slide the dots until they are connected directly by an edge, and just use (3.17) to reduce the graph.Proposition 5.4.
One may apply the weaki-colored dot contraction move to any graph Γ.Proof.
Suppose thei-graph of Γ contains a trivalent vertex connected to a dot. In Γ, the trivalent vertex is either a trivalent or 6-valent vertex v, and the edge connected the dot to the vertex may have numerous 4-valent vertices. Again, in Γ the dot may be slid across distant-colored strands until it is connected directly to v. If v is trivalent then (3.4) allows strict dot contraction, while if v is 6-valent, (3.28) sends Γ to the sum of two graphs allowed by weak dot contraction.Proposition 5.5.
One may apply the (strict)i-colored dot extension move to any graph Γ.Proof.
This is trivial, by (3.4).The following lemma is needed to prove the remainder of the basici-colored moves.Lemma 5.6.
LetΓ be a sequence of lines j̲ (i.e., the identity map of j̲), and let i be an extremal color in j̲, then Γ is equal in 𝒟𝒞1 to a sum of idempotents, such that each idempotent factors through a sequence of lines k̲ where i appears no more than once, and such that the idempotents do not introduce any new colors not present in j̲.Proof.
This proof is akin to the combinatorial argument that the relations defining the Hecke algebra or the symmetric algebra are enough to take any complicated word inbj or sj to a reduced form. We use induction on the length of j̲. If k(k+1)k appears in j̲ for some k, then using (3.26), we may factor through (k+1)k(k+1) instead, modulo morphisms that factor through shorter length sequences. If any color appears twice consecutively in j̲ then we may apply (3.25) to replace the two adjacent lines with an “H”, which factors through a sequence of lines of shorter length. If jk appears for j distant from k, then applying the R2 move we can factor through kj. None of these procedures added any new colors. So if we consider the sequence j̲ as a word in the symmetric group sj1sj2⋯sjd, then any nonreduced words will reduce to smaller length sequences, and any two reduced words for the same element will factor through each other, modulo smaller length sequences.
We may now use the easily observable fact that any element of the symmetric group can be represented by a reduced word which usess1 at most once, or sn at most once (although not both!). It follows from this that any element in a parabolic subgroup of Sn+1 can be represented by a reduced word which uses an extremal index at most once. Thus, by the process above, we can replace j̲ by idempotents factoring through reduced expressions k̲ which use i at most once.The usefulness of this lemma can be seen in the following proof.Proposition 5.7.
One may apply the (strict)i-colored connecting move to any graph Γ, so long as i is extremal.Proof.
Assumei-1 does not appear, although the i+1 case is analogous. Induct on the number of colors present in the graph: the base case of one color is clear, then we are attempting to apply the i-colored connecting move to some region of the graph which looks like this:
Γ′ is some graph composed entirely of the colors 1,…,i-2 and i+1,…,n, so that i+1 is extremal or nonexistent. In some neighborhood Γ′ is just a sequence of lines 1j̲. By the previous lemma, we may replace this sequence of lines with a sum of idempotents factoring through sequences k̲ where i+1 appears at most once, and i-1 appears not at all. Localizing to a neighborhood around 1k̲, we may as well assume that j̲=k̲. Now apply the R2 move to bring the i-strands past all the other colors so that they are separated by either nothing or a single i+1 strand. We have not yet altered the i-graph at all, then equation (3.25) or equation (3.26) (respectively) will allow the strict i-colored connecting move.When we have an edge in ani-graph, a neighborhood of that edge in the full graph will be nothing more than a sequence of 4-valent vertices as the i-strand crosses distant strands. The next corollary allows us to place restrictions on which distant strands the i-strand need cross.Corollary 5.8.
Suppose we are given a graphΓ which is a neighborhood of an i-colored strand consisting only of 4-valent vertices crossing the i-strand (see the picture below), then Γ is equivalent in 𝒟𝒞1 to a linear combination of graphs Γ′ which have the same i-graph, and for which the sequence of lines crossing the i-strand in Γ′ contains i+2 and i-2 each at most once.Proof.
Letj̲ be the sequence of lines crossing the i-strand in Γ; clearly i, i-1, and i+1 do not appear in j̲. According to the above lemma, we may replace 1j̲ with a sum of idempotents which factor through “nice” sequences k̲ where i+2 and i-2 each appear at most once. Moreover, for any idempotent appearing in this sum, i is distant from every color appearing in the idempotent (as well as the polynomials which may appear in the idempotent). So replacing 1j̲ with this sum immediately above the i-strand, we may then slide the i-strand in each idempotent so that it passes through k̲. An example is given below, ignoring polynomials which can also be slid.The last two moves will take the rest of the paper to prove.Proposition 5.9.
One may apply the (strict)i-colored needle move to any graph Γ.Proposition 5.10.
One may apply the weaki-colored associativity move to any i-colored “H ” in any graph Γ, so long as the “H ” does not look like the following picture: where the two vertices are 6-valent in Γ with different colors i+1 and i-1.
In particular, we may apply thei-colored associativity move to any graph Γ when i is extremal.Proof Setup. We apply induction on the set of colors present in the graph to prove these two propositions simultaneously. Both propositions hold when i is the only color in the graph, by (3.10), (3.18), (3.24), where the latter is needed because an arbitrary polynomial may be within the eye of the needle. The inductive hypothesis then implies, with the previous propositions, that for any graph with fewer colors, we may apply all the weak k-colored basic moves for an extremal color k. In this case Proposition 4.17 says that we may reduce the k-graph to a disjoint union of simple trees. Within each region of Γ delimited by the i-graph the color i is absent, so there are fewer total colors and we may reduce both the i-1-graph and the i+1-graph inside this region to a union of simple trees. This application of the inductive hypothesis was the only reason to consider the two propositions together; we now treat them separately.Needle Move: Modulo Induction Hypothesis. Suppose the i-colored graph contains a needle. The trivalent vertex of the needle is either trivalent or 6-valent in Γ, and the edge of the needle may contain a series of 4-valent vertices. So a neighborhood of the needle in Γ looks like one of the pictures below.The lines entering the needle around the top are colored with variousj all distant from i. We assume without loss of generality that, in the second case, the 6-valent vertex has second color i+1.We may now reduce thei+1 and i-1 graph of Γ′, since Γ′ does not contain the color i. In the first case, the i±1 graph has no boundary, so both reduce to the empty graph. In the second case, i+1 has a single boundary line so it reduces to a boundary dot, and i-1 has none so it reduces to the empty graph. Within the reduced Γ′, the possible i+1 dot may be slid under other lines until no 4-valent vertices separate it from the 6-valent vertex (as in the proof of weak dot contraction). Thus we may assume that, after reduction, our neighborhood looks likewhere nowΓ′ does not contain any of the colors i-1, i, i+1. Note that Γ′ may have arbitrary polynomials in its various regions. But then by Lemma 5.2 we can pull the line forming the needle through all of Γ′, thus completely ignoring Γ′ from the picture! There still may be a polynomial in the eye of the needle. We have effectively reduced to the 2-color case on the right, or the one color case on the left. We know the one color case works. To check the 2-color case, we use (3.28) followed by other reduction moves.In these final graphs, thei-graph is a dot, as desired. So we may apply the strict i-colored needle move.Associativity Move: Modulo Induction Hypothesis. We would like to apply associativity to the following subgraph of the i-graph.Each trivalent vertex of thei-graph may be either trivalent or 6-valent in Γ. We are forbidding the case when one is 6-valent with i+1 and the other with i-1, so without loss of generality with assume that a 6-valent vertex has i+1 as the other color. The neighborhood of this subgraph in Γ looks like one of the following cases:All polynomials may be assumed to lie outside the neighborhood. We may use Corollary5.8 to assume that the sequence of lines passing through the middle strand contains at most one instance of i+2 and i-2. In the first two cases, all such lines may be slid one by one to the right over the trivalent vertex, removing them from the neighborhood. In the third case, all lines not labelled i+2 can be slid to the right or to the left, and since there is at most one line labelled i+2, then at most one line remains. (If there had been multiple lines labelled i+2, then additional lines may have been stuck between them, but thankfully Corollary 5.8 eliminates this possibility.) Four cases remain:In the fourth case, the additional line isi+2. So far, the i-graph has been unchanged.Case 1.
One color associativity allows the stricti-colored associativity move.Case 2.
Double overlap associativity (3.30) allows the strict i-colored associativity move.The remaining two cases use the same trick: they replace the interior lines on the top and bottom of the graph with the corresponding sum of idempotents, and then resolve each one with double or triple overlap associativity. The remaining two cases will not allow the strict associativity move, only the weak one.Case 3.
We rewrite equation (3.25), using (3.16), so that there is no polynomial on the bottom.Applying this to the thick edges on top of Case3, and symmetrically to the bottom, we get a difference of graphs of two kinds.For terms which do not involve a dot, we get a graph which looks like the following, withno polynomial in any interior region:We may apply double overlap associativity (3.29) to a subgraph of this diagram (ignoring the top and bottom thick trivalent vertices), which will apply associativity to the i-graph.Consider a term where a dot connects to a 6-valent vertex. Resolving the dot using (3.28), we get a difference of two further terms: one which looks like Case 2, and the other which is one of the alternate graphs allowed by the weak associativity move.Thus we may apply weaki-colored associativity to each term.Case 4.
Applying equation (3.26) to the i+1, i+2, i+1 sequence on top of the graph, we get the differenceNow we need to show that we can apply associativity to each of these.For the second picture, we may drag the dot oni+2 through the i-strand, and then a smaller neighborhood of the X looks like Case 3.For the first picture, we once again apply (3.26) to the bottom of the graph to get the differenceAgain, for the second picture we may drag the dot through and reduce using Case3.For the first picture, there areno polynomials in any internal region, because these internal regions were just created by relations. We may now apply triple overlap associativity (3.37) to the subgraph of the this picture which ignores the top and bottom 6-valent vertices. This has the effect of applying weak i-colored associativity.Remark 5.11.
It does not seem possible to applyi-colored associativity to the following graph.
Consider switching thei-graph to the other version of an “H", and look at the triangular region delimited by the i-graph on top. It has at most one 6-valent vertex on its perimeter, so that its boundary lines consist of an i-1 line, an i+1 line, and at most one other i±1 line. This means that one of the two colors i-1 or i+1 must reduce to a boundary dot. It is not possible to obtain a degree 0 morphism if this happens.
Because of the failure ofi-colored associativity in this context, our algorithm towards reducing graphs has always been to treat extremal colors and use induction. Despite this pessimism, Proposition 4.30 (color elimination) implies that we can still do a lot. However, any purely graphical proof of color elimination is complicated by the failure of i-colored associativity for nonextremal colors.



---

*Source: 978635-2011-06-30.xml*