MATH 47A FALL 2008INTRO TO MATH RESEARCHKIYOSHI IGUSAContents1. Permutations or: group theory in 15 minutes 22. Transpositions 53. more group theory 83.1. inverse 83.2. commutativity 103.3. conjugation 113.4. definition of a group 133.5. permutation matrices 144. Roots and reflections 164.1. roots of type An−1164.2. reflections 194.3. other roots systems 225. Catalan numbers and Narayana numbers 245.1. binary trees 255.2. Dyck paths 285.3. Dyck paths to binary trees 315.4. reflection principle 345.5. noncrossing partitions 366. Braids 406.1. basic definitions 406.2. Artin braid group 406.3. Garside element ∆ 407. Categories 417.1. definition 417.2. posets 447.3. Additive categories 467.4. cluster categories of type Anover F2497.5. Clusters in the cluster category 51Date: October 20, 2008.0MATH 47A FALL 2008 INTRO TO MATH RESEARCH 18. Research 532 NOTES1. Permutations or: group theory in 15 minutesFor those of you who already took a course in group theory, youprobably learned about “abstract groups” which are sets with binaryoperations satisfying a list of conditions. I want to talk about permu-tations. Those who already know group theory can think about thequestion:Why is every group isomorphic to a permutation group?Definition 1.1. A permutation on a set X is a bijection f : X → X.Recall that a bijection is a mapping which is(1) 1-1 (injective) and(2) onto (surjective).If X = {1, 2, ··· ,n}, a permutation of X is called a permutation on nletters. The set of permutations of X will be denoted by P erm(X).I discussed three notations for permutations:(1) σ =!1 2 3 43 4 2 1"means σ(1) = 3,σ(2) = 4,σ(3) = 2,σ(4) =1 or σ(x)=y where x is given in the first row and y is given inthe second row.(2) (cycle form) σ = (1324). This means σ sends 1 to 3, 3 to 2, 2to 4 and 4 to 1: 1 → 3 → 2 → 4 → 1.(3) (graphic notation). Here you put the numbers x =1, ··· ,nvertically on the right, put y =1, ··· ,n vertically on the leftand connect each x to each y = f(x). For example, if f =(1423), you connect 1 on the right to f(1) = 4 on the left witha straight line, etc. In cycle notation, f = (1423).yxfx1 3 1!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!2 4 2""""""""""""""""""""""""""""3 2 3###############################4 1 4###############################MATH 47A FALL 2008 INTRO TO MATH RESEARCH 3Definition 1.2. If f, g ∈ P erm(X), fg = f ◦ g is the composition off and g. This is the permutation defined byfg(x)=f(g(x))It means you do g first and then f.Question: If g = (34) what is gf ? Write the answer in all three nota-tions and demonstrate the composition in the notation.(1) Stack up f, g, putting the first operation f on top and thesecond g underneath. Then cross out the second line:1 2 3 44 3 1 23 4 1 2=!1 2 3 43 4 1 2"(2) Write the cycles next to each other and compute the image ofeach x by applying the cycles one at a time going from right toleft:gf = (34)(1423) = (13)(24)for example:gf(1) =3(34)4(1423)1=3(3) Draw the diagrams next to each other, putting the first permu-tation f on the right:ygfx1 3 3$$1!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!2 4 4$$2""""""""""""""""""""""""""""3 1 2%%$$$$$$$$$$$$$$3###############################4 2 1&&%%%%%%%%%%%%%%4###############################Note that g = (34) switches the “letters” in locations 3 and 4. Wediscussed the fact that two of the crossings cancel when we redraw thepicture:4 NOTESygfx1 3 1''&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2 4 2''&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&3 1 3((''''''''''''''''''''''''''''''''''''''''''4 2 4((''''''''''''''''''''''''''''''''''''''''''Then we discussed the number of crossings.MATH 47A FALL 2008 INTRO TO MATH RESEARCH 52. TranspositionsOn Day 2, I tried to formalize things we talked about at the endof Day 1, namely, in what way do the crossings in the diagram givetranspositions and: What is the “longest word” ?Definition 2.1. A transposition is a 2-cycle (ab). For example(14) =!1 2 3 44 2 3 1"is a transposition. A simple transposition (also called a simple reflec-tion) is a transposition of two consecutive letters:si:= (i, i + 1)In the group of permutations of n + 1 letters there are n simple reflec-tions: s1= (12),s2= (23), ··· ,sn=(n, n + 1).We talked about the following vaguely phrased theorem.Theorem 2.2. A permutation f can be written as a product of simplereflections, one for every crossing in the diagram for f.I drew a bunch of diagrams to illustrate this. The first was:ygx1 3 1""""""""""""""""""""""""""""2 1 2""""""""""""""""""""""""""""3 2 3###############################(12)(23)The crossing on the right is s2= (23). The one on the left if s1= (12).Reading these from right to left we get:g = (123) = (12)(23) = s1s2.When two crossing lie above each other (so that you don’t know whichone is on the left and which is on the right) you can write them in6 NOTESeither order. For example:y(14)x1 4 1))((((((((((((((((((((((((((((((((((((2 2 2$$3 3 3$$4 1 4**))))))))))))))))))))))))))))))))))))(34)(12)(34)(12)(23)This gives:(14) = (12)(34)(23)(12)(34) = s1s3s2s1s3But the crossings labeled s1= (12) and s3= (34) lie above each other.So we can write them in either order:(14) = s3s1s2s3s1In general, the rule issisj= sjsiif |j − i|≥ 2Definition 2.3. Suppose that f is a permutation of the letters 1, 2, ··· ,n+1. Then the length "(f) of f is defined to be the number of pairs ofintegers i, j so that(1) 1 ≤ i<j≤ n +1(2) f (i) >f(j).In other words, it is the numb er of pairs of numbers whose order isswitched by f.Corollary 2.4. Any permutation f can be written as a product of "(f)simple reflections.Proof. Draw the diagram of the permutation. Move the lines slightlyup or down so that there are no triple crossings of lines. Lines i andj will cross if and only if the are in one order on the right (i<j) andin the other order on the left (f(i) >f(j)). Therefore, the number ofcrossings is equal to "(f) as defined above. The theorem says that eachcrossing gives one simple reflection and that f is a product of thosesimple reflections. Therefore, f is a product of "(f) reflections. !MATH 47A FALL 2008 INTRO TO MATH RESEARCH 7How large can "(f) be?The maximum possible numb er occurs when every single pair of in-tegers i<jgets reversed. This is the permutation called w0:w0=!1 2 3 ··· n +1n +1 nn− 1 ··· 1"The length of w0is the number of all pairs 1 ≤ i<j≤ n + 1 which is"(w0)=!n +12"=n(n + 1)2= 1 + 2 + ··· + nThis is a triangle number. As Tri pointed out