18 312 Algebraic Combinatorics Lionel Levine Lecture 15 Lecture date April 15 2011 1 Notes by Jacob Bower The Braid Arrangement In the last lecture we were introduced to the characteristic polynomial A q of the hyperplane arrangement A H1 Hn which was defined as X A q Flq ni 1 Hi X 1 q dimX X L A We were then introduced to the Braid arrangement which we redefine here Definition 1 The Braid arrangement Bl is defined as Bl Hij 1 i j l Where Hij v Flq vi vj We start our study of the Braid arrangment by studying the intersection poset defined last lecture of Bl We find that L Bl l lattice of partitions of l With minimum element Hij v Flq v1 v2 vl Next we wish to study the characteristic polynomial of Bl To begin we can choose v1 in q ways We can then choose v2 in q 1 ways because it must be distinct from v1 Similarly we can choose v3 in q 2 ways because it must be distinct from v1 and v2 Continuing this line of reasoning we find Bl q q q 1 q 2 q l 1 15 1 You may recall from our study of Stirling numbers that that this is the same equation appeared during our study signed stirling numbers of the first kind Given the signed stirling numbers of the first kind s l k we have l X Bl q s l k q k k 1 It is interesting that signed Stirling numbers of the first kind appear here because we recall that it is signed Stirling numbers of the first kind that count partitions and we have already seen a close connection between Bl and partitions It turns out that they key to the relation here is Stirling reciprocity which we have already seen in class but for which we can now present a different proof To begin we recall our definition of Stirling numbers of the second kind S k j S k j partitions of k into j nonempty parts k j If we consider some fixed l where k we can then write S k j l j For signed Stirling numbers of the first kind we have seen l X X s l k q k Bl q k 1 X 1 q dimX X L Bn Which means s l k X X 1 X L Bn dimX k X 0 l k We are now prepared to prove Stirling reciporcity Theorem 2 If we have signed Stirling numbers of the first kind s l k and Stirling numbers of the second kind S k j then l X s l k S k j jl k j 15 2 0 if j 6 l 1 if j l This concludes our discussion of the Braid arrangement Proof Using the definitions of s l k and S k j we have seen above we have l X k j s l k S k j l X X 0 l j k j l k X X 0 l j X 0 l j jl 0 if j 6 l 1 if j l 2 2 Counting Connected components in Rl We now wish to take our study of hyperplanes to the real numbers Suppose we have the hyperplane A H1 Hn defined over Z and we let A connected components of Rl ni 1 Hi We will study how A is related to the characteristic polynomial of the hyperplane A We will see A A 1 which can be proved by showing the sides satisfy the same recurrence Before we complete this proof we must introduce a few definitions and lemmas that will be useful Definition 3 The deletion of A which we call A0 is A0 H1 Hn 1 That is it is the set of n 1 hyperplanes in Rl Definition 4 The restriction of A which we call A00 is A00 H1 Hn Hn 1 Hn That is it is a set of n 1 hyperplanes in Rl 1 15 3 Lemma 5 Given a hyperplane A with deletion A0 and restriction A00 we have A q A0 q A00 q Proof To prove this lemma we look at sets created by our hyperplanes We have n 1 l n Flq n 1 i 1 Hi Fq i 1 Hi t Hn i 1 Hi Hn Examining the cardinalities of each part here we find A0 q A q A00 q This is equivalent to the statement in our lemma 2 We may be interested why there is no q in our recurrence This is because q enters the equation only through the base case For the base case of an empty arrangement l in Flq we have l Flq q l Next we examine A Lemma 6 Given a hyperplane A with deletion A0 and restriction A00 we have A A0 A00 Proof We observe that each connected component of Hn n 1 i 1 Hi Hn partitions a connected component of Rl n 1 H into two parts This means i 1 i n 1 A components of Rl i 1 Hi n 1 components of Rl n 1 i 1 Hi components of Hn i 1 Hi Hn A0 A00 This completes our proof 2 We are now prepared to present our relation between A q and A Theorem 7 If we have A H1 Hn defined over Z and A as defined above then A A 1 15 4 Proof To begin our proof we define A 1 dimA A We will seek to prove that A equals A q by showing that they satisfy the same recurrence with the same base case We have already seen the recurrence satisfied by A q in Lemma 5 so all we need to study is A From Lemma 6 we have A 1 dimA A 1 dimA A0 A00 Because dimA0 dimA and dimA00 dimA 1 we can write this as 0 00 A 1 dimA A0 1 dimA A00 A0 A00 Comparing this to the results of Lemma 5 it is thus clear that A and A q satisfy the same recurrence equation so to prove they are equal we just need to show they have the same base case For the base case we consider the empty arrangement l For we have l 1 l 1 We have seen l q q l so considering q 1 we have l 1 1 l We then conclude that because A and A q satisfy the same recurrence equation with the same base case that A A q Considering absolute values we then have A A A q This completes our proof 2 3 Graph Theory We now move on to a study of graph theory We begin with a few definitions Definition 8 A graph G is defined as a set V of verices and a set E of edges where E V V We often represent G by drawing the set V as a set of dots and drawing a line between two elements if there is a …