### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# LINEAR ALGEBRAIC GROUPS M 390C

UT

GPA 3.67

### View Full Document

## 49

## 0

## Popular in Course

## Popular in Mathematics (M)

This 93 page Class Notes was uploaded by Reyes Glover on Sunday September 6, 2015. The Class Notes belongs to M 390C at University of Texas at Austin taught by Christopher Hall in Fall. Since its upload, it has received 49 views. For similar materials see /class/181417/m-390c-university-of-texas-at-austin in Mathematics (M) at University of Texas at Austin.

## Reviews for LINEAR ALGEBRAIC GROUPS

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/06/15

Algebraic Combinatorics Geir T Helleloid Fall 2008 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Contents 1 Enumeration D 15 16 17 Spec 21 22 Lecture 1 Thursday August 28 The 12 Fold Way Stanley 4 Section 11 111 Stirling Numbers and Bell Numbers 112 Superclasses Arias Castro Diaconis Stanley 113 Back to the 12 Fold Way Lecture 2 Tuesday September 2 Generating Functions Stanley 4 Section 11 121 Recurrences 122 Catalan numbers 123 q Analogues Lecture 3 Thursday September 4 Permutation Enumeration Stanley 4 Section 11 Wilf 7 Chapter 4 131 Permutation Statistics 132 Multiset Permutations and q Analogues 133 Cycles 134 Using Generating Functions to Find Expected Values 135 Unimodality 136 Cycle lndex 137 Square Roots Lecture 5 Thursday September 11 The Exponential Formula Stanley 5 Chapter 5 Lecture 6 Tuesday September 16 Bijections Lecture 7 Thursday September 18 Bijections ll Lecture 8 Tuesday September 23 Bijections ll Aigner 1 Section 54 171 The Gessel Viennot Lemma ial Topics Lecture 9 Thursday September 25 Permutation Patterns Bona 2 Chapter 4 Lecture 10 Tuesday September 30 The Matrix Tree Theorem Stanley 5 Section 56 221 Spanning Trees and the Matrix Tree Theorem Lecture 11 Thursday October 2 The BEST Theorem Stanley 5 Section 56 231 The BEST Theorem 30 38 40 40 43 43 M390C Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 03 232 De Bruijn Sequences 24 Lecture 12 Tuesday October 7 Abelian Sandpiles and Chip Firing Games 52 25 Lecture 13 Thursday October 9 Mobius Inversion and the Chromatic Poly nomial Stanley 4 Chapter 2 251 Posets and Mobius lnversion 57 252 Back to the Chromatic Polynomial 26 Lecture 14 Tuesday October 14 The Chromatic Polynomial and Connections 60 261 The Graph Minor Theorem 61 262 Hyperplane Arrangements 62 The Representation Theory of the Symmetric Group and Symmetric Func tions 63 31 An Introduction to the Representation Theory of Finite Groups Sagan 3 Chapter 1 63 311 Representations 64 312 lrreducible Representations 65 313 Characters 66 32 Lectures 16 and 17 Tuesday October 21 and Thursday October 23 The lrreducible Representations of the Symmetric Group Sagan 3 Chapter 2 66 321 Constructing the lrreducible Representations Sagan 3 Section 21 66 322 The Specht module Squot Sagan 3 Section 23 67 323 The Specht Modules are the lrreducible Modules Sagan 3 Section 24 68 324 Finding a Basis for Squot Sagan 3 Section 25 70 325 Decomposition of Mquot Sagan 3 Section 29 71 33 Lecture 18 Tuesday October 28 The RSK Algorithm Stanley 5 Section 711 71 331 Row lnsertion 72 332 The Robinson Schensted Knuth RSK Algorithm 73 333 Growth Diagrams and Symmetries of RSK 74 34 Lecture 19 Thursday October 30 Increasing and Decreasing Subsequences Stanley 5 Appendix A 75 35 Lectures 20 and 21 Tuesday November 4 and Thursday November 6 An Introduction to Symmetric Functions Stanley 5 Chapter 7 78 351 The Ring of Symmetric Functions 78 352 Proposed Bases for the Ring of Symmetric Functions 79 353 Changes of Basis lnvolving the m 82 354 ldentities and an lnvolution 85 355 Schur Functions 86 356 The Hook Length Formula 88 357 Orthogonality 90 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Chapter 1 Enumeration Algebraic combinatorics is a new sprawling and poorly de ned subject area in mathematics As one might expect any topic with both an algebraic and a combinatorial avor can be called algebraic combinatorics Topics that are often included in this area that we will not touch on are nite geometries polytopes combinatorial commutative algebra combinatorial aspects of algebraic geometry or matroids What we will do is start with ten lectures on the fundamentals of enumerative combinatorics more or less the study of counting includ ing methods generating functions bijections inclusion exclusion the exponential formula standard results permutation enumeration enumeration of graphs identities and some special topics the Marcos Tardos theorem We will then spend about four lectures and perhaps more toward the end of the semester on topics in graph theory that have a more algebraic avor This will be followed by about ten lectures on the representation theory of the symmetric group and symmetric functions This is the principal topic in the area of algebraic combinatorics that we will cover and it will hint at the appearance of enumerative methods within representation theory and algebraic geometry The course will nish up with a few lectures on special topics of particular interest including the combinatorics of card shuffling and the enumeration of alternating sign matrices 11 Lecture 1 Thursday August 28 The 12Fold Way Stanley 4 Section 11 There are three goals for this lecture The rst is to introduce some of the fundamental objects in enumerative combinatorics The second is to foreshadow some of the enumerative methods that we will discuss in depth in subsequent lectures The third is to give examples of why these objects might be of interest outside of combinatorics The 12 fold way is a uni ed way to view some basic counting problems Let f N a X be a function where lNl n and le x It is illustrative to interpret f as an assignment of 71 balls to z bins We arrive at 12 counting problems by placing restrictions on f On the one hand we can count functions f with no restriction those that are surjective and those that are injective On the other hand we can also count functions up to permutations of N andor permutations of X an alternative viewpoint is that the balls are either distinguishable or indistinguishable and the bins are either distinguishable or indistinguishable We form a M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid chart of the number of distinct functions f under each possible set of restrictions 71 71 1 Any f with distinguishable balls and distinguishable bins Each ball can go in one of z bins so there are x functions 2 lnjective f with distinguishable balls and distinguishable bins The rst ball can go into one of z bins the second can go into one of the z 7 1 other bins and so on so there are z 7 1 x 7 n 1 functions This expression occurs often enough to earn its own notation De nition The falling factorial is de ned to be znxz71z7n1 111 Stirling Numbers and Bell Numbers 3 Surjective f with distinguishable balls and distinguishable bins To choose a surjective function f we have to split the balls up into z groups and pair up each group with a bin First we count the number of ways to split the balls into z groups De nition A set partition of a set N is a collection 7139 B1 Bk of subsets called blocks such that the blocks are non ernpty disjoint and their union is all of N For example the set partitions of 1 23 are 12fd1fd2 fdmx3sornetirnes denoted by 123 1 2 3sornetirnes denoted by 123 1 3 2sornetirnes denoted by 132 1 2 3sornetirnes denoted by 123 1 2 3sornetirnes denoted by 123 The number of set partitions of an n elernent set is the Bell number The number of set partitions of an n elernent set into k blocks is the Stirling number of the second kind Sn We will discuss Stirling number of the rst kind in a couple lectures Clearly a surjective function f is built by choosing one of the Sn set partitions of N with z blocks and then assigning blocks to bins in x ways so the number of functions is zlSnx M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Before moving on to the next entry in the 12 fold way let7s study Stirling numbers and Bell numbers a bit more They are very common in combinatorics and we will get a taste of some methods in enumerative combinatorics Ideally we would nd a closed form expression for Snk andor Bn but this is not possible We can however write down a recurrence that Sn k satis es De nition Let will denote the set 1 2 n Proposition 11 By de nition S0 0 1 Forn 2 1 ifk gt n then Snk 0 while Sn 0 0 For 0 lt k lt n Snk kSn71kSn 71k 71 Proof We obtain a set partition of into k blocks either by partitioning n 7 1 into k blocks and placing n in one of the blocks or by partitioning n 7 1 into k 7 1 blocks and placing n into its own block 1 Recurrences are powerful tools for computing terms in sequences and for nding for mulas for sequences We can nd a similar formula for the Bell numbers Proposition 12 For n 2 0 n n B 1 B 39 n gt lt2 Proof A set partition of 71 1 is formed by creating a block with n1 and any choice of n 7i elements from and choosing a set partition of the remaining i elements 1 These recurrences will quickly lead to generating functions for these numbers but we will defer that until next time We will however consider an alternative representation of set partitions Put n dots in a row labeled 1 2 n lfi and j are consecutive elements in a block when the elements in a block are written in increasing order connect them with an arc from i to j This is a bijection between set partitions of n and arc diagrams in which each dot has at most one incoming arc and at most one outgoing arc Arc diagrams turn out to be incredible intuitive and convenient way to represent many objects including set partitions 112 Superclasses AriasCastro Diaconis Stanley We will brie y discuss a non combinatorial context in which set partitions arise Let Un be the group of upper triangular matrices with ones on the diagonal and entries in E It has been proved that classifying the conjugacy classes of Un is equivalent to classifying wild quivers which seems to be impossible Note I have been asked to expand on this comment This seems to be the sort of throw away line found in papers with no justi cation or reference I am attempting to track down a better explanation Knowing the conjugacy classes of a group is important in representation 11 M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid 4 theory and the theory of random walks on groups Instead of classifying conjugacy classes7 it is possible and of use to classify so called superclasses7 which are unions of conjugacy classes If X I z E Un x is upper triangular with zeroes on the diagonal and Y E Un7 conjugation looks like Y lXY 1 Y le Here7 Y allows us to add a multiple of one row up while sirnultaneous adding the same multiple of the corresponding column to the right For superclasses7 we look at the orbit of X under the action I ZpY7 where Y7 Z 6 This is clearly a union of conjugacy classes Here7 multiplication of x by Z and Y lets us add multiples of a column to the left and multiples of a row up It is not so hard to see that each superclass will have a unique representative with at most one non zero entry in each row and column above the diagonal For exarnple7 if n 37 the representatives have the form 7 1 0 0 1 7 0 1 0 0 1 0 7 1 7 0 0 1 0 0 1 0 0 1 7 0 1 0 0 1 7 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 where 7 is any non zero element of E1 How many possible forms are there for the representatives7 Exactly Why7 For each non zero entry in i7j for i lt j draw an arc in the arc diagrarn This give a set partition and de nes a bijection 113 Back to the 12Fold Way Any f with indistinguishable balls and distinguishable bins lf yl balls are placed in the rst bin7 yg balls in the second7 and so on7 then the number of functions is just the number of ordered surns yl yr n with yi 2 0 This brings up compositions and multisets De nition A composition of n is an expression of n as an ordered sum of positive integers For exarnple7 the eight compositions of n are 111172 1 11 2 11123113224 A composition with h parts is called a k composition A weak composition of n is an expression of n as an ordered sum of non negative integers A weak composition with h parts is called a weak k composition Proposition 13 The number of k compositions ofn is and the number of compositions ofn is 2n 1 The number of weak h compositions ofn is Proof A h cornposition of n can be represented by n stars77 in a row and putting h 71 vertical bars77 into h 7 1 of the n 7 1 gaps between the stars This can be done in ways A weak h cornposition of n can be represented by any arrangement of n stars77 and h 7 1 vertical bars There are ways to arrange n stars and h 7 1 bars A composition of n is obtained by choosing whether or not to put a bar in each of the n 7 1 gaps7 so there are 2 1 cornpositions 12 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid H D U 03 I 00 p H This stars and bars77 argument is very standard Note that the number of k compositions of n is the number of positive integer solutions to 1 zk 71 Another viewpoint on compositions is as combinations with repetitions77 or multisets Let denote the number of ways to choose k elements from disregarding order and allow repe titions that is7 the number of multisets of cardinality k on ln fact7 we just need to decide how many 1s7 how many 2s7 and so on should be chosen7 and the number of ways to do this is the number of weak n compositions of k so 2 2511 Z So the number of functions is lnjective f with indistinguishable balls and distinguishable bins Each box contains at most one ball we can choose the boxes with balls in ways Surjective f with indistinguishable balls and distinguishable bins Each box contains at most one ball Remove one ball from each box to obtain a multiset on X with n 7 z elements So there are functions m new Any f with distinguishable balls and indistinguishable bins We need to group the balls into at most z groups7 which can be done in Sn1 Snz ways lnjective f with distinguishable balls and indistinguishable bins If there are at least as many bins as balls7 there is one such f otherwise there are none Surjective f with distinguishable balls and indistinguishable bins We need to group the balls into exactly m groups and the order of the groups does not matter7 so there are Snz functions Any f with indistinguishable balls and indistinguishable bins We need to break 71 balls up into at most z parts7 where the balls are indistinguishable and the order of the parts doesnt matter These are precisely the integer partitions of 71 into at most z parts Let pkn denote the number of partitions of 71 into k parts Then the number of functions is p1n pmn lnjective f with indistinguishable balls and indistinguishable bins If there are at least as many bins as balls7 there is one such f otherwise there are none Surjective f with indistinguishable balls and indistinguishable bins We need to break 71 balls up into exactly z parts7 so there are pwn such functions 12 Lecture 2 Tuesday September 2 Generating Func tions Stanley 4 Section 11 Over the next few lectures7 we will be discussing a variety of enumeration problems and how to solve them One of the principal techniques used is the theory of generating functions 13 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid An abstract setting for many enumerative problems is that we have nite sets 505152 and we want to nd ldeally7 we would nd a closed form formula77 for lSnl which may involve a sum or a product Alternatively we could nd a recurrence equation7 an asymptotic formula7 or a generating function It is only through experience that the usefulness of generating functions can be appreciated De nition Let 107017 be a sequence The ordinary generating function of this sequence is Zanz n0 while the ecoponential generating function of this sequence is 00 1 Gz Zan n0 Here are some simple examples 1 The OGF for the sequence 1117 is The EGF is em 2 The OGF for the sequence 1237 is 13W The EGF is x 1em In this lecture7 we will use generating functions to prove combinatorial identities7 solve recurrences7 and obtain exact formulas for various sequences For all of these applications7 we will regard generating functions as formal power series that is7 members of the ring and thus there is no question of convergence Eventually we will use analytic methods to extract asymptotic information about the coef cients7 and in those cases we will need to consider convergence questions Here is a more complicated example with deep connections Example Let pn be the number of partitions of n Then Zpnx H 1 x211 x311 4119 H17 04 n0 13921 i1 Let pdn be the number of partitions of n into distinct parts Then Zpdnx 1 x1 x21 x3 H 1 n20 13921 Let p0n be the number of partitions of n into odd parts Then 1 Zp0nn H 211 2211 3211 4211 H 1 7 2171 n20 13921 13921 l 17 1 H1I li iH12iil7 iZI i21 igt1 showing that p0n pdnl We will have more to say about partition identities in the lecture on bijections M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Before looking at more applications7 we need to write down multiplication formulae for generating functions Proposition 14 Products of generating functions satisfy the following equations soswgtzeww n0 i0 M m czw The multiplication formulas suggest that we can use generating functions to prove com binatorial identities There are hundreds of examples7 but here are two Example Find a nice expression for Example Find a nice expression for We will see many more combinatorial identities in the lecture on the WZ method 15 M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid 121 Recurrences Generating functions are intimately related to recurrences For now7 we focus on nding generating functions given recurrences Example The Fibonacci numbers are de ned recursively by fn2 fn1fn and f0 0 and f1 1 We can nd both the exponential generating function and the ordinary generating function for f Let Z fnz n20 If we rnultiply both sides of the recurrence by x and sum over all n 2 07 we nd F 7 7 m W Z fn1xn n20 y F pic 42 1 7 12 gt lt1 7 172 5gt 7 1 1 i 1 7 75 1 7 x 1 7 x On the other hand7 let 171 n20 Multiply both sides of the recurrence by znnl and sum over all n 2 2 Then G x G z G Gz 6 7 flnll l Example Recall that the Stirling numbers of the second kind satisfy the recurrence Either way7 we nd that 1 fn V5 Snk kSn 717k Sn 717k 71 16 M390C Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Let be the exponential generating function of Sn k with respect to n Then 11 11 n Z Sn71k71m n2 Esau0 stmim nZk 39 nZk Fax 7 kaltzgtFk1ltzgt lnduction shows that em 7 1 Then 7 e 7 7 7 e kl kl H 239 7 so 501710 a 220 lt71gtkilt gt Example Since x 1 m k 25n7klm 5 17 nZk we ndthat x 1 Zk21Snk Zywii nZk 39 k21 39 x at e 1 n20 39 If we differentiate and compare coef cients we reprove the recursion Proposition 15 For n 2 0 122 Catalan numbers There is one other famous combinatorial sequence to consider namely the Catalan numbers Richard Stanley has a list of 166 different families of objects enumerated by the Catalan numbers We will de ne them as follows De nition Let the n th Catalan number 0 be the number of lattice paths from 0 0 to 7171 with steps 1 0 and 01 that never go above the line y x When n 3 there are ve such lattice paths The sequence of Catalan numbers begins 1 1 2 5 14 42 132 429 1430 4862 It turns out that we can obtain a closed form formula for 0 using recurrences and generating functions M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Proposition 16 Proof For n 2 07 Let FZCn n20 Then 7 1 zFx2 and F717174x39 2x Since 27172 1 y x1 172 if 7 y n71lt 4 n7 we ndthat 1 27172 1 7495 F 7 7 a xltni1 4 n f 1 271 i z n0n1 n D We will see a more combinatorial proof in the lecture on bijections One example of where the Catalan numbers appear in a non combinatorial context requires an alternative discription of them Lemma 17 The Catalan number On is equal to the number of n element multisets 0n Zn1Z whose elements sum to 0 For eaample when n 3 we have 000 013 022 112 and 233 Proof The total number of n element multisets is Call two multisets M and N equiva lent ifthey are translates of each other7 that is7 M a1 7an and N a1k 7asz for some h E Zn1Z Each equivalence class contains exactly one multiset whose elements sum to 0 So the total number is D Example What does this relate to Let us count the number of conjugacy classes of A E SLnCC with An 1 A matrix in SLnCC is diagonalizable with eigenvalues that are 71 1 st roots of unity and sum to 1 Each conjugacy class is determined by the multiset of eigenvalues So the number of conjugacy classes equals the number of n element multisets of Zn 1Z that sum to 0 M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid 123 q Analogues There is a special type of generating function that is often referred to as a q analogue Suppose that 0 counts a set S of combinatorial objects 0 may depend on one or more parameters Suppose there is a non negative integer valued statistic77 on the objects in S Let 01 be the number of elements in S for which the statistic equals 239 Then the q analogue of c is the polynomial generating function W 09 2 0111117 i0 and note that lirnqnjL Cq 0 Example The classic example of a q analogue is the q binornial coef cient q which is a q analogue of the binomial coef cients The idea is that the sum ofthe coef cients of q is which counts7 say7 k subsets of an n set7 and the coef cients are positive7 so the k subsets of an n set should have a natural partition into groups pararneterized by 239 01 7m7 and the coef cient of qi in 2L should count the k subsets in the group pararneterized by 239 In this case7 let the k subsets of an n set be represented by an n bit binary string 5 with k ones Let 25 ab 5a gt 85 This is the number of inversions of s we will talk about this more later De ne kn7 k lzlf s SHE 4L 1 q 2q2 q3 14 This can also be de ned as For exarnple7 2 k and 1 q qk l Then the recurrence l2l7l 1lWlZil shows that these two de nitions are equivalent 2 U lt17 397 lt17 E l l E E Proposition 18 The number 0 k 139 39 L r of m n 139 39 Ueetar space over a m39te eld E is mg Proof Let the number in question be G01 k and let Nn7 k denote the number of ordered k tuples 11 711k of linearly independent vectors We may choose 01 in q 7 1 ways7 112 in q 7 q ways7 and so Nn7k 01 71M 7 Q f 7 q 19 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid But we can also choose 11 yk by choosing a k dimensional subspace W in Gn k ways and choosing U1 in qk 7 1 ways 112 in qk 7 2 ways and so on so NW k 7 Gn7kqk 71qk 7 Q qk 7 q Thus 7 Q 71Q 7QQ 7qk 1 ll in a qk71gtltqkeqgtltqkeqk71gt kixinekifllq39 We will see other q analogues in the next lecture on permutation enumeration 13 Lecture 3 Thursday September 4 Permutation Enumeration Stanley 4 Section 11 Wilf 7 Chap ter 4 As we will see through this course the symmetric group Sn is rich in combinatorics Today we focus on some basic enumerative problems about permutations There are three ways that we will represent a permutation 7T 6 Sn The rst is with two line notation in which we write 1 2 n MD M 7Tn39 The second is one line notation or as a word where we forget about the top row The last way is via the standard representation in disjoint cycle notation where we require each cycle be written with its largest element rst and the cycles are written in increasing order of the largest element For example 2 3 4 6 7 7T7 2 7 1 6 5 74271365 7 1423756 LOU 1 4 De ne a map 7r gt gt 7 by writing 7139 in the standard representation and erasing the paren theses interpreting the result in one line notation In the above example 7 1423756 Proposition 19 The map 7r gt gt if is a bijection and 7139 has k cycles if and only ifir has k left to right maxima Proof We can recover 7139 from 7 by inserting parentheses at the beginning end and after every left to right maxima Thus this map is a bijection and 7139 has k cycles if and only if 7 has k left to right maxima M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 131 Permutation Statistics A permutation statistic is a map from Sn to N For this subsection7 write 7139 in one line notation ln lecture7 we will skip descents7 excedences7 and the major index for now and go to the inversion number The rst permutation statistic to consider is the number of descents in 7T denoted des7r De nition The descent set of a permutation 7T 1102 nan is the set D7T 239 11 gt ll1 and des7r For example7 the permutation 7T 4271365 has D7T 137 6 and des7r 3 The rst question is how many permutations have a xed descent set S We can only give a partial answer right now Proposition 110 Let S 5152 75k Q n 71 and let 045 be the number of7r 6 Sn with D7T Q S Then n 045 51752517535277715k Proof To nd 7139 with D7T Q S we choose 11 lt 12 lt lt as1 in ways7 15111 lt 15112 lt n751 52791 71 77781 n7sk 71 MS 81 82781 7178k 51752751753752n7sk Counting the number of permutations with descent set S can be done using this result and the Principle of Inclusion Exclusion7 which we will talk about in a few lectures The next question to address is how many permutations have a given number of descents Let An7 k Hn 6 Sn des7r k71l this is called an Eulerlan number Then the Eulerlan polynomial Anx is the corresponding ordinary generating function lt 152 in ways7 and so on Thus D Am 2 Am kw k n H The rst few Eulerian polynomials are Alm z Agm x2 A n42z3 x112 11x3 4 z 26952 66x3 26x4 955 Dgt 82 a VVVVV H 4 Dgt s 5 It is clear that the coef cients of these polynomials are symmetric7 since if TIT is the reversal of 7T the map 7r gt gt 7TT is a bijection on Sn that takes a permutation with k 7 1 descents to a permutation with n 7 k descents We will return to Eulerian numbers in a little bit The next statistic is the weak ereedenee number exc7r 21 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid De nition The weak epeedenee set of a permutation 7T a1a2an is the set E7T i a gt i and exc7r For example the permutation 7T 4271365 has E7T 123 6 and exc7r 4 Proposition 111 The number of permutations 7T 6 Sn with h weak epeedenees equals An h 1 Proof Let 7T alagai1ai1ai2 aik711an Then 7139 has n 7 h descents On the other hand i is a weak excedence of 7139 exactly when a lt a L or i n so there are k of them Thus 7r gt gt 7 takes a permutation with h weak excedences to a permutation with h descents 1 Any statistic on Sn distributed the same as des7r or exc7r is called Eulerian These are fruitful sources of combinatorial bijections and turn up in poset topology among other places The third statistic we consider is the inversion number inv7r De nition The inversion set of a permutation 7T a1a2an is the set ij i lt j but a gt a7 and inv7r is the number of inversions of 7139 For example the permutation 7T 4271365 has inv7r 9 The generating function for the number of permutations in Sn with a given inversion number has a nice factorization and leads us into the topic of q analogues Proposition 112 2 gm 1Q1q21qq2Q 1 WEST Proof Given a permutation a1 an1 in SW1 the letter n can be inserted in one of n spots and inserting it after a increases the number of inversions by n 7 i 7 1 for 0 S i S n 7 1 So by induction if 2 qmvm1q1q21qq2qn72gt7 WES nil then Z qinv7r 1q1q21qq2q 1 65 The fourth statistic is maj7r De nition The major indep maj7r of a permutation 7139 is the sum of all the numbers in the descent set of 7139 Proposition 113 The number of permutations 7T 6 Sn with maj7r h equals the number of permutations with h inversions Any statistic on Sn distributed the same as inv7r or maj7r is called Mahonian 22 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 132 Multiset Permutations and qAnalogues Many ofthese statistics can be generalized to permutations of multisets that is permutations 7T 1102 on where we allow repetitions We will focus on inversions As before 7139 has an inversion ij ifi lt j but a gt aj Writing down the corresponding generating function requires a so called q analogue of the multinomial coef cients A q analogue is a generating function in the variable q that reduces to a known quantity when q a 1 The classic example of a q analogue is the q multinomial coef cient mg which is a q analogue of the multinomial coef cients De nition De ne the q multinomial coe cient or Gaussian polynomial by n J 7 n q a1 am q allqllaglql amlql7 Where lqull1lql2lq lqu and Mg 1 1 TL qkil Proposition 114 The q binomial coe cients satis es the recurrence n n 7 1 n 7 1 l l k l l q q T q The q multinomial coe cients are products of q binomial coe cients in direct analogue to 39 1 ac x 1 multinornial coe cients and thus the q quot39 J are r 39 in q The q multinomial coef cients arise all over the place but here they are in the context of inversions Theorem 115 Let M 1amp1 m be a multiset of cardinality a1 am Then 2 qinvw 01 n a l SSM W q Proof De ne a map ltSMgtltSa1 gtltgtltSam a Sn 7T07T1 nm gt gt 7139 by converting the a i7s in 7T0 to the numbers a1 ai1 1 a1 ai1 2 a1 ai1 a in the order speci ed by in For example 21331223212313121 gt 42861537 We look at the multiset permutation 21331223 Then 7T1 tells us to change the 1s to a 2 and 1 from left to right 7T2 tells us to change the 2s to a 4 a 3 and 5 from left to right and 7T3 tells us to change the 3s to a 8 a 6 and a 7 from left to right Then 7139 is a bijection and inv7r inv7r0 inv7rm Using Prop 112 lnlql QM allqlmlamlql WESM M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid Here is another instance of q binornial coef cients Theorem 116 The number 0 k 139 39 L r of an n J39 39 vector space 7 over a nite eld E is mg Proof Let the number in question be Gn k and let Nn k denote the number of ordered k tuples o1 ok of linearly independent vectors We may choose o1 in q 7 1 ways 112 in q 7 q ways and so N01 k 7 if 71M 7 Q if 7 q But we can also choose o1 ok by choosing a h dirnensional subspace W in Gn k ways and choosing U1 6 W in qk 7 1 ways 112 E W in qk 7 2 ways and so on so N01 k 7 Gnkqk 71qk 7 Q qk 7 q Thus Q 71Q 7QQ 7qk 17 lnll n Gm qk71gtltqkiqgtltqkiqk71gt WW7le l 133 Cycles We turn to looking at the number of cycles and cycle lengths of a permutation De nition The cycle type of 7139 6 Sn denoted type7r is the vector c1 cn where 7139 has c cycles of length i Theorem 117 The number 0f7T 6 Sn with cycle type c1 cn is n 101c1l202c2l n0ncnl39 Proof Let 7T a1 an Parenthesize 7139 so that the rst c1 cycles have length 1 the next c2 cycles have length 2 and so on This gives a map from Sn to the set of perrnutations with cycle type c1 cn Now if 0 has cycle type c1 cn the number of ways to write 0 as a product of disjont cycles with the cycle lengths non decreasing is lclcll 41 an So the number of distinct o is V n 101c1l202c2l n0ncnl39 D Let cnk be the number of 7139 6 Sn with exactly h cycles Then 71 kcn k is the Stirling number of the rst kind and cnk is the signless Stirling number of the second kind They satisfy a nice recurrence and we can use that recurrence to obtain a generating function M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid Theorem 118 The sighless Stirling numbers of the rst hirid Ci i7 h satisfy the recurrence Cn7h n 71en 717hcn 7176 71 Theri Zenhzk x1z 2zn 71 k0 Proof For the recurrence7 choose a permutation in Sikl with h 7 1 or k cycles In the rst case7 include 71 in its own cycle In the second case7 n can be inserted in one of the cycles in any one of n 7 1 positions The generating function follows from the recurrence by induction D 134 Using Generating Functions to Find Expected Values We use the results of the previous section and generating functions to prove probabilistic statements about perrnutations in 8 Proposition 119 Let X S 7 N be a random variable on a set S that assumes hori negative iriteger values arid let pk be the probability that X h The eapeeted value ofX is E X l Z 7119 rL0 arid the variariee is 00 CO 2 VarX 2 71210 7 up 0 rL0 Let Go rL0 Theri 00 Ele f 1 2711 rL0 arid VarX f 1 f 17 f 12 2712p 7 2711 Example Note that cnhnl is the probability that a random perrnutation in Sn has h cycles De ne the random variable X Sn 7 N where X7T number of cycles in if We know that iProbX kw f it xk we 1z 2 x n i 1 k0 k 39 39 o 25 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid by Theorem 118 We can compute the expected number of cycles in a random permutation in Sn f z 7 ijw n 170 zi 1 We can also compute the variance in the number of cycles in a random permutation in Sn ni w winilw f f f lt 20 xizj gt n71 1 1 1 1 1 1 1 7 7 7 ff 23 JI IltHWHgt 1770l i 1ll l 1ll 27133 7 2 3 n 2 3 n 4 9 1 1 1 1 1 1 v X 1 7 7 771777777i am 23 71 4 9 n2 7T2 m logn yi E o1 So the average number of cycles in a random permutation in Sn is logn with standard deviation xlogn 135 Unimodality It is nice to know when nite sequences are unimodal7 that is7 the entries rise to a maximum and then decrease The most well known unimodal sequence is 0 It is generally ex tremely hard to determine the unimodality of a sequence In a few cases7 however7 generating functions can help Theorem 120 Newton7s Theorem Darroch7s Theorem Let p co clz 02x2 cnx be a polynomial all of whose roots are real and negative Then the sequence of eoe eients is unimodal pr1 gt 0 then the value ofk for which ck is mamimized is within one emupm This immediately shows that the binomial coef cients and the Stirling numbers of the rst kind are unimodal It takes more work to show that the Stirling numbers of the second kind and the Gaussian coef cients are unimodal 26 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 136 Cycle Index This subsection derives some powerful asymptotic results about the cycle type of a random permutation in Sn as n a 00 Let nz Z l7r 6 Sn type7r cl silxgz cc1mcn In a future lecture7 we will call this the cycle indecc of Sn Note that M V Z Probtype7T 6 Sn C fl quot n cc1mcn 00 tn on t 2 as H n1 This huge generating function has a very nice form Theorem 121 17 cm exp 2 73921 j Proof Using Theorem 1177 Czt t n20 tn 7 Z HnESn type7rclf1x 2 n20 n c12c2n 1 l I n39 mils nl 101c1l202c2l n0rcnl n20 c12c2n 7 M1 t2202 i Z lchll Z 20262l c1gt0 c220 6tm16t21226t3133 717 exp 7 y l 7 D So how do we apply this to get probabilistic results about permutations We need to point out one lemma Lemma 122 Let Z bj be a convergent series Then in the power series erpansz39on of 1 7 7 n litzbgt 725m 7 n 27 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid we have and so lim an 2 b Let us insert a brief example to show how useful this is Example The ordinary generating function for the sequence 01121314 is 7 l 1 7 t 7 0E g n By the lemma the ordinary generating function for the sequence of harmonic numbers 0111211213 is log 1 7 t 1 7t 39 Now we have our big theorem Theorem 123 Let S be a set of positive integers for which 1 Z 7 lt oo n65 n The probability that the cycle type of a random permutation in S agrees with c in all of its components whose subscripts lie in S goes to 1 7 saw a e E z exp s a SES 8 11965 51 5 Sasl as n 7 00 Here we is the operator that eactracts the coe cient of p0 from the generating function following it Proof In Cpt set w 1 ifi S that is we have no interest in any cycle lengths other than those in S Then we nd Czt exp i39eS i39 S 1 7 exp Z og1 it i39eS 1teXpltZigt i39eS 28 M390C Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid The coef cient of t as n a 00 is ex 7 165 by the lemma we obtain this by setting t 1 D Corollary 124 Letting S 1 shows that the probability that a random permutation in Sn has epaetly cl ped points goes to 1clle as n a 00 Corollary 125 Letting S r shows that the probability that a random permutation in Sn has epaetly CT r eyeles goes to 1e1Trcrcrl as n a 00 Corollary 126 Letting S 1479167 shows that the probability that a random per 2 mutation in Sn has no eyeles whose lengths are squares is e 7r 6 as n a 00 Corollary 127 Letting S 17 2 shows that the probability that a random permutation in Sn has equal numbers of Z eyeles and 2 eyeles is 1 32 7 6 E 2 F0 27g as 77 00 137 Square Roots Finally7 we discuss the question of how many permutations have square roots Theorem 128 A permutation a has a square root if and only if the number of cycles of even length is even Proof Let 739 be a permutation A cycle of length 2m in 739 breaks into two cycles of length m in 7392 A cycle of odd length in 739 stays in a cycle of odd length in 7392 So the given condition is necessary for o to have a square root Conversely7 if a has an even number of cycles of even length7 it is easy to construct a square root of 0 So a has a square root if and only if the cycle type c has even indexed components that are even The coef cient of zctnnl in ewltemgt2Zemgt33 is the number of permutations of n letters whose cycle type is c To sum over all cycle types we are considlering7 set 1 3 x5 17 and replace emmtmZm by the series with only even powers7 namely cosh x and set zgm 1 Let fn7 2 be the number of permutations in 29 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Sn with square roots Then7 2 fn 2V et cosht22et33 cosht44e 55 n n20 tt33t55 H h tzm e cos 2m mZI 1t t2 7 h 7 Vinyl gt110 2m t t3 t4 t5 1t 3 12 6ogm Thus the number of permutations f2n in Sn with a square root generates a sequence 11131260 14 Lecture 5 Thursday September 11 The Expo nential Formula Stanley 5 Chapter 5 We have seen many examples of exponential generating functions involving the exponential function This is not a coincidence These functions arise naturally as we will see in the Exponential Formula We will use the Exponential Formula to rederive some of the generating functions we have already found see new applications to Stirling numbers of the rst kind graph enumeration and subgroup enumeration and we will get a chance to reVisit the cycle index of the symmetric group from another point of View Let n EM 2m H n20 We will often denote the size of a nite set S as S Let K be any eld of characteristic zero like R or C with some indeterminates attached We will soon see why we might want K to have indeterminates Proposition 129 Given functions fg N a K de ne a new function h N a K by the rule hltXgt Z fltSgtgltTgt ST where X is a nite set and where S T ranges over all weak ordered partitions ofX into two blocks weak means that S or T may be empty and ordered means that S T and T S are distinct partition Then ENC Ef96Eg96 Proof Let X n Then hltngt i Zfltkgtgltn e k h0 30 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid since if S k then S can be chosen in ways and T is the complement of S in X The desired formula follows from the formula for multiplying two EGFs The next proposition is a direct consequence of applying Proposition 129 repeatedly Proposition 130 Let h 6 ll and f1 fk N a K De ne h N a K by hltSgt Zf1T1f2T2 filtTigt where T1L7 7T19 ran9es over all weak ordered partitions ofS into h blocks Then ENC Ef195quot39Efi95 This proposition quickly rederives the EGF of the Stirling numbers of the second kind with respect to k Example In Proposition 1307 let fi0 0 and 1 otherwise for 1 S i S h Then hn simply counts the number of ordered partitions of into h blocks7 so hn len7 On the other hand7 em 71 for each i7 so Em imam k er 7 N Thus the EGF for Snk for xed h is 6m 0k kl 39 At this point7 we need to insert a little sidenote about the one issue I brushed over when I said that we could just manipulate generating functions formally without worrying about convergence Note In the ring of formal power series or Cz17x27H 7L7 we have clearly de ned addition and multiplication operations But what is the situation with regard to inverses and composition The answers are that f has an inverse if and only if f0 31 0 and the composition f9 is well de ned if 90 0 In the case of composition7 this is because computing the coef cient of x in f9z requires a nite number of steps if 90 07 but requires in nitely many if 90 31 0 and7 say7 f is not a polynomial It is time for the fundamental result in this lecture which specializes to the Exponential Formula Theorem 131 The Compositional Formula Given f l a K and 9 N a K with 90 1 de ne h Na K by h0 1 and hS Z fltBlgt fltBigtgltkgt 7rBlBk where the sum ran9es over all set partitions 7139 of the set S Then ENC EgEf96 31 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Proof Let S n7 and let hkn ZW BIMBk flBll for xed k The B1 Bk are non empty since f0 07 so there are kl ways to order them Thus 9 Ehi95 EfW Now we sum over all h 2 1 D The EGF for the Bell numbers follows almost immediately from Theorem 131 Example In Theorem 1317 let f 9a 1 Then hn Bn the n th Bell number But Efz em 7 1 and Egz em7 so the EGF for the Bell numbers is an 00 x Em e5 1 2301 H n0 39 Roughly7 the idea of the Compositional Formula is that if we have a set of objects like set partitions that are disjoint unions of connected components like blocks of a partition7 and if there are fj possibilities for a component of size j and there are gk ways to stick together h components to form an object7 then hn is the total number of objects We so often want 9a 1 that we state this case as a corollary Corollary 132 The Exponential Formula Given f l a K de ne h N a K by h0 1 hers Z fltBlgtfltBigt 7rBlBk where the sum ranges over all set partitions 7139 0f the set S Then ENC eXpEf95 The Exponential Formula is often used in the enumeration of graphs Recall that a graph consists of a vertex set V and a set of edges E7 where an edge is an unordered pair of distinct vertices A connected graph is one in which for any two vertices i and w7 there are vertices 110 11111112 711 it such that mill1 is an edge for all i Example The number of graphs with vertex set 12 7n is 23 each unordered pair of vertices may or may not correspond to an edge Let Cn be the number of connected graphs on this vertex set Let fn C71 and hn The Exponential Formula shows that Ewe 223 exp Zea n20 n21 SO 2001 log 2022 32 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Now we are going to nd a generating function for the number of graphs on n vertices with exactly k connected components Here is where we begin to use the generality of the eld K lf K contains indeterminates say we can use f andor 9 to assign weights to each choice of components Example For this example let 0101 be the number of graphs with k components on 12n and let hn chntk kZO Write LXVL Fzt Z ckntkgt 7 n20 kZO 7139 Let fn tcn namely t times the number of connected components on n vertices we are weighting each component by t and the weight of a graph is the product of the weights of the components so a graph has weight tk if it has k components let gk 1 and let hn 2100 ckntk Then by the Exponential Formula Fxt Ehz exp Etch lt22 39 n21 More generally if is the generating function for some collection of objects then Ehzt is a multivariate generating function that keeps track of the number of components Note that hn is the sum of the weights of the graphs on n vertices so if t 1 we just get the number of graphs on n vertices We can go further with this example by writing Fzt Z tkEck kZO ZtkEmltgtk kl kZO i l 7 E Suppose that instead of graphs we were looking at permutations of n which are a disjoint union of cycles Let hn n and let 071 Cn k the signless Stirling number of the rst kind Then 1 7 z 1 so the EGF for the Stirling numbers of the rst kind is E z log Em Ecnkz 200110 log1 z71k n20 We turn to an application of the Exponential Formula in group theory 33 M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid Example Let G be a nitely generated group and let HornG Sn be the set of homomor phisrns from G to Sn What is 71 g lHornGSnl H Observe that there is a bijection between such hornornorphisrns and actions of G on The orbits of this action form a set partition 7139 of Letting fd gd the number of transitive actions of G on d the Exponential Forrnula shows that x n N Z lHornG Sal exp gd n20 d1 Since the orbit of 1 in such a transitive action has size d then the stabilizer of 1 is a subgroup H of G of index d Now the d 7 1 coset representatives of the non trivial cosets of H send 1 to each of 2 d and we can determine that assignment in d 7 1 ways Thus gd d 7 1lsdG where sdG is the number of subgroups of G of index d Therefore x N Z lHornGSnl H exp sdG d n20 39 d As a nal application of the Exponential Forrnula we will brie y revisit the cycle index of last lecture Example Recall that the cycle index of Sn is nz 2 7 1 6 Sn type7r cf1 2 c0102m Letting fk k 7 1lxg that is the weight of a cycle of length k is 1 we see that nltxgt7 Z fltBlgtfltBkgt 7rBlBk where the sum is over set partitions 7139 of Since 00 tn Ef n g7 the Exponential Forrnula says that V L Gtx exp xn In particular if we let 0 that gives weight 0 to each cycle of length 239 and hence weight 0 to each perrnutation with a cycle of length 239 Hence choosing a set S letting x 0 ifz39 S and s 1 ifz39 E S lets the coef cient of tnnl in Ct s count the number of perrnutations 34 M390C Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid none of whose cycle lengths are in S Afternatively7 letting xi 1 ifz39 S makes the weight of a permutation just Hid xii so extracting the coef cient of Hid afitnnl from Ctw counts the number of permutations with cl i cycles when 239 E S The rest of the lecture yesterday was devoted to showing that7 for appropriate choices of S7 we can rewrite Ctw and use a lemma to nd an exact formula for the limit of the coef cient of Hid zfit in Ctw as n a 007 which gives the limiting probability that a random permutation in Sn has cl i cycles for each 239 E S 15 Lecture 6 Tuesday September 16 Bijections So far7 we have focused on the algebraic generating function approach to proving combina torial enumeration theorems One alternative is to prove enumerative theorems bijectively For example7 one might show that the n th Catalan number On satis es 1 2n 0 7 n 1 lt n by exhibiting a bijection between Catalan paths gtlt n 1 and 0 1 sequences of length 2n with n zeroes here7 Catalan paths is shorthand for the lattice paths from 07 0 to 7171 with steps 07 1 and 17 0 that never go above y l have tried to avoid bijective proofs so far because 1 bijective proofs tend to arise after an enumerative formula has been found via algebraic means in order to lend insight into the problem7 2 algebraic methods are more powerful in the sense that few7 if any7 identities can be proved via bijections that cannot be proved by algebraic means7 and 3 bijective proofs tend to be more specialized Still7 bijections are an important and beautiful part of enumerative combinatorics7 so lets dive in We begin with a varied collection of nice7 classic bijections Example One extremely common class of bijections are lattice path bijections Many combinatorial quantities have lattice path interpretations The classic example here is the Catalan number We wish to prove the following proposition bijectively Proposition 133 The Catalan number On is given by On 1 n 1 n Proof Our bijection is not of the type suggested in the introduction7 highlighting the fact that it is not always clear what sets should be involved in the bijection But recall that On was de ned to be the number of lattice paths from 07 0 to n7 n with steps 01 and 17 0 that never go above y x Let this set of lattice paths be L1 Let L2 be the set of lattice paths from 07 0 to n71n1 with steps 01 and 17 0 Let L3 be the set of lattice paths from 00 to 7171 with steps 01 and 17 0 Obviously ngl 1 and ngl We will exhibit a bijection from L3 to L1 U L2 which would show that On lLll 7 7337 and this equals the desired quantity Let P be a path in L3 Either it is in L1 or it crosses the line y x Find the rst edge in the path that lies above the diagonal7 and ip the portion of the path occurring after that 35 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid edge along a line parallel to y x The resulting path is in L2 Since every path in L2 must cross y x at some point every such path can be obtained in this fashion in precisely one way and the ip is clearly reversible This is the desired bijection The Catalan numbers have a great many different interpretations Richard Stanley has a list of 166 interpretations In the next example we give bijective proofs of several of these leading up to a rather nice result on counting triagulations Example Proposition 134 The following sets of objects are counted by the Catalan number On 1 1 lattice paths from 00 to 7171 with steps 01 and 10 that do not go above y x 2 2 triangulations of a conyep n 2 gon into n triangles by n 7 1 non intersecting diagonals 3 Sg lattice paths from 00 to 2n 0 with steps 11 and 1 71 that do not go below y 0 4 S4 sequences i1 bgn of 1 s and Z s with non negative partial sums and total sum equal to zer 5 S5 plane binary rooted tree with 2n 1 vertices Here a plane binary rooted tree is a rooted tree in which each interior node has one left child and one right child Proof The bijection from 1 to Sg is achieved by rotating a lattice path 135 degrees and scaling by The bijection from Sg to S4 is achieved by recording a 1 for each northeast step and a 71 for each southeast step The bijection from S4 to S5 is more dif cult Given a plane binary rooted tree with 2n 1 vertices traverse it in depth rst search order and each time a vertex is visited except the last record the number of children minus one This gives a sequence of 17s and 17s of length 2n with total sum 0 The fact that the partial sums are non negative follows from the fact that a vertex is visited before any of its children and the left subtree of a vertex has exactly one more leaf node than interior node So traversing a vertex and its left subtree gives equal numbers of 17s and 17s and the traversal can be decomposed into several traversals of left subtrees so all partial sums must be non negative It is clear how to reverse the map It is probably easier to go from 1 to S5 directly The bijection from 2 to S5 is neat Fix an edge e in the n2 gon Given a triangulation T form a tree G in which the edges of the triangulation are the vertices of G the root is the vertex corresponding to e the left and right child are the other two edges of the triangle containing e and so on This gives a plane binary rooted tree with 2n 1 vertices and reversing the bijection is easy Example The next common class of bijections involves partitions and Ferrers diagrams Given an integer partition A A12k where A1 2 A2 2 2 Ak gt 0 its Ferrers diagram representation consists of h rows of left justi ed dots with A dots in row h Using boxes in places of dots gives us the Young diagram which will be integral to the second half of this course We call h the length l of A Here are some basic partition bijections 1 The number of partitions of n with length h equals the number of partitions with largest part h M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid F 9 Proof The transpose A of the partition A is the partition whose Ferrers diagram is obtained from the Ferrers diagram of A by re ecting across the diagonal y 7x If A has length k then A has largest part k D The number of partitions of n into odd parts equals the number of partitions of n into distinct parts Proof Given a partition A of n into odd parts7 merge pairs of parts of equal size until all parts are distinct We can recover A by breaking in half all even parts until there are only odd parts left D 373927739 aj2j z 2 x 2 The bijective proof of this result is our rst example of the lnvolution Principle7 which lets us give bijective proofs when there is subtraction involved Euler7s Pentagonal Number Theorem says that H17zi1Z717 i1 73921 Theorem 135 lnvolution Principle Suppose a nite set S is the disjoint union of a positive part SJr and a negative part S Suppose o S 7 S is an involution and sign reversing that is either Mp z or z and Mp are in di erent parts Then lSl lS l lFiw Sl lFi S l Proof of Euler s Pentagonal Number Theorem The coef cient of x on the left equals the number of partitions of n into distinct parts that have an even number of parts minus the number of partitions of n into distinct parts that have an odd number of parts Let the rst set be S and the second set be S We must show that m 7 WW 1 We want to nd a sign reversing involution on S SJr U S with no xed points except when n j3j i 127 in which case there will be one xed point in SJr or S as appropriate n j3j i 12 otherwise Given a partition A of length h in DO U D17 let p be the maximum index such that A1 A21A32App71 lfkpandAkporAkp1don7tdo anything Otherwise7 if Ak 3 p7 move the dots in the last row of A to the ends of the rst Ak rows of A If Ak gt p7 move the last dot in the rst p rows to a new last row of A Clearly the new partition has all distinct parts and except in the last case7 the parity of the length changed The only partitions for which we dont do anything have the form A17A1 71 7A1 7 h 71 with A1 7 h 71 h or k 1 There is one such partition if and only if n j3j i 12 for some j This proves the theorem D 37 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 16 Lecture 7 Thursday September 18 Bijections II Our nal type of basic bijection is a tree enumeration bijection Example Theorem 136 Cayley7s Theorem The number of trees that is connected graphs with n 7 1 edges on the vertem set equals 71 We will see an algebraic proof of this in a few lectures7 but today we will see a bijective proof There are several known ones we will look at the proof using so called Pr ufer codes Proof We will de ne a bijection P from trees on to Mn Let T be a tree on We are going to de ne a sequence of trees T17T27 7Tn1 Let T1 T Given Ti which has n 7t1 vertices7 let be the vertex of degree one with the smallest label Let it be adjacent to yi Delete and edge ziyi from T to get Ti Let PT y17y27 7 As an example7 consider the tree T with edges 127 157 177 1107 237 247 677 810 and 910 Then PT 22711771710710710 Note the following facts First7 VTk m7 7xn17n and ywl n The edges of Tk are for 239 2 h Now7 the number of times that 1 appears in 117 yn2 is the degree of o in T minus one By extension7 the number of times that a vertex 1 in Tk appears in 211 ynig is the degree of o in Tk minus one This implies that the degree one vertices of Tk are precisely those vertices which do not appear in 17xk1yk yn1 and M is that degree one vertex with the smallest l abel Thus given PT7 we can iteratively determine 1727 zn and this determines T Finally7 given an element of nln z7 this procedure produces a connected graph with n 7 1 edges7 which is a tree D Now that we have seen some basic types of bijections7 we further explore the one generic idea we have seen7 the lnvolution Principle7 in the context of determinants Here is a more complicated application of the lnvolution Principle Example In this example7 we compute the Vandermonde determinant Theorem 137 Let 71 371 271 72 72 272 V 39 3 1 2 n 1 1 1 Then detV H 7 7 A 1 iltjS Note that this theorem is easy to prove directly Letting xi xi we see that the determinant becomes 07 so detV must be divisible by m 7 xi Also7 the determinant is a polynomial of total degree at most 1 so we know detV is some constant multiple of ngiqgn 7 7 That this constant is 1 is easily determined But the involution proof leads us into a general way to evaluate determinants bijectively 38 M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid Proof On the one hand7 detV Z sgnax 1 man 765 On the other hand7 A Z1m9 l1m9 i 7 E where Zal and m j Q is taken from xi 7 7 There are 2 terms in this sum We associate each surnrnand in the expansion of A with a tournament A tournament is a directed graph on the vertex set with exactly one of the arcs tj and jn for each 239 31 j The weight wa of an arc 2397j is xi and the sign sgna of the arc is 1 ifz39 ltj and 71 ifz39 gt j The weight of a tournament T is wT H wa and the sign of a tournament T is sgnT H sgna The weight of a tournament is if mgquot where al is the out degree of 239 Then A Z sgnTwT T A tournament is transitive if whenever arcs tj and jk are present7 so is 239 This de nes a unique permutation of n so there are n transitive tournarnents If T is the transitive tournarnent corresponding to the permutation a then wTcr 39 39 V530 and sgnT 71 0 0 sgnU Thus detV Z sgnawTU USS Let 5 be the non transitive tournarnents with sign 1 and let S be the non transitive tournarnents with sign 71 To show that detV A7 it suf ces to construct a sign reversing involution on S 5 U 5 Note that T is non transitive if and only if there are vertices 239 and j with equal out degrees Given a non transitive tournarnent7 choose the least such 239 and then the least such j We may assume that T contains 239 j For each vertex k 31 thy there are four possibilities 1 T contains We and khj 2 T contains kn and j7 77 M7 Note that the number of k for which case b hold is one fewer than the number of k for which case a holds De ne T be reversing the arc tj and the other two arcs in the triangle tjk for which case a or case b holds Then the out degree of each vertex in T is the same as in T7 T is non transitive and t is reversible7 and t is an involution Also7 t reverses an odd number of edges7 so the sign of T and of T are different Thus t is sign reversing 1 3 T contains 239 k and 4 T contains kn and M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 17 Lecture 8 Tuesday September 23 Bijections II Aigner 1 Section 54 171 The Gessel Viennot Lemma The Gessel Viennot Lemma originally proved by Lindstrom is a powerful result connecting determinants of matrices to paths in graphslattices Let G V7 E be a nite acyclic directed graph with weighted arcs Let P be a directed path from 1 to w7 and let the weight of P be wP Haepu a7 with wP 1 if the length of P is 0 Suppose that V 017711n and W 101 7tun are two sets of vertices not necessarily disjoint To V and W we associate the path matricv M mlj7 where Pmiawj A path system S from V to W consists of a permutation 039 6 Sn and n paths Pl vi a wag Let sgnS sgnU The weight of S is 105 HwPl A path system is vemtem dz39sjomt if no two paths have a vertex in common Let VDPS be the set of vertex disjoint path systems from V to W Lemma 138 Gessel Viennot detM Z sgnAwA AeVDSP Before we prove this7 lets see an example Example We want to compute detM7 where mij for 1 S tj S 71 Consider the lattice Z2 with arcs directed up and to the right with all weights 1 Let Di 07 7m 71 1 and 10 j 7 17 ij 1 for 1 S tj S n Then the number of paths from vi to 10 is On the other hand7 the number of vertex disjoint path systems is 1 see drawing7 so the determinant is 1 Proof of the Gessel Viehhot Lemma Expanding detM gives a sum over 039 6 Sn with sum mands sgnltagtmlammmsgnltagt 2 mm 2 won P13A1HBO1 Ph3Ah4 Boh So detM is the sum ngnAwA A over all path systems from V to W We need to show that Z sgnBwB 07 B 40 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid where the sum is over all non vertex disjoint path systems B We will de ne a sign reversing involution on the set of non vertex disjoint path systems B Given B7 nd the smallest index 239 such that Pl crosses some P the rst vertex x on P1 shared with another path and the smallest indexj gt 239 such that z is on Pj Now swap the part of Pi and the part of Pj that come after x This gives a new non vertex disjoint path system and de nes a sign reversing involution Now we look at a very nice application of Gessel Viennot If you are reading the notes7 I know that this will be incomprehensible without the pictures drawn in class Sorry Example We begin with a regular hexagon of side length n triangulated into equilateral triangles of side length 1 A rhombus consists of two triangles with a common side We want to count the number of tilings of the hexagon by rhombi Associate to the hexagon a directed graph with each edge segment on the lower left edge of the hexagon labeled by 110 vn1 and each edge segment on the upper right edge of the hexagon labeled by we wn1 and edges in the directed graph go at 90 degrees or 30 degrees across one edge in the triangulation to the next edge The number of paths from Ai to B is muf 2n nz397j39 On the other hand7 rhombus tilings correspond bijectively to vertex disjoint path systems Just view the tiling in 3 D7 shading in rhombi tilted up and to the right7 and we get a series of white staircases from vi to 10 Thus the number of rhombus tilings is detltlt 1 gtgt 2 3 1939an Via row and column operations7 one can show that 2n n71 2ni det n Z J1sm n M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Chapter 2 Special Topics In this chapter we move from general methodstopics in enumerative combinatorics to more specialized topics These topics include permutation patterns the Matrix Tree Theorem and the BEST theorem chromatic polynomials including posets and Mobius inversion the WZ method and asymptotic enumeration 21 Lecture 9 Thursday September 25 Permutation Patterns Bona 2 Chapter 4 One of the hot new areas in combinatorics permutation patterns One way to view permu tation patterns is as a generalization of the inversion number of a permutation De nition For k S 71 let 7T 7T17T2 73 be a permutation in Sn and let 039 0102 47 be a permutation in Sk Then 7139 contains the pattem 039 if there is a subsequence 7317 7rlk of 7139 such that 2391 lt lt z and 7 gt 7 if and only if an gt 01 Example Let 039 21 Then each occurrence of 039 in 7139 corresponds to an inversion in 7139 Example Let 039 123 Then each occurrence of 039 in 7139 corresponds to a subsequence of three not necessarily consecutive increasing entries One way to visualize a pattern in a permutation is to look at the matrix representation A aij of 7139 We will de ne A by setting aij 1 if 7Tj n 1 7239 and 0 otherwise this way increasing subsequences correspond to a set of columns in which the heights of the 17s are increasing from left to right Each k gtlt k permutation submatrix de nes a permutation that is contained as a pattern in 7139 Types of questions we can ask about permutation patterns include 1 How many 7139 6 Sn do not contain 07 2 How many times does 7139 6 Sn contain 0 3 How many distinct patterns does 7139 6 Sn contain 43 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid We will only discuss the rst question Several chapters on this subject can be found in Bona Given a pattern a let Nno denote the number of 7139 6 Sn that avoid do not contain a The rst result is easy Proposition 21 Let 00 6 Sk correspond to permutation matrices that are equivalent under dihedral symmetries Then Nno Nno Proof If 7139 contains a and o is obtained by for example rotating the permutation matrix of o 180 degrees then the permutation obtained from 7139 by rotating the permutation ma trix of 7139 180 degrees avoids o This gives a bijection between o avoiding and o avoiding permutations D The six patterns of length 3 are 123 132 213 231 312 and 321 Of these 123 and 321 have equivalent permutation matrices and 132 213 231 and 312 have equivalent permuta tion matrices Theorem 22 Nn123 Nn132 This theorem shows that the number of permutations in Sn that avoid a given pattern of length 3 is independent of the pattern Proof We will de ne a bijection f from the set of 132 avoiding permutations to the set of 123 avoiding permutations Given a permutation 7139 its left to right minima are those entries which are smaller than all of their predecessors For example the left to right minima in 7139 67341258 are 631 Given 7139 let f7r be the permutation obtained by keeping the left to right minima of 7139 xed and rearranging the remaining entries in decreasing order So f67341258 68371542 Then f7r is 123 avoiding since it is the union of two disjoint decreasing subsequences We claim that the left to right minima of 7139 and f7r are the same Observe that to compute f7r we can imagine switching pairs of non left to right minima in 7139 that are not in decreasing order Since this moves a smaller entry to the right and a larger entry to the left f cannot create new left to right minima or destroy existing left to right minima Now to recover 7139 we keep the left to right minima of f7r xed and ll in the remaining entries from left to right by placing the smallest unplaced element that is largest than the left to right minimum to the left of the given position This is forced by the fact that 7139 must avoid 132 D Now we can compute Nn132 Theorem 23 Nn132 On the n th Catalan number Proof For 7139 to avoid 132 it must be that each entry to the left of n is larger than each entry to the right of n and that the entries to the left of n are 132 avoiding as are the entries to the right of n This shows that n71 Nn132 ZN132N1132 i0 Since N0132 1 and N1132 1 the two sequences satisfy the same recurrence and are equal M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid While investigations into pattern avoidance often do not have connections with other areas of math one of the original motivations for pattern avoidance comes from Knuth who showed that the 231 avoiding permutations are precisely the stack sortable permutations Given a permutation 7T 7T17T2 73 and a rst in last out stack we begin by placing 7T1 on the stack At each step we can put the next entry in 7139 reading left to right on the stack or we can take the top element in the stack and add it to our output Every entry must be put on the stack at some point Then 7139 is stack sortable if it can be passed through a stack with the elements removed in ascending order If it is stack sortable the unique way to sort it is if the next element to be added to the stack is greater than the top element of the stack remove the top element and otherwise add the next element For example 7139 85214376 is stack sortable We push 852 and 1 pop 1 and 2 push 4 and 3 pop 34 and 5 push 7 and 6 and pop 67 and 8 Theorem 24 The 231 auoiding permutations are the stack sortable permutations Our proof follows the presentation by Julian West in his 1990 PhD thesis Proof lfi lt j and if lt if then if has to be removed from the stack before 79 is added If i lt h and if gt Wk then if must stay on the stack until Wk has been removed So ifi lt j lt h and Wk lt if lt 7T 7T must be removed before 7Tj is added but after 7 But this is impossible so a stack sortable permutation cannot have a subsequence of type 231 On the other hand the algorithm fails to sort 7139 only if we must remove an element from the top of the stack which is not the largest element that hasnt been removed Then the top element of the stack is smaller than the next element to be added but larger than some later element These three elements form a 231 pattern So a 231 avoiding permutation is stack sortable For patterns of length greater than 3 questions about Nno becomes very dif cult However there was a long standing conjecture recently proved that shows that Nno is small relative to n for all 0 Theorem 25 Stanley Wilf conjecture proved by Marcus Tardos Let U be any pattern There epists a constant CU so that for all positive integers n Nno S 0 Moreover lim quot Nno Hoe epists Doron Zeilberger has interpreted the proof in terms of love patterns That feels a little too silly for me to present so I will interpret the proof in terms of American and European golfers Proof We rst prove the Furedi Hajnal Conjecture then show that the Furedi Hajnal Con jecture implies the Stanley Wilf Conjecture We say that a 0 1 matrix M contains a permu tation o if there is a h gtlt h submatrix of M that has a 1 in every position that the permutation 45 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid matrix of 039 has a 1 in the submatrix may have additional ones as well The Euredi Hajnal Conjecture states let 039 be a permutation matrix and let fna be the maximum number of 1s in a U avoiding n gtlt 71 0 1 matrix Then there is a constant d0 so that fna 3 dan For our interpretation of this problem7 we have a 0 1 matrix M in which the rows corre spond to 71 American golfers ranked by ability and the columns correspond to 71 European golfers ranked by ability Each 1 corresponds to a match between an American golfer and a European golfer For a xed a we want to avoid the match pattern a that is7 we forbid there to be k American golfers and k European golfers such that the 24th best American golfer amongst these k plays the 039Z th best European golfer What is the maximum number of matches fna7 Suppose a divides n Divide the American golfers respectively7 the European golfers into na teams7 where the a best American resp European golfers are on the rst team and so on A team plays a team from the opposite continent if there is at least one match between players of the teams A team challenges a team from the opposite continent if there are at least k players from the rst team who play against players on the other team The total number of pairs of teams that play each other is fna7 039 else 039 would occur in the full matrix If a team were to challenge k other teams because of the k players on the challenging team7 then M would contain k rows and k blocks containing those rows in which each block contains a one in each of the k rows In this case7 any k gtlt k pattern would be contained in M7 including 039 Therefore7 since M avoids a a team can challenge fewer than teams from the opposite continent So there are at most 2 E challenges The number of matches between teams that play each other but do not challenge each other is at most k 7 12 The number of matches between teams that challenge each other is at most 12 Thus fn k 712fna 2ak n fn 2k4 71 So we can take d0 2k4k7 proving the Euredi Hajnal Conjecture As for the Stanley Wilf conjecture7 let NU be the number of n gtlt 71 0 1 matrices that avoid 039 Clearly Nna S N a But to construct a n gtlt 71 0 1 matrix that avoids a we do the following Divide the golfers into teams of 2 We can choose the teams that play each other in at most Ny LZQT ways7 and there will be at most dam2 pairs of teams that play each other We can choose how the players within a pair of teams play each other in 15 ways So NU S NyL2U15d0n27 which implies that Nna S N a 3 15d Finally7 to show that the limit exists7 we claim that Nna Nma S Nmna lndeed7 we may assume that k precedes 1 in 039 Given 7T 6 Sn and 739 E Sm that avoid a construct a new permutation in Sm that avoid 039 by concatenating 7139 and 739 and adding 71 to each element of 739 This injection shows that Nn039Nm039 S Nmn039 so Nna is monotone increasing and bounded7 so the limit exists 1 Letting a k2 we nd The value of lim quot Nna 46 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid for various 039 has been investigated When 039 has length 37 the limit is 4 There are cases known in which the limit is 8 or 97 which prompted a conjecture that the limit is always an integer7 but Bona demonstrated a pattern 039 for which this limit is not rational 22 Lecture 10 Tuesday September 30 The Matrix Tree Theorem Stanley 5 Section 56 Graph theory began when Euler solved the Konigsberg bridge problem in 1735 Seven bridges connected parts of the city of Konigsberg see Figure 7 and the populace wondered if they could walk over each bridge once and return to their starting spot Euler viewed this as a multi graph problem7 with parts of the city represented by vertices and bridges by edges He proved that such a walk was not possible in modern terminology7 there is no Eulem39an tour We will prove this on Thursday Draw bridges and graph analogue The next major development in graph theory came in the mid 1800s Although the knight s tour problem which asks for a sequence of knight7s moves on a chessboard that visits each square once and returns to the starting square has been around since the 1400s7 19th century mathematicians were the rst to view it as a problem about visiting each vertex in a graph once and returning to the starting vertex in modern terminology7 nding a Hamiltonian cycle Hamilton even marketed the lcosian77 game7 which essentially asked for a Hamiltonian cycle on the vertices and edges of a dodecahedron The late 1800s saw increasing interest in what is now called graph theory7 from the 4 color conjecture in 1852 to the enumeration of graphs by Cayley and Sylvester for applications in chemistry Sylvester was the rst to use the word graph77 in this context Graph theory research exploded in the 1900s7 particularly with the rise of computer science and electronics We begin the next two lectures by stating and proving beautiful formulas for counting the number of spanning trees in a graph the Matrix Tree Theorem and the number of Eulerian tours in a digraph the BEST Theorem Then we apply the Matrix Tree Theorem in a couple enumerative contexts Further applications of the Matrix Tree Theorem and the BEST Theorem appear on the homework 221 Spanning Trees and the Matrix Tree Theorem Let G be a general graph Recall that a spanning tree of G is a subgraph H that is a tree and VH VG In a directed graph7 an oriented spanning tree with root 1 is a spanning tree in which all arcs point towards 1 Spanning trees have many applications in computer science and other elds often a network is represented by a graph and one wants to connect all nodes on the network as cheaply as possible by nding a spanning tree of the network One of the homework problems addresses this More importantly for our purposes7 spanning trees turn up in a number of enumeration problems In this section7 we prove the Matrix Tree Theorem7 which gives us a determinantal formula for the number of spanning trees in a graph7 and then apply it in later sections Let D be a directed graph digraph The adjacency matna AD of D is the n gtlt n 47 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid matrix aij where aij the number of arcs from 2 to 07 Let TD tij be the n gtlt 72 diagonal matrix with th outdeg2l The Laplacz39an LD of D is the matrix LD TD 7 AD Note that LD is independent of the loops in D For example7 let D be the digraph on vertices V 01702703704 with arcs 211212 21302 040304211214212 Then 010 0 0 0 0 0 AltDgt 010 0 1 1 10 10 0 0 0 0 0 0 TltDgt 0 010 0 0 0 3 1 i1 0 0 0 0 0 0 LltDgt 0 i1 1 0 i1 i1 i1 3 The adjacency matrix and the Laplacian are ubiquitous in graph theory we will see just a few of their uses Let LAD be the matrix obtained by deleting row 2 and column 2 from LD Let G be a graph The adjacency matricv AG of G is the n gtlt 72 matrix calj where the number of edges between 2 and 2 2 31 j a twice the number of loops at 2 Let TG tij be the n gtlt 72 diagonal matrix with th deg2l The Laplacitm LG of G is the matrix LG TG 7 AG Again7 LG is independent of the loops in G For example7 let G be the graph on V 01702703704 with edges 010270104702037212047213214 Then 0101 1011 Aw 0101 1110 2000 0300 HG 0020 0003 271071 7137171 MG 071271 7171713 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Let tG be the number of spanning trees in G and let tDi be the number of oriented spanning trees of D rooted at 1 Theorem 26 Matrix Tree Theorem Let G be a general graph Then tG detLlG spanning trees this determinant is independent of i There is a matrix theoretic proof of the Matrix Tree Theorem using the Cauchy Binet Theorem that can be found in Van Lint and Wilson 67 and there is a proof using the Gessel Viennot Lemma in Aigner 17 but we will prove it as a corollary of a more general theorem about directed graphs that can be proved by induction Theorem 27 Let D be a digraph with uertem set V o1on Then tD1i detLlD Before proving this theorem7 we show that the Matrix Tree Theorem is a corollary Proof of the Matricc Tree Theorem as a corollary of Theorem 27 Given a general graph G7 form a digraph D by replacing each edge pip in G by arcs pl71g and oi15 Then LG LD Furthermore there is a bijection between spanning trees of G and oriented spanning trees of D with root le39 given a spanning tree of G7 orient all edges toward le39 to obtain an oriented spanning tree of D with root pi and given an oriented spanning tree of G with root oi unorient the edges to obtain a spanning tree of G So tG tDol By Theorem 277 the number of spanning trees of G equals detLlD detLlG D Now we prove Thereom 27 Proof of Theorem 27 The proof is by induction on the number of arcs in D If D is not connected7 then the number of spanning trees is 07 while if D1 is the component containing le39 and D2 is the rest7 then detLlD detLlD1 detLD2 0 The Laplacian has determinant 0 since 1 is a right eigenvector If D has n 7 1 edges7 then D is a tree as an undirected graph If D is not an oriented tree with root oi then some vertex oj 31 le39 has out degree 07 LiD has a row of zeroes7 and the determinant is 0 Otherwise7 if D is an oriented tree with root 111 then LiD is conjugate to an upper triangular matrix with 17s on the diagonal and has determinant 1 If D has in gt n 7 1 arcs7 we may assume that le39 has no outgoing arcs these are not contained in any spanning tree with root 1 and do not affect detLlD Then some vertex oj 31 1 has outdegree at least two choose one outgoing arc e Let D1 be D with e removed and let D2 be D with other outgoing arcs from W removed By induction7 detLlD1 and detLlD2 equal the number of oriented spanning trees rooted at le39 in the respective graphs The number of such trees in D is the sum of these two numbers But also detLiD detLiD1 detLiD2 by the multilinearity of the determinant7 since D equals D1 and D2 except in row j and row j in D is the sum of row j in D1 and rowj in D2 D Lemma 28 Let M be an n gtlt n matrip with row and column sums 0 Let Mij be the matricc obtained by removing i th row andj th column Then the coe cient ofz in detM 7 x1 is 1ij1p M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Proof We prove this for i j n Add all rows of M 7 z except the last row to the last row This changes all entries of the last row to 7x Factor that 7p out7 giving Nz with detM 7 x1 7p detNx The coef cient of z in detM 7 x1 is 7detN0 Add all the columns of N0 except the last column to the last column The last column of N0 becomes the column vector 07 07p Expanding by the last column shows that detN0 pdetMm D Corollary 29 If D is a balanced digraph each yertem has the same in degree and out degree and the eigenvalues ofLD are M1 un 0 then the number of oriented spanning trees rooted at i is u1un1n Example Let G Kn7 the complete graph on n vertices Then LG n 7 1 Since 1 has eigenvalue 0 with multiplicity n 7 1 and eigenvalue n with multiplicity 17 then LG has eigenvalue n with multiplicity n 7 1 and eigenvalue 0 with multiplicity 1 So the number of spanning trees of G is 71 Cayley7s Theorem 23 Lecture 11 Thursday October 2 The BEST The orem Stanley 5 Section 56 231 The BEST Theorem An Eulerian tour in a graph respectively7 a digraph is a closed walk respectively7 directed walk which uses every edge respectively7 arc exactly once A graph or a digraph with an Eulerian tour is called Eulerian The Konigsberg bridge problem asks for an Eulerian tour in a multigraph with 4 vertices and 7 edges lnsert diagram There is a simple necessary and suf cient criterion for the existence of an Eulerian tour in a digraph Theorem 210 A digraph D without isolated vertices is Eulerian if and only if it is con nected and indegy outdegi for all vertices i E VD Proof D The analogous theorem for graphs is proved in precisely the same way7 so we will state the theorem and omit the proof Theorem 211 A graph G without isolated vertices is Eulerian if and only if it is connected and every yertep has even degree M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Now that we have settled the existence question for Eulerian tours7 we turn to enumer ating them It turns out that counting Eulerian tours in a graph is hard more formally7 it is P complete Counting Eulerian tours in a digraph is made possible by the BEST Theorem7 named after de Bruijn7 van Aardenne Ehrenfest7 Smith and Tutte Theorem 212 BEST Theorem Let D be an Eulerian digraph Let e be an arc with initial uertem i Let tDi be the number of oriented spanning trees rooted at i and let eDe be the number of Eulerian tours starting with e Then eDe tDi H 0utdegi 71l 116V Proof Given a tour E e17 em7 for each u 31 1 let eu be the last exit from u in the tour We claim 1 The vertices of D and the arcs eu form an oriented spanning tree T with root 1 2 Given an oriented spanning tree with root 1 we can construct Hug outdegi 7 1 Eulerian tours To prove 17 just observe that 1 T has n 71 edges 2 T does not have two arcs going out of the same vertex 3 T does not have an arc going out of i 4 T does not have a cycle To prove 27 given T7 we construct an Eulerian tour by starting at e and continue to choose any edge possible except we dont choose f E T unless we have to The set of last exits of the tour coincide with the set of edges of T The only way to get stuck is to end at i with no more exits available7 but with some edge unused lf so7 some unused edge must be a last exit edge that is7 an edge in T Let u be a vertex closest to i such that f E T outgoing from u is not in the tour Let y be the endpoint of f If y 31 1 since we enter y as often as we leave7 we dont use the last exit from y Thus y 1 But then we can leave 1 a contradiction 232 De Bruijn Sequences One problem solved by the BEST Theorem and the Matrix Tree Theorem is the enu meration of de Bruijn sequences A de Bruijn sequence of degree n is a binary sequence A 1102 agn so that each binary sequence of length n appears exactly once as the subse quence aim1 ain1 indices taken modulo n as i ranges from 1 to 2 We begin by constructing a digraph Dn and a bijection between de Bruijn sequences of degree n and pairs E7e where E is an Eulerian tour in Dn and e is an edge in D The vertices of Dn are the 2 1 binary sequences of length n 7 1 There is an arc from the vertex 51 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid a1an1 to the vertex b1bn1 if a2 an1 b1bn2 For convenience label the arc with bwl Each vertex in Dn has indegree 2 and outdegree 2 and Dn is connected so Dn is Eulerian and has 2 edges Draw de Bruijn graph Given an Eulerian tour E in D concatenate the edge labels in Dn in the order that they appear as E is traversed starting at e It is easy to see that we obtain a de Bruijn sequence and that each de Bruijn sequence arises in this way Therefore the number of de Bruijn sequences of degree n equals 2 times the number of Eulerian tours in D By the BEST Theorem and the Matrix Tree Theorem the number of de Bruijn sequences of degree n equals 2 detL1Dn It only remains to compute detL1Dn It is possible to compute this determinant by row and column operations but the following argument is more attractive One reason that the adjacency matrix of a digraph is so useful comes from this proposition Proposition 213 Let A be the adjacency matricc of a digraph D Then the ij entry in Ak equals the number of directed walks from i to W of length k The digraph Dn has a particularly nice property Proposition 214 Let u and i be any two vertices of D Then there is a unique directed walk from u to i of length n 71 Let A be the adjacency matrix of D These two propositions imply that A 1 is the 2 1 gtlt 2 1 matrix of ones But the eigenvalues of that matrix are 2 1 with multiplicity one and 0 with multiplicity 2 1 7 1 Thus the eigenvalues of A are 2 with multiplicity 1 and 0 with multiplicity 2 1 7 1 24 Lecture 12 Tuesday October 7 Abelian Sand piles and ChipFiring Games Today7s topic is just a fun one that has a connection to the Matrix Tree Theorem A survey of chip ring can be found on the arXiv co authored by Alexander Holroyd Lionel Levine Karola Meszaros Yuval Peres James Propp and David Wilson Let G be a nite directed graph on n 1 vertices Let s be a vertex with out degree 0 such that from every other vertex there is a directed path leading to 5 call 5 a global sink Let V G VG s o1 on and let d be the outdegree of 11 Let a chip con guration be a map a VG 7 N we think of C as representing stacking 01 chips on the vertex i for each non sink vertex i If 01 2 outdego that is there are at least as many chips on i as outgoing arcs of i then i is unstable and can re which removes outdego chips from i and puts one chip on w for each arc ow in G if it 31 5 This gives a new chip con guration Note that the total number of chips decreases by the number of arcs os in G A chip con guration is stable if no vertex can re and unstable otherwise A ring sequence F o ooolo1ogo2omom is a sequence of rings on o where o is the chip con guration obtained from Tl1 by ring 11 Relading a chip con guration means that we re vertices until we have reached a stable con guration It is easy to see that a stable con guration is reached in nitely many steps 52 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Proposition 215 Given a chip con guration 0 there is a unique stable con guration achieved from relaccing 0 that is independent of the choice and order of rings in the rela ation process Call this stable con guration the relaxation ofo and denote it by PAC Proof Let F o 00 01111 02112 omom be a ring sequence with om stable and let F G OO039111039212 0244 be some other ring sequence I claim that l S m and no vertex res more times in F than in F Suppose we have a counterexample with m l minimal Since oi is unstable in o it must be red at some point in F say i oi Then ring Dbl102Ui711i11m in order generates a valid ring sequence with nal stable con guration om Thus the ring sequences generated by 111112 oi1oi1 om and 12 1 form a smaller minimal counterexample This is a contradiction D There is an addition operation on chip con gurations lf 0102 VG a N are chip con gurations then 01 02 is the chip con guration for which 01 oz 1 011 021 that is you just combine the two piles of chips at each vertex Now generalize to chip con gurations that allow negative numbers of chips at vertices that is maps 0 V G a Z and allow any vertex to re Generalized chip con gurations form a group under naturally isomorphic to Z Let S be the generalized chip con gurations that can be obtained from the con guration of all zeroes by a sequence of rings Note that S is a subgroup under De nition The chip ring group GFG of G is the quotient ZnS We think of the cosets as being equivalence classes of generalized con gurations under ring At the moment it is not clear why GFG is interesting but we can compute lGFGll Let LG be the Laplacian of G and let LAG be the n gtlt n matrix obtained from LG by deleting the row and column corresponding to the sink 5 Then the rows of LAG generate S as a sublattice of Z But the index of S in Z equals the volume of the parallelopiped whose edges are the rows of LAG and this volume is equal to the determinant of LAG The Matrix Tree Theorem implies the following theorem Proposition 216 The order of the chip ring group GFG equals the number of oriented spanning trees ofG rooted at 5 So whats interesting about the chip ring group De ne a new addition operation 69 on chip con gurations with non negative numbers of chips where 01 EB 02 R01 oz De nition A chip con guration 0 is recurrent if given any other chip con guration 0 we can arrive at o by selectively adding chips at vertices and ring unstable vertices Note that adding chips at vertices and ring unstable vertices are commuting operations so we can do things in any order Also any con guration with at least dd 7 1 chips at each vertex is recurrent Theorem 217 Each coset of ZnS that is each equivalence class under ring contains emactly one stable recurrent con guration The group ZnS is isomorphic to the group of stable recurrent con gurations under 69 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Before we prove the theorem note if G has arcs o w and wo no con guration with zero chips at i and at w is recurrent since if we start with a con guration with a positive number of chips at i and it there is no way to arrive at a con guration in which neither 1 nor it has any chips Let 6 be the chip con guration with do outdego for all 1 Lemma 218 Each coset contains a stable chip con guration Proof Note that 67136 has at least one chip on each vertex and is in S Given any 04 E Z let in be the minimum of all coordinates of Oz and 0 so that m S 0 Then 6 a m5 P45 has nonnegative entries and is equivalent to a So 6 is a stable con guration in the coset of 04 Lemma 219 Each coset contains a stable recurrent con guration Proof Again let 04 E Z with in equal to the minimum of the coordinates of Oz and 0 Let d be the maximum outdegree in G Then 04 is equivalent to B 04 d7 m6 7 R6 Every entry in B is at least d Then 6 is recurrent given any con guration a compute Ro then add chips at each vertex until we arrive at 6 Then R is stable and recurrent D Lemma 220 Let 8 26 7 R26 Ifo is stable and recurrent o Ro 8 Proof Choose 7 so that o R6 C Let y6C86C267R26 Since 8 has non negative entries we can re all the unstable vertices in 6 C to get a then add 8 and relax so RM Ro 8 On the other hand since 6 7 R26 has non negative entries we can re all the unstable vertices in 26 to get 6 C which relaxes to a so RM o D Lemma 221 Each coset contains at most one stable recurrent con guration Proof Let 01 and 02 be stable recurrent equivalent con gurations Write TL 01 02 ZCiRiv i1 where R is the i th row in LAG Let J i c gt 0 and J i c lt 0 Then 039 3 01 Z 02 Z i6J ieJt Choose h so that o o he has at least lcildv chips at vertex 11 From 0 we can re each i in i E J a total of 7c times resulting in 01 he But Ro he 01 by the above lemma Similarly Ro he 02 Thus 01 02 D 54 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Now we can ask questions about GFG What is the identity element This is one of my favorite mathematical questions What is the inverse of a group element What is the structure of GFG as a nite abelian group ls there a bijection between oriented spanning trees and group elements We can compute the identity via Id R26 7 2 7 R26 7 We can compute the inverse of 0 via 0 1 R3673 7R3673 70 But this doesnt tell us what these elements look like as chip con gurations There are now several known bijections with spanning trees7 but I wont discuss them here Finally7 it turns out we can compute the structure of GFG Proposition 222 Any m gtlt n matricc L can be written L ADB with A B invertible with determinant i1 and D a diagonal matriw with diagonal entries 07 707d1 dk such that dileH This is called the Smith normal form ofL and the dl are the invariant factors Theorem 223 Let d17 dk be the invariant factors of L5G Then GFG E ZdlZ gtlt gtlt Zde Example Let G Kn the complete graph on n 1 vertices7 with one vertex designated as the sink Then LsltGgt7ltn1gtI7J7 I rmly where J is the n gtlt n matrix of all 17s7 I is the n 71 gtlt n 7 1 identity matrix7 J is the n 7 1 gtlt n 71 matrix of all 17s7 and u is the n 71 gtlt 1 matrix of all 17s De ne 1 u R1 u I J 1 7ut 0 I 39 R1L5GRz 1 n011 39 Thus GFG g 1Z 3 and R2 Then 25 Lecture 13 Thursday October 9 Mobius Inver sion and the Chromatic Polynomial Stanley 4 Chapter 2 We are going to start today with another graph theory topic with algebraic connections the chromatic polynomial Let G be a graph on n vertices and suppose is a set of colors A proper coloring of G is a map a VG 7 such that ifv and w are adjacent7 nv 31 nw 55 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid De nition Let XGUs be the number of proper colorings of G using h colors The smallest h for which XGUs 31 0 is called the chromatic number xG of G The 4 Color Theorem says that if G is planar that is7 can be drawn in the plane with no two edges crossing7 then xG S 4 Proposition 224 The quantity XGUs is a polynomial in k Thus it makes sense to call it the chromatic polynomial of G Proof 1 Let e be the number of proper colorings of G using exactly i colors Then X000 E 5i i1 is a polynomial in k 1 How can we compute XGUs Our rst method is to nd a recurrence for XGUs Consider two ways to reduce a graph to a smaller graph 1 Deletion If e is an edge in G7 delete it to obtain the graph G e 2 Contraction If e is an edge in G7 remove it and contract identify the two endpoints into one vertex to get Ge Theorem 225 960k XGek XGek Proof Let C1 be the set of k colorings of G7 let C2 be the set of k colorings of G e7 and let C3 be the set of k colorings of Ge We describe a bijection between C2 and C1 U C3 Let e have endpoints i and w Given a coloring n in C27 if i and it have different colors7 then this is a proper coloring of G Otherwise7 we obtain a proper coloring of Ge by using the same colors7 with the vertex formed by contracting i and w colored the same color as i and it were in n This is clearly a bijection D This is called the Deletion Contraction Recurrence The base case for this recurrence is the graph on n vertices with no edges7 which has chromatic polynomial k This recurrence not only gives an alternate proof that XGUs is a polynomial7 but also shows the following facts Proposition 226 1 Xgk is a monie polynomial of degree n with integer eoe eients 2 The eoe eients of XGUs alternate in sign 3 The eoe eient ofan l is 7m where m is the number of edges in G There are alternative formulas for XGU and this forces us to detour into the world of posets and Mobius inversion M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 251 Posets and Mobius Inversion A poset P a partially ordered set consists of a set also denoted by P and a partial order 3 where a partial order 3 on a set is a binary relation that satis es 1 Re exivity For all z 6 P7 x S x 2 Antisymmetry If x S y and y S L then x y 3 Transitivity If x S y and y S 2 then x S 2 If x lt y and there is no 2 for which z lt z lt y then we say y covers x We often represent posets by their Hasse diagram7 which is the graph whose vertices are the elements of P7 whose edges are the cover relations7 and if z lt y then y is drawn above x Here are some important examples Example The set is a poset under the usual order on integers whose Hasse diagram is just a path on n vertices Example The set of subsets of is a poset under inclusion whose Hasse diagram is the n dimensional hypercube projected to two dimensions This is often called the Boolean algebra Example The set of positive integral divisors of 71 forms a poset in which the partial order is given by divisibility Example The set of set partitions of is a poset under re nement That is7 7139 S 039 if 039 is obtained from 7139 by merging blocks of 7139 Example There are many posets on the set of permutations on Sn One such poset is the inversion poset7 in which 7139 S 039 if 039 is obtained from 7139 by a sequence of transpositions that put a smaller number after a larger number De nition The poset P has a 0 if there is a unique minimum element of P It has a T if there is a unique maximum element of P A chain in P is a sequence of elements 0 lt 1 lt lt zk The poset is graded if every maximal chain has the same length Then there is a unique rank function p P a 07771 such that if y covers 7 then My 996 1 Note that all of the above poset examples are graded respectively7 by size7 size7 number of prime factors7 number of blocks7 and inversions De nition The Mobius function of a nite poset P is the map M P gtlt P a Z de ned inductively by Mar 1 Way i 2 WW mgzlty 57 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Theorem 227 Mobius Inversion Formula Let P be a nite poset and let fg P a 3 Then 995 Elm7 for all x e P 219 if and only if 1 29y y7z ySw Corollary 228 Dual Form Let P be a nite poset and let fg P a C Then 995 Zfy7 far all z e P 212w if and only if 1 290le 212w We will defer the proof until next time Lets see some applications Example Let P be the natural poset on Then 1 z y Way 1 t 961171 0 otherwise Mobius inversion says that if 13971 92 2 f 77 j1 then f0 90 79041 Example Let P be the set of subsets of Then MS 71gt S T We can prove this by induction for example Mobius inversion says that if 95 Z T for all S c X Tgs then fS Z 1 S T 9T Tgs This is what is generally called the Principle of Ineluslon Emeluslon For example recall the problem of counting derangements that is how many permutations 7T 6 Sn have no xed points Let Dn equal the number of derangements in Sn let fS be the number of 58 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid permutations in Sn whose xed points are exactly the elements of S and let 95 be the number of permutations in Sn that x the elements of S Then 95 Z T for all S c X T25 D f0 ngmm Z lt71gti ltn e 239 n 2 y T i0 i0 252 Back to the Chromatic Polynomial De ne a poset P called the bond lattice of G The elements of the poset are partitions of VG into connected components blocks The partitions are ordered by re nement Example Consider the graph G with edges abacbcbd Cd The bond lattice is a graded poset with 1 element of rank 0 ve elements of rank 1 six elements of rank 2 and one element of rank 3 Given a partition 7139 of VG into connected components let X7k be the number of proper k colorings of G in which 1 all vertices in a block have the same color 2 any two adjacent blocks have different colors Then Xak X0k Note that knumber of blocks in 7r 2 X0 72 Let fU X7k and 90 knumber 0f 13106151 7 By dual Mobius inversion X7r 2 717 0 knumber of blocks in c7 72 X0 Z 67 0knulnber of blocks in 7 In the above example Xgk k4 7 5k3 8k2 7 4 Next comes a surprising result about XG71 which we would not necessarily expect to be meaningful De nition An acyclic orientation of G is a way to orient each edge of G so that no cycles are created Let wG be the number of acyclic orientations of G Theorem 229 Stanley M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Proof This holds trivially for G En7 the graph with no edges7 since XEnU k and wEn 1 If we could show that wG wG e wGe7 then by induction on the number of edges in G7 MG wG6 wG6 1 Xae11 1Xae1 71 XG571 7 XGe71 1 Xa1 To prove the recursion for wG7 take an acyclic orientation of G Removing e gives an acyclic orientation of G e But if two acyclic orientations of G are the same except for the orientation of e7 we get the same acyclic orientation of Ge twice In this case7 if e Ly7 this means there is no directed path between my in either direction So we also get an acyclic orientation of Ge Thus wG wG e wGe D 26 Lecture 14 Tuesday October 14 The Chromatic Polynomial and Connections We begin with a proof of the Mobius lnversion Formula The techniques used in this proof are not so important for us7 but are useful for more detailed studies of posets Proof of Mobius Inversion De ne the incidence algebra of P over C by P PgtltPgtC y0ifx y This is an algebra under convolution7 de ned by 5V96y Z ammo m z y This convolution is associative and 6ltzygt 9 otherwise is a 2 sided identity lf E P has a 2 sided inverse 4 then xx 1 1z 6Q n 1 Thus x7x 31 0 for all z E P On the other hand7 suppose x7x 31 0 for all z E P Then it is easy to verify that if 4 is de ned inductively by 1 1 6mm 39 y 5 y rig isummSKZ lw2 27y 3 P 7 17 60 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid then 4 is a left inverse for g and by associativity a right inverse as well In particular a is the inverse of i 1 x S y y and so of 6 The algebra P acts on the right of CF by few 2 mm x ySw for f 6 CF and g E P Then fC 9 means 900 2 f y ySw but multiplying by a on the right shows that f go so 1 2 yaw 96 219 261 The Graph Minor Theorem One of the two most important results in graph theory along with the 4 color theorem over the past 30 years is the Graph Minor Theorem by Robertson and Seymour Though not directly connected to the chromatic polynomial it does demonstrate that the operations of edge deletion and edge contraction have a lot of signi cance De nition A graph H is a minor of a graph G if H be can obtained from G by a sequence of deletions and contractions Theorem 230 Graph Minor Theorem Any in nite family of graphs contains one that is a minor of another Corollary 231 Any minor closedfamily f that is whenever G E 7 so are all the minors of G has a characterization of the form quotG E f if and only if the following nite list of graphs does not include any minors of G1 Example 1 The minor closed family of forests graphs with no cycles is the family of graphs that do not have 03 the cycle on 3 vertices as a minor Wagner7s Theorem The minor closed family of planar graphs is the family of graphs that do not have K5 the complete graph on 5 vertices or K33 the complete bipartite graph on two sets of three vertices as a minor 2 The minor closed family of graphs that can be embedded in a torus has not been so characterized though it is known that a minimal list of avoided minors contains at least 16000 graphs M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 262 Hyperplane Arrangements One signi cant area of study related to combinatorics re ection groups Lie theory etc is the study of hyperplane arrangements A hyperplane arrangments in R is just a collection of hyperplanes For example let A x 0y 0 z 0 z y 0 We can construct its intersection poset LA whose elements are the intersections of 0 or more hyperplanes in A ordered by reverse inclusion The characteristic polynomial of A is given by gt040 2 W37 Wm 16LA For the given example XAt t3 7 4t2 5t 7 2 Theorem 232 The quantity 71 XA71 is the number of regions that the hyperplanes partition A into The quantity 71T quotkAXA1 is the number of bounded regions where the rank ofA is the dimension of the space spanned by the normal vectors to the hyperplanes in A In fact the characteristic polynomial is a generalization of the chromatic polynomial Theorem 233 Let G be a graph with uertices o1 1 De ne the graphical arrangement AG in R corresponding to G to have the planes 7 pj 0 for mi 6 Then XAGt X00 Moreover if E is a nite eld and Ag the arrangment A viewed as a set of hyperplanes over an Fq vector space has the same intersection poset as A then XAq is the number of points in l9 that do not lie on any hyperplanes in Aql Chapter 3 The Representation Theory of the Symmetric Group and Symmetric Functions Symmetric function theory and its connections to representation theory and algebraic ge ometry have dominated the world of algebraic combinatorics over the past twenty years or so There are at least two perspectives to take on symmetric function theory On the one hand it has long linked tableaux combinatorics to the representation theory of the symmetric group and the general linear group and more recent research has developed combinatorial theories for the representation theory of other groups There are also deep connections between symmetric functions and topics in algebraic geometry like the Schubert calculus of Grassmanians and Hilbert schemes On the other hand tableaux combinatorics and symmetric functions provide a uni ed setting in which to for example study enumer ative questions about permutations partitions and topics like Polya theory Our goals in this chapter are four fold The rst goal is to discuss the representation theory of the symmetric group and present the RSK algorithm This is a reasonably natural way to introduce tableaux The second goal is to introduce symmetric functions and their algebraic properties and to connect them to the representation theory of the symmetric group The third goal is to link the algebraic and combinatorial properties of symmetric functions with the combinatorics of permutations and other objects The fourth and nal goal is to use all of this theory to solve a variety of problems 31 An Introduction to the Representation Theory of Finite Groups Sagan 3 Chapter 1 This section presents the most basic facts about the representation theory of nite groups It does not correspond to a lecture rather you should read it to prepare yourself for the lectures in this chapter It is important to remember that we are only working with nite groups much of what is written in this section is not true for in nite groups Representation theory turns out to be fundamental in virtually all of mathematics besides the combinatorial implications we will eventually discuss an application to probability theory namely card 63 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid shuf ing and the convergence rates of random walks 311 Representations Let G be a nite group Given a complex nite dimensional vector space V of dimension n let GLV denote the group of invertible linear transformations of V Then a complex representation of G of dimension n is a group homomorphism p G a GLV alternatively a representation of G is a group action of G on a vector space In this situation V is a called a G module We obtain a more concrete description of p if we choose a basis of V Then if dimV n we can view p as a homomorphism p G a GLnCC where GLnC is the group of invertible n gtlt n complex matrices The only problem is that a different choice of basis for V will give us a different homomorphism p G a GLnC For example let V C3 and let Sg act on V by permuting the standard basis vectors e1 eg and egg this de nes a homomorphism p into GL3CC With respect to the standard basis we nd 1 0 0 0 0 1 pltlt1gtlt2gtlt3gtgt o 1 o pltlt123gtgt 1 o o 0 0 1 0 1 0 0 0 1 0 1 0 0 H O 90133 9132 OHO OOH O 100 001 pltlt132gtgt 0 1 0 HOG 1 0 o 1 pltlt1gtlt23gtgt 0 0 But with respect to the basis o1 100 o2 110 and 113 011 we nd 1 0 0 i1 0 2 9123 0 1 0 p123 1 0 71 0 0 1 0 1 1 i1 0 2 1 0 pltlt123 1 1 1 p132 71 0 0 0 1 1 1 1 2 0 1 2 90132 1 1 1 9123 0 1 1 1 1 0 0 1 1 To correct this ambiguity we say that two representations p and 739 are isomorphic if there is a change of basis matrix T E GLnC such that 79 T 1pgT for all g E G For any group G there is the trivial representation of dimension 1 corresponding to the trivial action of G on a one dimensional vector space 64 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 312 Irreducible Representations Given two representations p and 77 we can form a new representation p 69 7 by taking a direct sum Under this new representation p 69 7 9 p9 EB 797 where the direct sum of the two matrices p9 and 79 is the block matrix with p9 in the upper left7 79 in the lower right7 and zeroes elsewhere On the other hand7 given a representation 07 suppose we can nd a change of basis matrix T so that o is isomorphic to a representation in which each matrix 09 is a block matrix with the same size blocks for each 9 Then we can decompose o as the direct sum of two smaller dimensional representations For example7 let p be the three dimensional representation where Sg permutes the standard basis vectors in C3 and let 7 be the trival representation Then with respect to the standard basis7 p 69 7 is given by 1 0 0 0 0 0 1 0 peTgtltlt1gtlt2gtlt3gtgt 8 3 f 8 panama 3 f 8 8 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 pe7123 3 3 f 3 ltp 7gtltlt13gtlt2gtgt f 5 8 8 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 p 7132 1 8 1 8 pe7123 8 1 1 8 0 0 0 1 0 0 0 1 With respect to some other basis7 these matrices would not be block matrices7 but the representation would still be isomorphic to the direct sum of p and 7 Irredueible representations are the building blocks for all representations A representa tion p is irreducible if it cannot be written as the direct sum of two representations If p is not irreducible7 it is reducible Maschke7s Theorem says that every representation of a nite group G has a unique decomposition up to the ordering of the factors into the direct sum of irreducible representations of G Thus if we can understand all irreducible representations of a group7 we can understand all representations of a group One important representation of a group G is the regular representation This represen tation has dimension lGl and corresponds to G acting by left multiplication on 917 79n7 the vector space of all complex linear combinations of the elements of G7 also known as the group algebra of G It turns out that the regular representation p of G decomposes into irreducible representations as p 7 an irreducible representation of TT That is7 the multiplicity of 7 in p is dim7 for every irreducible representation of G In particular this proves that the number of irreducible representations of G is nite and that M Z mime 7 an irreducible representation of G 65 M390C Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid ln fact7 the number of irreducible representations of G equals the number of conjugacy classes in G Finally7 given an irreducible G module W and a G module V7 the multiplicity of W in V equals the dimension of HomlV7 V 313 Characters It is well known that the trace of a matrix is invariant under conjugation Therefore7 if p is a representation of G on the G module V7 the trace of pg does not depend on the basis chosen for V It makes sense7 therefore7 to de ne the character of p to be the function X G a C where xg Tracepg Moreover7 X is constant on the conjugacy classes of G For example7 for the 3 dimension representation 739 of Sg given in Subsection 3117 Xltlt1gtlt2gtlt3gtgt 3 xltlt123gtgt xltlt132gtgt o and xltlt12gtlt3gtgt xltlt13gtlt2gtgt xltlt1gtlt23gtgt 1 The characters corresponding to irreducible representations are called irreducible characters Since the number of irreducible characters equals the number of conjugacy classes of G7 the character values for G can be represented in a conjugacy table Here is the table for SS with the rows labeled by irreducible characters and the columns labeled by representatives of conjugacy classes 123 123 123 X1 1 1 1 X2 1 1 71 X3 2 i1 0 32 Lectures 16 and 17 Tuesday October 21 and Thurs day October 23 The Irreducible Representations of the Symmetric Group Sagan 3 Chapter 2 In this section we construct the irreducible representations of the symmetric group and look at related results The number of conjugacy classes in Sn is the number of partitions of 717 so we seek irreducible representations indexed by the partitions of n We begin by constructing a family of representations Mquot that are indexed by the partitions of u but are not7 in general7 irreducible We will nd the Specht module Squot as a submodule of Mquot and we will show that Squot is irreducible We nish this section by nding a basis for Squot and by nding the decomposition of Mquot into Specht modules 321 Constructing the Irreducible Representations Sagan 3 Sec tion 21 We build up to the construction of Mquot via several de nitions and then offer several examples De nition Let A k n A tableau of shape A or a A tableau t is obtained by replacing the dots in the Ferrers diagram of A by positive integers A tabloid of shape A t is an equiv alence class of tableaux of shape A7 where two tableaux are equivalent if the corresponding rows of the two tableaux contain the same elements A Young tableau of shape A is a 66 M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid tableau of shape A in which each integer from 1 to n appears exactly once and a Young tabloid is an equivalence class of Young tableaux De nition Let VA be the vector space spanned by the Young tabloids of shape A The group Sn acts on the set of Young tabloids by perrnuting the entries this de nes a representation Mquot of Sn on VA Here are all Young tableaux and all Young tabloids of shape 21 Young tableaux 2 3 1213 Young tabl01ds 37 27 17 lfA3then M3CC12 3 and this is the trivial representation If A 21 then 1 2 1 3 2 3 21 7 7 7 M TC 3 7 2 1 Finally if A 111 then 1 M144 2 c 7 E 7 7 lwlwlel lwlelwl lelwlwl E L L lelwlwl and this is the regular representation 322 The Specht module S Sagan 3 Section 23 We will identify the representation Squot by nding a subspace of VA on which Sn acts Given a subset H Q Sn de ne the group algebra surns H 2w 6 Sn WEH H Z sgn7r7r 6 Sn WEH Given a tableau t with columns 0102 Ck let 0 SC gtlt gtlt Sck 3 Sn be the column stabilizer of t which acts on t but only perrnutes entries within colurnns Then pt C t is the polytableau associated to It By replacing each tableau in pt by the corresponding tabloid we obtain the polytabloid 6 associated to t For example let 4 1 2 t 7 3 5 67 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Then and 5 2 3 5 2 1 4 1 39 De nition The Specht module Squot is the subspace of Mquot spanned by the polytabloids et where t has shape A Now7 it is not even clear that this de nition makes sense we need to show that Sn acts on this subspace This follows from the next lemma Lemma 31 Lett be a tableau and 7139 6 Sn Then 1 Cm nC r l 2 C7 nCt n l 3 em net Proof For part 17 we have ant 7ft up to column equivalence 039 6 07 lt gt lt gt nilont t up to column equivalence lt gt n lon 6 Ct lt gt o E nCtnil The proof of parts 2 and 3 are similar D Part 3 shows that Sn does acts on Squot and therefore Squot is a module 323 The Specht Modules are the Irreducible Modules Sagan 3 Section 24 Next we have to order all the partitions of n so that we can deal with the MA one by one One extremely important partial order on partitions is the dominance order If A and a are partitions of 727 then A dominates a written A E a if A1 A2 AZ E 221 222 n for all 2 2 1 It is convenient to re ne or extend this to a linear order7 and this is given by the lexicographic order on partitions Here7 A 2 a in the lex order if7 for some 27 Aj 22 for j lt2 and AZ gt m We need a criterion for dominance involving tableaux Lemma 32 Dominance Lemma Lett be a A tableau and let 5 be a n tableau If for each indecc 2 the elements of row 2 2n 5 are in dl erent columns in t then A E a Proof We can sort the columns oft so that the elements in the rst 2 rows of s are in the rst2rows of t Thus A1A22M1M M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid We need to show that the Specht modules are irreducible they are pairwise non isomorphic and they are a complete set of irreducible Sn modules This requires many delicate lemmas De ne the inner product on Mquot where ltt7 5gt 5ts Lemma 33 Sign Lemma Let H be a subgroup of Sn 1 fir E H then 7TH H ir sgnirH Otherwise let W H H 2 For any um E Mquot ltH uogt ltu H ogt 3 If the transposition bc E H then H k8 7 bc for some h 6 Sn 4 ft is a tableau with bc in the some rorn oft and bc E H then H t 0 Proof Part 1 follows from from the multiplicatiVity of the sign function For part 2 we have ltH uogt Z ltsgn7r7ruogt Z ltu sgnir7r 1ogt ire WEH Replace 7139 by 7T 1 in the nal sum to get ltu H ogt In part 3 we can take h K for the subgroup K e bc of H In part 4 we just apply part 3 the tabloid t is annihilated by bc D Corollary 34 Lett be a A tableau and lets be a u tableau If Cs 31 0 then A E u If A u then Ct s iet Proof Suppose b c are in the same row of 5 If they are also in the same column of t then G contains bc and Cs 0 by part 4 of the previous lemma By the dominance lemma A E u If A u then s 7Tt for some 7139 6 0 by the dominance lemma Then 05 sgnirCt t iet by part 1 of the previous lemma D Corollary 35 Ifu 6 MM andt is a u tableau then Ct u is a multiple of et Theorem 36 Submodule Theorem Let U be a submodule of Mt Then U 2 SM or U Q 5 so SM is irreducible M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Proof Let u E U and t be a u tableau Then C i fet for some f E C There are two cases Suppose that f 31 0 for some choice ofu and t Then fet Ct u E U and et 6 U But et generates S 7 so U 2 SM Now7 if Cfu 0 for all u and t7 consider any u E U and u tableau t Then ltuetgt ltu70tgt ltOutgt 0 Thus u 6 Std D Lemma 37 If HomS M is non trivial then A E u IfA u then HomS M is one dimensional Proof Let 0 31 6 E HomS M Extend 6 to HomM 7 M by setting 0S u 0 Then7 for some et 6 Squot7 0 7e 9a 9Ct 05900 By the corollary7 A E u If A u then 0et cet and acting on t by 7139 proves this holds for all polytabloids D Theorem 38 The Squot for A h n form a complete list of irreducible modules for Sn Proof By the Submodule Thrn7 the Specht modules are irreducible The number of Specht modules matches the number of irreducible Sn modules By the above lemma7 if Squot S 7 then HomS 7 M and HomSt 7 MA and A u D Corollary 39 The MM decompose as Mr em KMSquot 324 Finding a Basis for S Sagan 3 Section 25 There are a lot of polytabloids and the linear relations between them are unclear in partic ular7 it is unclear what the dimension of Squot is So we would like to nd a basis for 5quot It is easy to state the relevant theorem A standard Young tableau is a Young tableau in which the entries in each row and each column are increasing Theorem 310 The set et t is a standard Young tableau of shape A is a basis for SA In the interest of time7 we will only sketch the proof Proof 1 De ne a dominance order on tabloids 2 Show that t is the maximum tabloid that appears in et this shows the et are indepen dent M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 3 Show that for any tableau t7 the polytabloid et is a linear combination of standard polytabloids e5 B Let fquot be the number of standard Young tableau of shape A Then the dimension of Squot x A is f and Z W m Ahn 325 Decomposition of M Sagan 3 Section 29 In this subsection7 we want to write Mquot as a sum of Specht modules Why Partly it is just because the Mquot are nice modules to understand7 but mostly it is because the decomposition will introduce a fundamental generalization of standard Young tableaux De nition The content of a tableau of shape A is the composition a M1 um where u equals the numbers of is in T A tableau is a semistandard Young tableau if the entries in each row are weakly increasing and the entries in each column are strictly increasing Theorem 311 MM 2 AKAMSA7 where KM is the number of semistandard Young tableau of shape A and content a The method of proof is to show that HomS Mf has a basis parameterized by If T T is a SSYT of shape A and content a We will omit the lengthy proof Example The theorem shows that M221 g S221 EB S331 9 2832 9 2841 9 85 Example Note that KM fquot7 the number of standard tableaux of shape A So MOquot 2 ems This shows that the regular representation decomposes as a sum of all irreducible modules appearing with multiplicity equal to their dimension 33 Lecture 18 Tuesday October 28 The RSK Al gorithm Stanley 5 Section 711 Now that we have constructed the irreducible representations of the symmetric group7 what next The rst step is to examine the identity 2AM f 2 n more closely can we nd a bijective proof7 for example This question leads to a lot of beautiful combinatorics that is the subject of the next two subsections after which we will meander back to the representation theory of Sn The identity 2AM f 2 n begs for a bijective proof that is7 a bijection between pairs of SYT of the same shape and permutations in Sn ln fact7 we can do better The Robinson Schensted Knuth RSK Algorithm offers a bijection between pairs of SSYT of the same shape and in nite N matrices with nite support7 and it specializes the bijection we desire This bijection is more than a curiosity it has many consequences7 as we shall see 71 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 331 Row Insertion The key component to this bijection is row insertion Let P be a SSYT and let h be a positive integer The row insertion of h into P7 written P H k is de ned as follows 1 Find the largest r such that P1J11 S k if P11 gt k let r 1 2 If P1 doesnt exist because P has r H 1 colurnns7 append h to the end of the rst row and stop The resulting array is P H k Otherwise7 replace P1 by k and insert P1 into the second row using the same algorithrn Continue until an element is inserted at the end of a row The result is P H h For exarnple7 let 112 l5l5l6 233l6l6l8l P446l l 1 g lnserting 4 results in 112 4 l5l6l 2335 l PH44466l iii 8g where the elements that were inserted into a row are in positions 17 57 27 47 37 47 43 the inserted elements are 4 57 67 and 8 respectively The set of positions into which an element was inserted is called the insertion path P H 4 We need to prove two useful properties of insertion paths7 the rst application of which will be the fact that the new array is also a SSYT Lemma 312 1 The insertion path does not move to the right 2 Ifj S k then P H j lies strictly to the left ofIP H j H h andIP H j H k does not emtend below the bottom of P H j Proof 1 Suppose that r75 6 P H Either P711 gt PTS or P711 does not exist In the rst case7 when PTS is burnped to row r 17 it cannot be inserted to the right of P711 In the second case7 when PTS is burnped to row r 17 inserting it in position 5 1 would leave a gap in the row A number must burnp a strictly larger nurnber7 so h is inserted into the rst row of P H j to the right of j The element j burnps is at most the element that h burnps7 so by induction7 for all rows7 P H j is left of P H j H The last elernent inserted in P H j went at the end of its row If P H j H k inserts an element into this row7 it goes at the end of the row and the insertion algorithrn stops E0 D Corollary 313 IfP is an SSYT then so is P H k Proof The rows of P H h are clearly weakly increasing If a burnps b7 then a lt b7 and b is not inserted to the right of a in the next row7 so b is below a number smaller than b Thus P H h is increasing in columns M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 332 The RobinsonSchensted Knuth RSK Algorithm Let A ahMZl have non negative integer entries with nitely many nonzero entries Associate to A a two line array 2391 2392 Z39m w A J1 J2 jm where the columns ihjr are listed in lexicographic order with multiplicity aij if ihjr ij For example if 10 A02 11 w i 1 1 1 2 2 3 3 A 1 3 3 2 2 1 2 39 Note that A is a permutation matrix if and only if wA is a permutation written in two line notation We construct a pair of SSYT P Q from A as follows Begin with P0 Q0 Q 0 Once PtQt is de ned construct Pt1Qt1 by DOM then 1 Pt1 Pt H jt1 2 QML is obtained from Q by adding 25L in the position that makes Qt have the same shape as 13 Then P Q PmQm and we write A IE P Q This is the RSK Algorithm The SSYT P is called the insertion tableau of A and Q is called the recording tableau of A Example Applying RSK to the above A and um we have Theorem 314 RSK Theorem The RSK algorithm is a bijection between N matrices A aij of nite support and ordered pairs P Q of SSYT of the same shape In this correspondence the content ofP is the vector of column sums ofA and the content on is the vector of row sums ofA M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Proof By the corollary P is a SSYT Also P and Q have the same shapes and speci ed contents and that Q is weakly increasing in rows and columns It remains to show that Q is strictly increasing in columns and that this is a bijection lf ik ik in am then jk S jk1 By the lemma the insertion path of jk1 lies strictly to the right of the insertion path of jk and does not extend below that of jk1 Thus ik will be inserted to the right of ik in Q and Q must be strictly increasing in columns It is easy to reverse the RSK procedure by nding the largest element in Q break ties by nding the right most occurence reverse insertion of the corresponding element in P and iterating The only question is if starting with a pair P Q yields a valid two line array It suf ces to show that if ik ik then jk S jk1 Let ik QM and ik QM so r 2 u and s lt i The element P7W lies at the end of its row when we begin to apply inverse bumping to it So the inverse insertion path of PM intersects row u to the left of column 1 That is at row u the inverse insertion path of PM lie to the left of that of PM More generally the entire inverse insertion path of PM lies to the left of that of PM Thus before removing ik the two element jk and jk1 appear in the rst row with jk to the left of jk1 So jk S jk1 D Corollary 315 The RSK algorithm is a bijeetion between permutation matrices and SYT tableaum of the same shape In particular SAW 0 quot2 nl 333 Growth Diagrams and Symmetries of RSK There is an alternate geometric description of the RSK algorithm involving growth diagrams that among other things leads to a quick proof of one symmetry of the RSK algorithm 2 preliminary comments 1 Standardization 2 Containment of partitions Given w wl wn 6 Sn construct an n gtlt n array with an X in the wi th square from the bottom of column i just as we did when talking about permutation avoidance We are going to label each of the n 12 points that are corners of squares in the array by integer partitions Label all points in the bottom row and left column with the empty partition Q If three corners of a square 5 have been labeled M A V we label the upper right corner by the partition p de ned by 1 L1 lf 5 does not contain an X and A M V let p A 2 L2 lf 5 does not contain an X and A C M V then M was obtained from A by adding 1 to some part A Let p be obtained from M by adding 1 to M11 3 L3 lf 5 does not contain an X and M 31 V then let p maxiV 74 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 4 L4 lf 5 contains an X7 then A u V Let p be obtained from A by adding 1 to A1 This generates the growth diagram 9w of it If a point p is labeled by A then W is equal to the number of X7s in the quarter plane to the left and below p Let A be the partition in row 2 with the bottom row being row 0 and column 72 Then 2 Let Mi be the partition in column 2 and row 72 Then A0 C A1 C C A and 0 C M1 C C a correspond to SYT Pw and Qw Theorem 316 The SYT Pw and Qw are the same as the SYT obtained from it via RSK Proof Let the partition in row 2 and column j be V2j For xed j 0 V0j g V02 g g Wm when lVijVi 7 Lj 01 Let T2j be the tableau of shape V2j obtained by inserting h into the square Vkjnuh 71j when 0 S h lt2 and lykjVk 71jl 1 We claim that T2j has the following description Let 21117 ikhjk be the positions of X7s to the left and below T2j7 with jl lt jg lt lt jk Then T2j is obtained by row inserting 21227 72k beginning with Q The proof of the claim is by induction on 2 j It is true if239 0 or j 0 lf2 gt 0 and j gt 07 then T2 7 1M77 T2j 7 17 and T2 7 17j71 satisfy the desired conditions Now7 check that T2j satis es these conditions using the rules L1 L4 lf2 727 then Tnj 07201 7202 lt H721 So Tnn Pw is the insertion tableau of 2U7 while Qw is the recording tableau D Corollary 317 Let A be an N matri2 of nite support and let A IE P7 Q Then A is symmetric if and only ifP Q Corollary 318 The number ofSYT of size n equals the number of inuolutions in Sn Thus the generating function for tm the number of SYT of size n is Ztn739exp n20 39 34 Lecture 19 Thursday October 30 Increasing and Decreasing Subsequences Stanley 5 Appendix A Schensted7s original motivation for the RSK algorithm came from studying increasing subse quences in permutations Schensted7s Theorem has been generalized to Greene7s Theorem7 and the techniques used to prove Greene7s Theorem will be useful to us in a couple weeks when proving the Littlewood Richardson Rule Let 7T 7T1 73 6 Sn and h E N Let Ik7r denote the maximum number of elements in a union of h increasing subsequences of 7139 Let Dk7r be the maximum number of elements in a union of h decreasing subsequences of 7139 For example7 if 7139 236145 E 56 then 0a 07117139 47127139 13M 6 D07T 07D17T 27 D27T 4 D37T 57D47T 6 Let sh7r denote the shape of the insertion and recording tableaux of 7139 under RSK 75 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Theorem 319 Greene7s Theorem Let 7T 6 Sn and A sh7r Then 11 A1k and Dklt7Tgt X1 This theorem tells us 1 a way to nd Dk7r and Ik7r and 2 when two permutations have the same shape The proof of theorem will also discuss when two permutations have the same insertion tableau De nition A Knuth transformation of a permutation 7T switches two adjacent entries a and c provided that next to a or c is an entry b with a lt b lt c Two permutations 7139 o are Knuth equivalent written 7139 5 o if one can be transformed into the other by a sequence of Knuth transformations For example 54123 51423 51243 15243 15423 and 12543 are all Knuth equivalent Theorem 320 Permutations are Knuth equivalent if and only if their insertion tableau coincide De nition Let T be a SYT The reading word of T is the sequence of entries of T obtained by concatenating the rows of T bottom to top For example the tableau 468 579 3 468 5798 579 has reading word 579468123 Note that a tableau can be reconstructed from its reading word by nding the descents in the word Theorem 321 Each Knuth equivalence class contains eccactly one reading word of a SYT and consists of all permutations whose insertion tableau is that SYT In the above example the only reading word in the given Knuth equivalence class is 54123 and it corresponds to the tableau Lemma 322 For any h the values Ik7r and Dk7r are invariant under Knuth transfor mations of 7139 Proof Note that W nilum satis es Ik7r Dk7r and Ik7r Dk7r and 7139 5 o if and only if 7T 5 0 so it suf ces to prove the lemma for Ik7r Suppose 7139 contains acb and the Knuth transformation switches a and c to obtain 0 when l is on the other side the situation is analogous Let Ik7r m Clearly Iko S m If Iko lt m it means that every collection 51 5k of disjoint increasing subsequences of 76 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 7139 which cover in elements has an element7 say 51 containing a and 0 In this case7 if b does not belong to some 51 we replace 0 by b in 51 obtaining a contradiction lf b does belong in some 51 say 52 then 51 m1ltlt7risltaltclt7ris3lt 52 W11 39lt7Tjtltblt7rjt2ltquot397 and the increasing subsequences 5 1 m1ltltms ltaltbltms3 lt 52 W11 lt lt79 ltClt7Tjt2 ltquot397 cover the same elements of if which is again a contradiction So Iko m D Lemma 323 Any permutation is Knuth equivalent to the reading word of its insertion tableau Proof lt suf ces to show that readingPk 5 readingP k for any h and SYT P Consider readingPk We can switch h with its left neighbor until h winds up to the right of exactly those entries to the right of h in the rst row of P e h Then the left neighbor of h is the entry that is bumped to the second row of P7 and it can be switched with its left neighbor until it winds up in the corresponding spot in the permutation7 and so on D Corollary 324 Let P be the insertion tableau for 7139 Then 7139 and readingP have the same values ofIk and Dk Lemma 325 Let 7139 be the reading word of a SYT T Then T is the insertion tableau 0f7T Proof of Greene s Theorem We may assume that 7139 is the reading word of a SYT T Note that each row of T is an increasing subsequence in if so 11 Z A1quot k7 and each column of T is a decreasing subsequence in if so Dk7r 2 A A For example7 consider 7T 592671348 with insertion tableau Now7 pick a box in T along the lower right border in the above example7 59767747 or 8 Let it be in row h and column l Then Ik7rDl7r2A1AkA Agnkl But an increasing subsequenbe and a decreasing subsequenbe have at most one element in common So Ik7r Dl7r S n kl 77 M390C Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid So equality holds throughout with INT A1quot k7 and Dklt7Tgt X1 For any given h or Z we can nd a suitable box along the border so this holds for all h and Corollary 326 The shape 0f7T is invariant under Knuth transformations But here is a stronger corollary Corollary 327 The insertion tableau of a 7139 is invariant under Knuth transformations Proof Let 7Tk be the permutation in Sk formed by the entries 1 h in 7139 Then PW is the insertion tableau formed by the h smallest entries in P Note that any Knuth transformation of 7139 either does not change 7Tk or transforms it into a Knuth equivalent permutation This does not affect the shape of 7Tk which is the shape of PW But the shapes of PW for all k uniquely de ne P Since all PW are unchanged by Knuth equivalent permuations so is This proves the remaining two theorems 35 Lectures 20 and 21 Tuesday November 4 and Thurs day November 6 An Introduction to Symmetric Functions Stanley 5 Chapter 7 Unfortunately it is essentially impossible to introduce symmetric functions in a motivated way But as we build up the theory of symmetric functions we will see more and more connections to the representation theory of the symmetric group the RSK algorithm enu meration problems and more In this section we de ne the ring of symmetric functions introduce ve bases for the ring prove that they are bases nd transition matrices for pairs of bases introduce a scalar product and a special ring homomorphism and prove algebraic equalities involving the bases 351 The Ring of Symmetric Functions The fundamental object of study in this section is the ring of symmetric functions It is misleading to refer to the ring of symmetric functions for three reasons The rst reason is that the functions in question are multi variate polynomials there is essentially no theory of more general symmetric functions The second reason is that this ring can be de ned over any commutative ring B so it is not unique However we will only be interested in this ring de ned over Q or more rarely Z The third reason is that the symmetric functions in question can be functions of nitely many variables x x1x2 xn or in nitely many 78 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid variables x x1z2 yet another reason that the ring in question is not unique As you might expect it is easier to write down examples using nitely many variables But more importantly some theorems need to be proved for functions of nitely many variables and then hold for functions of in nitely many variables by letting n go to in nity Before we give formal de nitions here are a few examples of symmetric functions in three variables 1 2 3 1M 1M 2M 2 2 3 1 1M 1M 2 2M 3 21 22 23 7 512 7 513 7 523 More formally the symmetric group Sn acts on the ring Qz1z2 an by permuting the variables and a polynomial is symmetric if it is invariant under this action Let A be the subring of symmetiic functions A function f E A is homogeneous of degree k if every monomial in f has total degree k Letting A be the Q vector space of homogeneous symmetric functions of degree k we may write An as the vector space direct sum An kZOA27 and observe that An is a graded Q algebm Recall from the de nition of a vector space direct sum that if f f0 f1 f2 with fk 6 A5 then all but nitely many fk must be 0 If we repeat the above de nitions with an in nite set of indeterminates we obtain A k20Ak the graded Q algebra of symmetric functions in in nitely many variables We will brush over technical details related to having in nitely many variables but it is true that A is the inverse limit of the An in the category of graded rings If we replace Q by Z in the above de nitions we obtain AZ EBkZOAQ the graded ring and Z module of symmetric functions in in nitely many variables We will rarely refer to AZ but we will see that several bases of A are also Z bases of AZ 352 Proposed Bases for the Ring of Symmetric Functions A natural rst step in the examination of A is to nd one or in our case ve bases for A as a Q vector space We will de ne the ve bases in this subsection In the next subsection we will build up the tools for proving that they are bases and relating them to one another Then we will prove that they are bases and give transition matrices for pairs of bases In each basis the basis elements are indexed by partitions A lfa 041042 ozn E N let x denote the monomial x1 2 mgquot The simplest basis consists of the monomial symmetiic functions Let A be a partition of length at most n We de ne the monomial symmetiic function mAz1 xn Ea z 79 M3900 Algebraic Cornbinatorics Fall 2008 Instructor Geir Helleloid where the sum ranges over all distinct permutations of the entries in A For exarnple7 mg 1 m1 12n 2 2 2 m2 xlzzn 77111 E ii j ilti 7 2 77121 i iij 1399 There is no need to wait two subsections to prove that the m form a basis it is obvious that mA1 2 A S n and W k forms a Q basis of A and mA21 2 A S n forms a Q basis of An The second basis consists of the elementary symmetric functions Let A be a partition We de ne the elementary symmetric function e21x2 2 by 51 511512 CT E iil39uil39T i1ltquot39lti f For exarnple7 e0 1 51 12nm1 52 j 77111 ilti 511 5151 m2 277111 5251 m21 3771111 We will show that exlxn A1 3 n and W k forms a Q basis of A and eAxl 2 A1 3 n forms a Q basis of An The third basis consists of the complete homogeneous symmetric functions Let A be a partition We de ne the complete homogeneous symmetric function h21zg 2 by 111 Ml112 hr Z iil39uil39T i1 quotSii For exarnple7 he 1 hl 12nm1 h2 Zi j 7712 77111 iSJ39 hll hlhl 7712 277111 I121 h2h1 ms 277121 3771111 80 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid We will show that hA1n A1 3 n and lAl k forms a Q basis of A and hAz1 7x A1 3 n forms a Q basis of An The fourth basis consists of the power sum symmetric functions Let A be a partition We de ne the power sum symmetric function pz1x2 7x by 10A PA1PA2quot39 pr i For example7 100 1 101 7 12nm1 p2 z z xim2 1011 101101 7712 277111 1021 102101 ms 77121 We will show that pA1xn A1 3 n and lAl k forms a Q basis of A and pAz1 7x A1 3 n forms a Q basis of An The fth basis consists of the Schur functions These are more complicated to de ne Sometimes they are de ned algebraically and sometimes they are de ned combinatorially We will de ne them algebraically7 and the combinatorial de nition will become apparent when we prove the Schur functions form a basis Let 80 denote the sign of the permutation 0 Given a monomial x and a permutation o E Sn7 let 0z0 denote the monomial obtained when 0 acts on x by permuting variables Now let 04 be a partition of length at most ii Let aax1z2 7x be the skew symmetric polynomial aa Z 8oo 765 It is skew symmetric because 0aa 8oaa Note that out vanishes unless 04 has distinct parts So let 04 have distinct parts we can write 04 A 6 where A is a partition of length at most n and 6 is the staircase partition n 7171 7 2 7271 Then A 7 aA6 Z UUA6 detWM 019739 765 This determinant equals 0 if we set xi 7 for some i 31 j Thus it is divisible by the Vandermonde determinant a5 H 7 xj detx j 131an Therefore a5a5 E An and we may de ne the Schur function 5A a5a5 For example7 81 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid when n 2 51 712m1 2 2 52 1122m2m11 2 511 7 12m11 Tl 1 3 1 952 752 7 2 2 7 521 7 7 1M 12 7 m21 x1 x 2 2 We will show that 5Az1 xn A S n and W k forms a Q basis of A and pAz1 xn A S n forms a Q basis of An 353 Changes of Basis Involving the m In this subsection we combinatorially express e h p and 5A in terms of the m basis This will prove that e p and 5A are also bases for An Proving that h is a basis requires a bit more effort and we will do this in the next subsection For what follows remember that we previously de ned the dominance order 3 on partitions and the reverse ledieographie R order 3 Given a matrix A let rowA denote the vector of row sums of A and let colA denote the vector of column sums of A Theorem 328 Let A h h Then 6A Z MMmM nhn where MM is the number of 0 1 matriees A with rowA A and colA M Further more MM 0 unless M S X and MAN 1 Therefore e E Ak is a basis for Ak and ex1 xn A1 3 n and W k is a basis for A5 Also e1e2 are algebraically independent and generate A as a Q algebra that is A Qe1 e2 Proof Consider the matrix 1 2 3 1 2 3 82 M390C Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid A term of e ee2 is obtained by choosing A1 entries from the rst row A2 entries from the second row and so on and multiplying those entries together to get some x Converting the chosen entries to 1 and the rest of 0 we obtain a 01 matrix A with rowA A and colA a Conversely each such matrix corresponds to a term of e Thus 6A E MMmM Mhn lf MM gt 0 let A be a 01 matrix with rowA A and colA it Let A be the matrix with rowA A and the ones left justi ed Then A colA 2 colA M Moreover A is the only matrix with rowA A and colA A so MAX 1 Thus the transition matrix MN for lAl W k is upper triangular and invertible so eA E Ak is a basis for A If we are working in nitely many variables we nd that e 0 unless A1 3 n in which case M S n Thus ex1xn A1 3 n and lAl h is a basis for A2 Finally since each f E A is uniquely expressed as a linear combination of products of es the e are algebraically independent generators of A D As an example of the previous theorem we see that 51111 7714 477131 677122 12771211 247711111 5211 77131 277122 5771211 127711111 522 77122 2771211 67711111 531 771211 47711111 54 i 7711111 Note that MAM can be interpreted as follows we have h balls with A balls labeled 239 for each 239 We have boxes labeled 1 2 Them MM is the number of ways to place the balls into the boxes so that no box contains more than one ball with the same label and box 239 contains M balls Theorem 329 Let A h k Therz h ZNAMWM Mhn where NAM is the number of N matrz39ees A with rowA A and colA M Proof Consider the matrix 1 2 3 1 2 3 A term of h hh2 is obtained by choosing A1 not necessarily distinct entries from the rst row A2 not necessarily distinct entries from the second row and so on and multiplying those entries together to get some x Converting the chosen entries to positive integers 83 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid giVing the number of times the entry was chosen we obtain an N matrix A with rowA A and colA a Conversely each such matrix corresponds to a term of h Thus h Z NMmM nhn 1 Unfortunately the matrix NM is not upper triangular so we cannot at the moment prove the h form a basis Note that NAM can be interpreted as follows we have h balls with A balls labeled i for each i We have boxes labeled 1 2 Them NM is the number of ways to place the balls into the boxes so that box i contains u balls Theorem 330 Let A h h Then pA Z RAnmnv nhn where RAM is the number of ordered partitions 7T B1 BZW of the set WAN such that MZi7 lgjgk Furthermore RM 0 unless A S u and RAN miAl where A has parts of size i Therefore 10A 6 Ak is a basis for Ak and pAp1pn A1 3 n and 1A1 k is a basis for A5 Also 101102 are algebraically independent and generate A as a Q algebra Proof RAM is the coef cient of xf 941ng in p To obtain the monomial xf we choose from each factor so that H xf Let B j ij r Then B1 BZW is an ordered partition of the appropriate type If RM gt 0 then let 7139 be an appropriate ordered partition Let Bil BZS be the distinct blocks of 7139 containing at least one of 12 r Then 1 u 2 Mil his 2 A1Aandu2 A If u A then B contains a single element The elements in B1 Bm1 can be any permutation of 1m1 the elements in Bml1Bmm2 can be any permutation of m1 1 m1 7712 and so on So RM Since RAM is upper triangular pA E Ak is a basis for Ak and pAp1pn A1 3 n and 1A1 k is a basis for A5 As before this shows 101102 are algebraically independent and generate A as a Q algebra D Theorem 331 Let A h h Then 8A Z KAMmM nhn where KM is the number of semi standard Young tableaup of shape A and type u Further more KAM 0 unless A 2 u and KM 1 Therefore 5Az1 xn A1 3 n and 1A1 k is a basis for A5 The proof of this theorem requires results from the next subsection 84 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid 354 Identities and an Involution The goal of this subsection is to develop several classes of identities relating the various bases We begin with the three generating functions Et Z M 1 m 720 11 Ht Z hTt H 1 mrl 720 11 Pt pr l 721 11 1 7 H M ErlR a 7 A H l 2 3 H log Ht gsum A C E l C H Ms H a 2 s Ar bladed A 3 a 7 D1 A C A or V We can use these generating functions to write down formulas relating 6 I17 and p The only formula we need relates er and hr since HtE7t 1 we nd that V L Z 1eh 0 70 From the above formula it looks like there is some sort of symmetry between 6A and h and indeed there is Since the e are algebraically independent we can de ne an algebra endomorphism w A a A by we hT Applying w to the above equation gives V L V L Z 1Th7whni7 0 1nirwh7hni77 70 70 and it must be that wh 6 Thus LUZ 1 and w is an involution of A The de nition of in has many consequences First since u is an isomorphism of An and sends e to h it follows that h A1 3 71 forms a Q basis of An completing the assertion that we have de ned ve bases of An Next we can compute the action of w on each of our bases 85 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Theorem 332 For any partition A let 8A 71l l l Then we h wh 6A MFA EAPA ws sV wmA fA where the f are the forgotten symmetric functions Proof The equalities for we and wh follow from the above discussion ofw The equality for wm is simply the de nition of the forgotten symmetric functions they do not have a particularly simple description As for 10A note that wHt Et7 so wPt P7t It follows that p 71 110 and thus wp eApA The result for s will follow directly from the Jacobi Trudi identity7 which will be proved in the next subsection D At the moment7 it is not clear why u is so useful basically7 given some identity involving one or more of the bases7 we can apply in to obtain a dual identity This will change in the next subsection when we prove an important property of w 355 Schur Functions We need to nish off the proof of several theorems that were stated involving Schur functions First7 we prove that the algebraic and combinatorial de nitions of Schur functions are the same We need a quick lemma rst Proposition 333 Let Oz andE be compositions ofn that are rearrangements of one another Then KAD KAE Proof lt suf ces to prove this when a 041042 7042717a217042704227 Let TM be the set of all SSYT of shape A and type a Let Tm be the set of all SSYT of shape A and type 6 Let T 6 TM Consider the parts of T equal to 2 or 2 1 If a column of T contains no such parts7 or one part 2 and one part 2 17 ignore the column The other columns contain one part 2 or one part 2 1 If a row has r 27s followed by 5 2 17s7 convert to 5 27s and r 2 17s The result is an element of Tm and this is a bijection Theorem 334 Let A F h Then s Z KMmM7 nbn where KM is the number of semi standard Young tableaum of shape A and type 12 Further more KM 0 unless A 2 u and KM 1 Therefore 5A1xn A1 3 n and lAl h is a basis for A2 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Proof Let 63 denote the elementary symmetric function in the variables 1 7j717j17 an Let M M1 Ml be a composition and de ne the l gtlt l matrices Afar Hidwt Eltlt71gtll e igtgt We claim AM HME To prove this write 171 Em Zegkn Hlt1 xit n0 1739 Then HtE1t 1 7 jt7 extracting the coef cient of 1 on each side gives l Z hMrHllt71gtlTkelek 95 k1 and this proves the claim Taking determinants we nd lAMl lHMl lEl where lAMl 1M Letting M 6 since ngl 1 we get up Now letting M A 6 we get a 5A lHA6l lhAHHl as The Jacobi Trudi identity proved below completes the proof D Theorem 335 Jacobi Trudi ldentities 5A dethxrijl ij n 71 Z 50 5A det5eij1ijgm m 7 503 Proof For the rst identity we will use the Gessel Viennot Lemma Let A Aoz y6 consist of all path systems where path L goes from BiW to oh45 Let the weight of a horizontal step in row j be xj Let m a 7 6 Then the weight of a path system will be HwtLH Z zklukaHhmi5iz i i 7i2k12 392kmi26i 139 Let B be the set of all non intersecting path systems Let B be the total weight of all systems in 8 Then B dethaj i 51 L Nowletozjjnij inii yioo and6j1 Then B dethjj On the other hand given a nonintersecting lattice path system L in 8 construct a reverse SSYT all the rows are weakly decreasing and all columns are strongly decreasing of shape A 87 M390C Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid such that the weight of L is ztype where if the horizontal steps in path Ll occur at heights 11 2 a2 2 2 curW then let these be the t th row of T This is a bijection Note that such reverse SSYT are in bijection with SSYT of shape A and the same type 04 041042 7 since if k is the largest entry of T7 replacing TH by k 1 7 TH gives a bijection with the Km SSYT of shape A and type E ak7ak1 7 and these are in bijection with KM by the proposition By the Gessel Viennot Lemma7 the rst identity is proved To prove the second identity7 consider the matrices H hiij03ijSN and E 1H i71093jN Both are lower triangular and7 by the identity from the previous subsection7 are inverses A fact from linear algebra tells us that any minor of H is equal to the complementary cofactor of Et that is7 the determinant ofthe submatrix of H obtained by selecting rows 2391 z39k and columns j1 7jk is equal to 71quot1quot39ik71quot397k times the determinant of the submatrix of Et obtained by selecting the complementary rows and columns Let A7 be two partitions of length at most p such that ACM have length at most q7 where p q N 1 Consider the minor of H with row indices AZ 10 7239 1 S 239 S p and column indices p it 1 S i S 10 The complementary cofactor of E has row indices p71j7A9 1gqu andcolumnindicesp71j lgqu So dethAHj19jgp UW det1Agiij5A27ijIsmsq Cancelling minus signs gives dewb7140 de mgim v proving the result D Corollary 336 w5 5N 356 The Hook Length Formula One beautiful enurnerative formula in this area is the Hook Length Formula This formula counts the number of SYT of shape A since this is also the dimension fquot of the Specht module Squot7 this computes the dimension of the irreducible representations of the symmetric group Given a shape A and a square 1 6 A7 let Hy be the hook of 1 namely 1 union the squares below 1 and the squares to the right of 1 Theorem 337 Hook Length Formula Let A be a partition ofn n f 7 HueA h 88 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid An inner corner of A is a square whose removal leaves another partition that is7 it is a square that is at the end of a row and the end of a column Proof by Greene Nijenhuz39s Wilf Consider the following algorithm 1 Pick 1 E A with probability 171 2 While 1 is not an inner corner7 pick w E Hy 1 with probability 1hv 7 1 and set 1 w 3 Label the corner 1 that you have reached 71 4 Repeat with A replaced by A 1 and n replaced by n 7 17 until all the cells of A are labeled The sequence of nodes generated by one pass through the rst three steps is called a trial We claim that each SYT tableau P of shape A is produced with probability HyEA hvnl First7 it is clear that the algorithm terminates at a SYT of shape A Now7 let 046 be the cell of P containing 71 and let pa be the probability that the rst trial ends there Suppose we knew that WW 7 1 l 1 j1 W Let P be the SYT of shape A obtained by removing the square labeled n from P Let E be the hook length of a square in P By induction7 HveA n 7 1 Note that EU by if 1 is not in row 04 or column B If 1 23976 then E hm 71 and if 1 047j then by hw 71 We have pP MP 0171 ijiv1 HHEA h U n To show the formula for 10ozB7 if a trial ends in 046 let the horizontal projection of the trial be I 239 31 04 1 2397j for some 1 on the trial 89 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid The vertical projection is de ned similarly Let pIJO 78 be the sum of the probabilities of all trials terminating at 046 with horizontal projection I and vertical projection J We claim that 1 1 1 PLJW n hm 7 1 hm 71 lEI JEJ Summing over all I C a 71 and all J C B 71 and factoring gives the formula for poz To prove the formula for pIJO 787 note that for I J 7 the probability is 1717 agreeing with the formula We prove the formula via induction on lIl Let a be the smallest element of I and let I be the smallest element of J Let I I a and let J J For a trial to have projections I and J7 it must start at cab and the next step must either be to 17 b or CL77 where a is the smallest element of I and b is the smallest element of J So 101I047 np1 1a Rpm0475 11171 1 1 1 1 1 nn1111gt hm1ltidlhi 71jdhwil id hw71jdhar1 1 1 1 H7H77ma har2gt WAN106771 11171 13961 1 H 1 61 hi 7 1 jeJ ha 7 1 EMA EMA EMA ElH 357 Orthogonality This is the nal subsection introducing the basics of symmetric functions In here7 we discover the Cauchy identities7 which lead us to de ne a scalar product a Z valued bilinear form on An in fact7 it will be an inner product7 but we will need a couple results before we can prove it is symmetric and positive de nite This scalar product gives us the nal tool to understand the transition matrices between bases and how to express elements of An in terms of a basis Theorem 338 Cauchy Identities 1 7 961104 ZX1PApA1 J gh m y 297mmth gs y 90 M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Proof D It turns out that the Cauchy identities suggest de ning a scalar product on An by lthmgt FM for all partitions A and u M3900 Algebraic Combinatorics Fall 2008 Instructor Geir Helleloid Bibliography H Martin Aigner A course in enumeration7 volume 238 of Graduate Tecets in Mathematics 2007 B Miklos Bona Combinatories ofpermutatz39ons Discrete Mathematics and its Applications Boca Raton Chapman amp HallCRC7 Boca Raton7 FL7 2004 E Bruce E Sagan The symmetric group 1991 Representations combinatorial algorithms7 and symmetric functions E Richard P Stanley Enumerative eombz39natom39es Vol 1 1997 E Richard P Stanley Enumerative eombz39natom39es Vol 2 1999 J H van Lint and R M Wilson A course in eombz39natom39es 2001 SE Herbert S Wilf generatingfunetionology 2006 available online

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.