×

Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

Create a StudySoup account

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

or

By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

by: Edgar Jacobi

16

0

125

Special Topics Linear Regression MATH 796

Marketplace > Kansas > Mathematics (M) > MATH 796 > Special Topics Linear Regression
Edgar Jacobi
KU
GPA 3.6

Staff

Almost Ready

These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
125
WORDS
KARMA
25 ?

Popular in Mathematics (M)

This 125 page Class Notes was uploaded by Edgar Jacobi on Monday September 7, 2015. The Class Notes belongs to MATH 796 at Kansas taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/182386/math-796-kansas in Mathematics (M) at Kansas.

×

Reviews for Special Topics Linear Regression

×

×

What is Karma?

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

Date Created: 09/07/15
Wednesday 326 Oriented Matroids Last time Let A H1l r r Hn be a hyperplane arrangement in Rail Let 1 r r r Zn be af ne linear forms such that H E 6 Rd l 0 for all ii For c 01 Won 6 70 let gt 0 if c F EERdl zi5lt0 if c 7 430 if 570 If F a 0 then it is called a face of A and c CF is the corresponding covectori y A faces of A LQAQA yQA U 0 big face lattice of A ordered byFSF ifFQF Consider the linear forms 139 that were used in representing each face by a covectorr Specifying i is equivalent to specifying a normal vector 17139 to the hyperplane H with i 17139 L As we know the vectors 17 represent a matroid whose lattice of ats is precisely LAl Scaling 17139 equivalently 1 by a nonzero constant A E R has no effect on the matroid represented by the ails but what does it do to the covectors If A gt 0 then nothing happens but if A lt 0 then we have to switch and 7 signs in the ith position of every covectorr So in order to gure out the covectors we need not just the normal vectors 17139 but an orientation for each one Example Lets go back to the two arrangements considered at the start Their regions are labeled by the following covectors Now you should object that the oriented normal vectors are the same in each case Yes but this couldn7t happen if the arrangements were central because two vector subspaces of the same space cannot possibly be parallel In fact if A is a central arrangement then the oriented normals determine yA uniquelyl Proposition The covectors of A are preserved under the operation of negation changing all 7s to 77s and vice versa if and only if A is central In fact the maximal covectors that can be negated are exactly those that correspond to bounded regionsl Example 1 Consider the central arrangement A whose hyperplanes are the zero sets of the linear forms 11y 217y 3172 1yzl The corresponding normal vectors are V 1711 1 l 174 where 171 1710 172 110 173 101 174 0171 The projectivization projA looks like this 7 7 77 Each region F that borders the equator has a polar opposite 7F such that C7F 70Fl The regions with covectors 7 7 7 and 77 do not border the equator ie they are bounded in proj Since they do not border the equator neither do their opposites in A so those opposites do not occur in MMM 1n the gure of Example 1 consider the point p 2 3 4 That three lines intersect at 17 means that there is a linear dependence among the corresponding normal vectors 172 i 173 174 07 or on the level of linear forms 1 127131401 Of course knowing which subsets of V are linearly dependent is equivalent to knowing the matroid M represented by Vi lndeed 172173174 is a circuit of 1 However 1 tells us more than that there exists no 139 E R3 such that 21 gt 0 31 lt 0 and 41 gt 0 That is A has no covector of the form 7 for any 96 E 7 We say that 07 is the corresponding oriented Circuiti For c E 70 write c7z39 l Q7 c77z39 l c177 De nition Let n be a positive integer A Circuit system for an oriented matroid is a collection 5 of ntuples c E 70 satisfying the following properties 1 000 ltgi 2 If c E if then 7c E if 3 If cc E if and c f c then it is not the case that both 0 C c and c C CL 4 If cc E if and c f c and there is some i with Ci and c 7 then there exists d E 9 with di0 and for allja i d CCUC F andd Cc UcLi Again the idea is to record not just the linearly dependent subsets of a set 1 i i i Zn of linear forms but also the sign patterns of the corresponding linear dependences or syzygieslli Condition 1 says that the empty set is linearly independent Condition 2 says that multiplying any syzygy by 71 gives a syzygyi Condition 3 as in the de nition of the circuit system of an unoriented matroid must hold if we want circuits to record syzygies with minimal supporti Condition 4 is the oriented version of circuit exchanger Suppose that we have two syzygies n n 7ij 2ij 07 j1 j1 with 71 gt 0 and 75 lt 0 for some ii Multiplying by positive scalars if necessary hence not changing the sign patterns we may assume that 71 77 Then i6ij 0 j1 where Sj 7139 7 In particular 6139 0 and Sj is positive respi negative if and only if at least one of 717 is positive respi negative 0 The set 0 Uc la 6 9 forms a circuit system for an ordinary matroidi 0 Just as every graph gives rise to a matroid any loopless directed graph gives rise to an oriented matroid homework probleml As in the unoriented setting the circuits of an oriented matroid represent minimal obstructions to being a covectori That is for every real hyperplane arrangement A we can construct a circuit system if for an oriented matroid such that if k is a covector of A and c is a circuit then it is not the case that 16 2 0 and K 2 cm More generally we can construct an oriented matroid from any real pseudosphere arrangement ie a col lection of homotopy d 7 lspheres embedded in R such that the intersection of the closures of the spheres in any subcollection is connected or empty Here is an example of a pseudocircle arrangement in R2 394 ln fact7 the Topological Representation Theorem of Folkman and Lawrence 1978 says that every oriented matroid can be realized by such a pseudosphere arrangementi However7 there exist lots of oriented matroids that cannot be realized as hyperplane arrangements A Example Pappus7 Theorem from Euclidean geometry says the following Let a 25 a 12 c be distinct points in R2 such that a 25 and a 12 c are collineari Then the three points I W n m 7 yiac ac 2Wn are collineari o If we perturb the green line a little bit so that it meets z and y but not 2 we obtain a pseudoline arrangement whose oriented matroid M cannot be realized by means of a line arrangementi o Pappus7 Theorem can be proven using analytic geometry The equations that say that 17y72 are collinear work over any eld Therefore7 unorienting M produces a matroid that is not representable over any eld Monday 21 1 Graphic Matroids De nition 1 Let G be a nite graph With vertices V and edges E For each subset A C E the corresponding induced subgraph of G is the graph GM with vertices V and edges A The graphic matroid or complete connectivity matroid MG on E is de ned by the closure operator 1 A e 95y E E l A contains a path from x to y e 95y E E l x y belong to the same component of CH The associated rank function is rA minlAl A Q A W A Such a subset A is called a spanning forest of A or of GM Theorem 1 Let A Q A Then any two of the following conditions imply the third and characterize spanning forests of A 1 TUV NA 2 A is acyclic 3 lA l lVl E c where c is the number of connected components of A The ats of MG correspond to the subgraphs Whose components are all induced subgraphs of G For Q V the induced subgraph GW is the graph With vertices W and edges my E E l x y E Example 1 If G is a forest a graph With no cycles then no two vertices are joined by more than one path Therefore every edge set is a at and MG is a Boolean algebra Example 2 If G is a cycle of length n then every edge set of size lt n E 1 is a at but the closure of a set of size n E 1 is the entire edge set Therefore MG E Un1n Example 3 If G Kn the complete graph on n vertices then a at of MG is the same thing as an equivalence relation on Therefore is naturally isomorphic to the partition lattice 1 17 Equivalent De nitions of Matroids In addition to rank functions lattices of ats and closure operators there are many other equivalent ways to de ne a matroid on a nite ground set E In the fundamental example of a linear matroid M some of these de nitions correspond to linearalgebraic notions such as linear independence and bases De nition 2 A matroid independence system J is a family of subsets of E such that 2a 0E 2b ifIE andIQ1thenIE and 2c if I J E J and 1 lt lJl then there exists as E JI such that Ugo E Note A family of subsets satisfying 2a and 2b is called a simplicial complex on E If E is a nite subset of a vector space then the linearly independent subsets of E form a matroid indepen dence system Conditions 2a and 2b are clear For condition 2c the span of J has greater dimension than that of I so there must be some as E J outside the span of I and then I U x is linearly independent A matroid independence system records the same combinatorial structure on E as a matroid rank function Proposition 2 Let E be a nite set 1 fr is a mat roid Tank function on E then ACE l TAlAl is an independence system 2 If g is an independence system on E then 7 A max I Al 1 E Q is a mat roid Tank function 3 These const ructions a re mutual inue39rses If M MG is a graphic matroid the associated independence system is the family of acyclic edge sets in C To see this notice that if A is a set of edges and e E A then 7 A e lt 7 A if and only if deleting e breaks a component of GM into two smaller components so that in fact 7 A e 7 A E 1 This is equivalent to the condition that e belongs to no cycle in A Therefore if A is acyclic then deleting its edges one by one gets you down to ll and decrements the rank each time so 7 A On the other hand if A contains a cycle then deleting any of its edges won t change the rank so 7 A lt Here s What the donation condition 2c means in the graphic setting Suppose that lVl n and let CH denote the number of components of a graph H If I J are acyclic edge sets With 1 lt lJl then CGlI 71 W gt CGlJ 71 lJl and there must be some edge e E J Whose endpoints belong to different components of 0 that is I U e is acyclic The maximal independent sets are called bases of the matroidi De nition 3 A matroid basis system Q on E is a family of subsets of E such that for all B B E Ba lBl WM and 3b for all e E B B there exists e E B B such that B e U e E g The condition 3b can be replaced With 3c for all e E B 3 there exists e E B B such that B e U e E although this is not obvious proof for homework Indeed if S is a nite set of vectors spanning a vector space V then the subsets of S that are bases for V all have the same cardinality namely dim V and satisfy the basis exchange condition 3b If G is a connected graph then the bases of MG are its spanning trees Here s the interpretation of 3b If e E B B then B 5 has two connected components Since B is connected there must be some edge 5 With one endpoint in each of those components and then B e U 5 is a spanning tree As for 3c if e E B B then B U 5 must contain a unique cycle C formed by 5 together with the unique path in B between the endpoints of e Deleting any edge 5 E C 5 Will produce a spanning tree Wednesday 13008 Modular Lattices De nition A lattice L is modular if for every x y z E L with x S 2 l xVyzxVyzl Note For all lattices if x S 2 then x y 2 S x y Some basic facts and examples 1 Every sublattice of a modular lattice is modular Also if L is distributive and x S 2 E L then xVyz aczyz xVyz so L is modular 2 L is modular if and only if Lquot is modular Unlike the corresponding statement for distributivity this is completely trivial because the de nition of modularity is invariant under dualization 3 N5 is not modular With the labeling below we have a S b but aVcbaO a aVcblb b 4 M5 E H3 is modular However H4 is not modular exercise Modular lattices tend to come up in algebraic settings 0 Subspaces of a vector space 0 Subgroups of a group 0 Rsubmodules of an Rmodule Elgl if X Y Z are subspaces of a vector space V with X Q Z then the modularity condition says that XY ZXY Z Proposition 1 Let L be a lattice TFAE l L is modular 2 For allxyz E L ifxE y22 then x xVy2 2 For allxyzE L ifxE yyz then x aczy 3 For all y 2 E L there is an isomorphism of lattices Mad A ydV2 given byai HlVy b2lt7 b Proof 1 gt 2 is easy if we take the de nition of modularity and assume in addition that ac 2 y 2 then the equation becomes ac ac y 2 For 2 gt 1 suppose that 2 holds Let X Y Z E L with X 3 Z Note that YAZgXVYZ ZVZZ so applying 2 with y Y 2 Z ac X Y Z gives XVYZ XVYZY Z XvYMZ as desired 2 ltgt 2 because modularity is a selfdual conditionl Finally 3 is equivalent to 2 and 2 togetherl D Theorem 2 Let L be a lattice 1 L is modular and only it contains no sublattice isomorphic to N5 2 L is distributive and only if it contains no sublattice isomorphic to N5 or M5 Proof Both gt directions are easy because N5 is not modular and M5 is not distributivel Suppose that ac y 2 is a triple for which modularity failsl One can check that xVy xVy z is a sublattice details left to the reader Suppose that L is not distributivel If it isn t modular then it contains an N5 so there s nothing to prove If it is modular then choose ac y 2 such that acyzgt acyac2l You can then show that 1 this inequality is invariant under permuting ac y z 2 95A y Vz 3 A2 and the two other lattice elements obtained by permuting ac y 2 form a cochain an 3 the join respl meet of any of two of those three guys is equal Hence we have constructed a sublattice of L isomorphic to M5 D Semimodular Lattices De nition A lattice L is upper semimodular if for all z y E L 2 xAylty 9 sz Here s the idea Consider the interval as y x y C L xVy xy H L is semimodular then the interval has the property that if the southeast relation is a cover then so is the northwest relation L is lower semimodular if the converse of 2 holds for all z y E L Lemma 3 UL is modular then it is upper and lower semimodular Proof If xy lt y then the sublattice acy y has only two elements H L is modular then by condition 3 of Proposition 1 we have x y y 9595 y so 95 lt x y Hence L is upper semimodular A similar argument proves that L is lower smimodular In fact upper and lower semimodularity together imply modularity To make this more explicit we will show that each of these three conditions on a lattice L implies that it is ranked and moreover for all x y E L the rank function r satis es rx y rx y S rx ry if L is upper semimodular rx y rx y 2 rx ry if L is lower semimodular rx y rx y rx ry if L is modular Friday 411 Until further notice G is still a nite group and all representations are nitedimensional over C New Characters from Old In order to investigate characters we need to know how standard vector space or in fact Gmodule functors such as EB and 8 a ect the corresponding characters Throughout let p V p V be representations of G with V O V ll 1 Direct sum To construct a basis for V EB V we can take the union of a basis for V and a bais for V Equivalently we can Write the vectors in V EB V as column block vectors Vex2H3 lvEV Mew Accordingly de ne p EB p V EB V by 7 90739 0 pep gtlthgt fl 0 W t From this it is clear that 1 ngph Xph Xphl 2 Duality Recall that the dual space V of V consists of all lFlinear transformations lt1 V A F Given a representation p V there is a natural action of G on V de ned by MW ltWflv for h E G lt1 E Vquot v E V You need to de ne it this way in order for hi to be a homomorphism 7 try it This is called the dual representation or contragredient representation pf Proposition For every 1 E G 2 Xpdh XpU bl Proof Choose a basis 11 t i i 27 of V consisting of eigenvectors of 1 since we are working over C say hvl Alil In this basis ph diagl ie the diagonal matrix Whose entries are the Al and in the dual basis ph diag1i On the other hand some power of ph is the identity matrix so each 1 must be a root of unity so its inverse is just its complex conjugate 3 Tensor product Recall that if 21 i i 27 21 i v are bases for V V respectively then V V can be de ned as the vector space With basis vl vl1 i n1 j mi In particular dim V V dim Vdim V Accordingly de ne a representation 17 17 V V by p p hv 7 MW 7 v MW or more concisely h v v hv v v 017 extended bilinearly to all of V V In terms of matrices 17 p h is represented by the block matrix 11113 11113 an 11213 11223 1an M13 anQB am Where ph 111 le and 1701 B In particular 3 Xp ph XphXph 4 m Recall that HomGV V Homap p is the vector space of all Gequivariant maps 1 A 1quot Meanwhile Hode W can be made into a Gmodule by 4 h gtgtltvgt hlt gtlth4vgtgt p lthgt ltplth1gtltvgtgt for h E G lt1 E HOde W 1 E V That is 1 sends lt1 to the map 1 lt1 Which acts on V as above You can then verify that this is a genuine group action In general When G acts on a vector space V the subspace of Ginva m39ants is de ned as VGvEVlhvthEGi In our current setup a map lt1 is Gequivariant if and only if h lt1 lt1 for all h E G proof left to the reader That is 5 HomGV W Hode WGi Moreover Hode W E V W as vector spaces so 6 XHompp h W M h The Inner Product Recall that a Class function is a function X G A C that is constant on conjugacy classes of G De ne an inner product on the vector space CHG of class functions by 1 7 ltX gta E Z XMW M l l heG Proposition 1 With this setup 1 dlmc VG E Z Xph ltXtriv XpgtG heG Proof De ne a linear map 7r V A V by 1 7r 7 p h 101 In fact 7rv E VG for all 1 E V and if v E VG then 7rv 1 That is 7r is a projection from V A Va and can be represented by the block matrix I 0 0 l Where the rst and second column blocks resp roW blocks correspond to Va and VGL respectively is now evident that dimc V tr 7r giving the rst equality The second equality follows because Va is just the direct sum of all copies of the trivial representation occurring as Ginvariant subspaces of V D Example 1 Suppose that p is a permutation representation Then Va is the space of functions that are constant on the orbits Therefore the formula becomes number of orbits 1 E 2 number of xed points of h heG Which is Burnside s Lemma Proposition 2 ltXp XpgtG dimc Homgpp Proof ltXp XpgtG E ZWXph heG 1 E Z XHompph by 6 l l heG dimc Homp pG by Proposition 1 dimc Homap p by D Monday 310 Projectivization and Coning Let K be a eld Denote points of K by 55 x1 i i Projective space llm lK is by de nition the set of lines through the origin in K If K R we can regard Pn llR as the unit sphere S7 1 with opposite points identi ed in particular it is an n 7 1dimensional manifold Algebraically write 55 N j if a and j are nonzero scalar multiples of each other Then N is an equivalence relation an P 1KltKn6gt Linear hyperplanes in K correspond to af ne hyperplanes in Pn lK Thus given a central arrangement A Kquot we can construct its projectivization projA C Pm lK Projectivization supplies a nice way to draw central 3dimensional real arrangements Let S be the unit sphere so that H O S is a great circle for every H E A Regard H0 0 S as the equator and project the northern hemisphere into your piece of paper proj 3 proj Brg projessBr3 Of course a diagram of projA only shows the upper half77 of A We can recover A from projA by re ecting the interior of the disc to the exterior77 Stanley For example when A 3 In particular rproj TAi De nition Let A C Kquot not necessarily central The cone CA is the central arrangement in K7 1 de ned as follows 0 Geometrically Make a copy of A in Kn1 choose a point p not in any hyperplane of A and replace each H E A With the af ne span H ofp and H Which Will be a hyperplane in Kn1l Then toss in one more hyperplane containing p and in general position With respect to every H o Algebraically For H 9 l Li39 111 E A With L a homogeneous linear form on K and al E K construct a hyperplane H xlyu cmy l Li39 aly C K7 1 in CA Then toss in the hyperplane y 0 For example if A consists of the points x 0 x 73 and x 5 in R1 then CA consists of the lines 95 y 9573y x5yandy0ian2l Proposition 1 XCAUs k E 1XAk We ll prove this next time In particular Zaslavsky s formula for the number of regions implies that rcA 2rAl More on Regions and the Characteristic Polynomial Let A C K be a hyperplane arrangement We have seen that if K R then rA of regions ofA 71dimAXAEl bA of rel bounded regions 71mquotkAXA1l Zaslavsky s theorems and that if K qu then 1 FEWll 11 a fact rst noticed implicitly by Crapo and Rota and explicitly by Athanasiadis What if A C Cquot is a complex hyperplane arrangement Since the hyperplanes of A have codimension 2 as real vector subspaces the complement X Cquot A is connected but not simply connected Theorem 2 Brieskorn 1971 The homology groups H1X Z are free abelian and the Poincare polynomial of X is the characteristic polynomial backwards n Zrankz HzXZql qleLM l Il 10 Orlik and Solomon 1980 strengthened Brieskorn s result by giving a presentation of the cohomology ring HX Z in terms of LA thereby proving that the cohomology is a combinatorial invariant of A Brieskorn s theorem says only that the additive structure of H X Z is a combinatorial invariantl The homotopy type of X is not a combinatorial invariant according to Reiner by a result of Rybnikov Graphic Arrangements De nition 1 Let G be a simple graph on vertex set The graphic arrangement AG C K consists of the hyperplanes x1 95 Where ij is an edge 0 The arrangement AG is central but not essential so LAa is a geometric lattice The corresponding matroid is naturally isomorphic to the graphic matroid of G In particular 7 AG TG 2 0 equals the number of acyclic orientations of G For instance if G Kn then A BT71 Which we have seen has n regions On the other hand the acyclic orientations of Kn are in bijection With total orderings of its vertices Moreover the chromatic polynomial of G equals the characteristic polynomial of LAai This last fact has a concrete combinatorial interpretation Regard a point 951 i i i 957 E F as a qcoloring of G that assigns color 951 to vertex 239 Then the proper qcolorings are precisely the points of F2 AG The number of such colorings is xG q the chromatic polynomial of G evaluated at 11 on the other hand by 1 it is also the characteristic polynomial XAGqi Since xG q XAGq for in nitely many 1 namely all integer prime powers the po ynomials must be equa For some graphs such as complete graphs and trees the chromatic polynomial factors into linear terms For others it doesn t Example 1 Let G C4 a cycle With four vertices and four edges and let A Aa Then LA is the lattice of ats of the matroid U34 iiei LF 4 W 3 With 7 F minlFl 3 Since the Mobius function of an element of L depends only on its rank it is easy to check that XLk k3 74k 6k 7 3 k 71x18 73k 13 Multiplying by kdim AL mnk lL k4 3 gives the characteristic polynomial of AL Which is the chromatic polynomial of C4 XC4k Mk 71k2 7 3k k So the question arises For Which graphs does the chromatic polynomial factor into linear terms More generally for Which arrangements A does the characteristic polynomial XAUs factor Wednesday 49 Irreducibility Indecomposability and Maschke s Theorem Today G is a nite group and all representations are nitedimensional De nition 1 Let p V be a representation of G A vector subspace W C V is Ginvariant if pgW C W equivalently if W is a Gsubmodule of V V is irreducible or simple or colloquially an irrep if it has no proper Ginvariant subspace For instance any 1dimensional representation is clearly irreducible It would be nice if every Ginvariant subspace W had a Ginvariant complement ie another Ginvariant subspace WL such that W O WL 0 and W WL V However funny things can happen in positive characteristic Example 1 Let e1e2 be the standard basis for F2 Recall that the de ning representation of 32 12 21 is given by 1 0 0 1 pdef12 0 I Pdeflt21 I 0 and that Pdef951 52 Peru9X51 52 Pdef951 52 Psign951 52 Therefore as we saw last time the change of basis map 1 71 E l H1 3f is a Gequivariant isomorphism between pdef and pmv EB psign 7 unless F has characteristic 2 In that case W spane1 e2 is certainly Ginvariant but it has no Ginvariant complement D ohl row row lolH De nition 2 The representation V is decomposable if there are Ginvariant subspaces W WL with W 0 WL 0 and W WL V Otherwise V is indecomposable Clearly every representation can be written as the direct sum of indecomposables Moreover irreducible implies indecomposable But the converse is not true in general as Example 1 illustrates Fortunately this kind of pathology does not happen in characteristic 0 Indeed something stronger is true Theorem 1 Maschke s Theorem LetG be a nite group and letlF be a eld whose characteristic does not divide Then every representation p G A GLV is completely reducible that is every Ginvariant subspace has an invariant complement Proof If p is an irreducible representation then there is nothing to prove Otherwise let W be a Ginvariant subspace and et 7r V A W be any projection ie a surjective linear transformation with nothing assumed about its behavior with respect to p For 1 E V de ne 1 Cv gg fg lv Then Cv E W because W is Ginvariant Moreover for h E G we have mm 2 WW gEG Zlthggtwltlthgr1hvgt gEG 1 1 Z g7rg 1v h7rGv gEG that is a is Gequivariant Now de ne WL ker a Certainly V E W EB WL as vector spaces and by Gequivariance if v E WL and g E G then Cgv g7rgv 0 ie 92 E WL That is WL is Ginvariant D Maschke s Theorem implies that a representation p is determined up to isomorphism by the multiplicity of each irreducible representation in p By the way implicit in the proof is the following useful act Proposition 2 Any Gequivaritmt map has a Gequivaritmt kernel and Gequivaritmt image De nition 3 Let p V be a representation of C over F lts character is the function Xp G A F given by XM tr 99 Example 2 Some simple facts and some characters we ve seen before 1 A onedimensional representation is its own character 2 For any representation p we have Xp1 dim p because p1 is the n X 71 identity matrix 3 The de ning representation pdef of 37 has character Xdef039 number of xed points of a 4 The regular representation preg has character 0 if a la a xreg 0 otherwise Example 3 Consider the twodimensional representation p of the dihedral group D7 r s l r 32 0 srs r l y rotations and re ections S 7 1 0 T 7 cost9 sint9 p 7 0 71 p 7 Esint9 cost9 lts character is Xprl 2cos23919 0 S 239 lt n Xpsrl 0 0 S j lt On the other hand if p is the ndimensional permutation representation on the vertices then its character is n if g 1 0 if g is a nontrivial rotation Xpg 1 if n is odd and g is a re ection 0 if n is even and g is a re ection through two edges 2 if n is even and g is a re ection through two vertices One fixed point No fixed points Two fixed points Proposition 3 Characters are class functions that is they are constant on conjugacy classes of G More over ifp p t en Xp Xp Proof Recall from linear algebra that trABA 1 trB in generals Therefore tr 019175 tr 9hp9ph 1 tr MMMQWWYI 179 For the second assertion let lt1 p A p be an isomorphism iiei lt1 179 p g lt1 for all g E G treating lt1 as a matrix in this notation Since lt1 is invertible we have therefore lt1 179 lt1 p ow take tracesi What we d really like is the converse of this second assertions In fact much much more is true From now on we consider only representations over C Theorem 4 Let G be any nite group X X en a is a represen a ion is e ermine up 0 isomorp ism y i s c arac er 1 p pth pr Tht39 tt39 39dt 39d t39 h39 b39t h t e c arac ers o irre uci e represen a ions orm a asis or e uec or space 0 a c ass 2 Th h t 39 d 39bl tt39 b 39 th t CZG ll l functions of G Moreover this basis is orthonormal with respect to the natural Hermitian inner product de ned by ltf m 2mm gEG The bar denotes complex conjugate 3 As a consequence the number of di erent irreducible representations of G equals the number of conjugacy classes e regu ar represen a ion re sa is es 4 Th l t t39 p g t39 5 ea dim p meg 7 EB p irreps 17 so in particular 0 Z dimp irreps 17 Example 4 The group G 33 has three conjugacy classes determined by cycle shapes C1 16 C2 12 13 23 C3 1213 132 We ll notate a character X by the bracketed triple XC1 XC2 XC3li We know two irreducible 1dimensional characters of 33 namely the trivial character va 1 1 1 and the sign character Xsign 1 71 1 Note that ltva Xtriv 1 ltXsign Xsigngt 1 ltXtriv Xsigngt 0 Consider the de ning representation lts character is Xdef 3 1 0 and 1 3 7 ltXtriv Xdaf 6 Zlcjl XtrivCj XdefCj j1 l 6113311210 1 1 3 7 ltXsign Xdaf 6 Zlcjl XtrivCj XdefCj j1 1 61137311210 0 This tells us that pdef contains one copy of the trivial representation as a summand and no copies of the sign representation If we get rid of the trivial summand the remaining twodimensional representation p has character Xp Xdef 7 va 2 0 71 Since 12 2 30 0 2 1 1 7 7 ltxp xpgt f 1 it follows that p is irreducible So up to isomorphism 33 has two distinct onedimensional representations pmv psign and one twodimensional representation p1 Note also that Xcriv Xsign 2Xp 111l1r11l 2 0 1 6 0 0 Xreg New Characters from Old In order to investigate characters we need to know how standard vector space or in fact Gmodule functors such as EB and 8 a ect the corresponding characters Throughout let p V p V be representations of G with V V ll 11 Direct sum The vectors in V EB V can be regarded as column block vectors for v E V v E V Accordingly de ne p EB p V EB V by 7 90739 0 paw gtlthgt fl 0 W 1 It is clear that 2 Xpeap Xp Xx Next time Tensor product dual and Hom Monday 225 The Incidence Algebra Many enumerative properties of posets P can be expressed in terms of a ring called its incidence algebra De nition 1 Let P be a locally nite poset and let lntP denote the set of intervals of P The incidence algebra P is the set of functions f lntP A C l ll abbreviate x by x For convenience we set x y 0 if x i This is a Cvector space with pointwise addition subtraction and scalar multiplication It can be made into an associative algebra by the convolution product wow 2 fxaz9zy zeixv Proposition 1 Convolution is associative Proof lf9hlxy Z f9zZhzy zehg Z lt Z fwmm hm zehg wehx Z fltzwgtlt Z gltwzgthltzygtgt wepg zdwm Z fzw9hwy wepg fghxy D Proposition 2 f E P is invertible if and only fx x y 0 for all x Proof lff is invertible with inverse 9 then gx x x xgx x for all x so in particular x x y 0 OTOH if fx x y 0 then we can de ne a left inverse g inductively gx x lfx x and for x lt y we want to have 9 fxy 0 Z 9xzgtfltzygt ISISy gxyfxa 1H E fx292y xgzlty so de ne 1 995 3 m 211905 ZUV y The identity element of P is the Kronecker delta function 6 l ifxy x y 0 ifxy y The zeta function is de ned as 7 l ifoy xy70 ifxiy and the eta function is l ifzlty x n y 0 ifx y iiei n76i Principle Counting various structures in P corresponds to computation in P For example look at powers of 2 we 2 Z ammz y Z 1 zexy zdaw 2 xgzgy mm 2 Z ltltxzgtltltzwgtltltwygt Z 1 zEcyuEzy xgzgwsy 2212 xgzgwgy ltquotzyx1mxn71 magmasswelsy number of nmultichains between 95 and y Similarly nnxy x1uixn1xltx1 ltx2 lt ltxn1 lty number of nchains between 95 and y o If P is chain nite then 7 0 for 71 gtgt 0 The Mobius Function Let P be a poset We are going to de ne a function M Mp on pairs of comparable elements ofP equivalently on intervals of P called the Mobius function of P The de nition is recursive l MPII l for all x E P 2 If I i y then 130641 0 3 If I lt y then 139641 7 2 13m 1306 2 This is just the construction of Proposition 2 applied to f That is M 1 the Mobius function is the unique function in P satisfying the equations Z 1306 Z 596 y z szSy Example 1 In these diagrams of the posets M5 and N5 the red numbers indicate Mp O 1 2 1 1 1 1 1 Example 2 In the diagram of the following poset P the red numbers indicate up 1 1 Example 3 Let Q7 be the Boolean algebra of rank n and let A E 7 I claim that M A El Al To see this induct on The case A 0 is clear For A gt 0 we have quot1 W M6114 7 EHW 7 Z 71klt k by induction BgA k0 W HM 7 34 2 1W1W il Al More generally if B Q A then MB A EllBAl because every interval of n is a Boolean algebra Even more generally suppose that P is a product of n chains of lengths a1 i i a That is Px x1iiixn 03 x 3 al for allz39 E ordered by x S y ill x S 31 for all 239 Then A 0 if x1 2 2 for at least one 239 MO I s 71 if x cons1sts of s ls and n E s 0 s The Boolean algebra is the special case that a 2 for every This conforms to the de nition of Mobius function that you saw in Math 724 This formula is sufficient to calculate My x for all x y E P because every interval y C P is also a product of chains Example 4 We Will calculate the Mobius function of the subspace lattice L L7 1 Notice that if X C Y C F With dirnY 7 dirnX m then X Y E Lmqi Therefore it suf ces to calculate fq 71 I MOE Let gqk n be the number of kdirnensional subspaces of F2 Clearly fq 1 2 4 1 1fn72then9q1a2i qilQ150f112 1111 3 Hn3athen9q139q2a3i711q2q1s0 fq 3 W11 7 03 V Vgrg 72pwwvmm k0 717q2q17142 11 1 Forn4 fq4quka4fqak k0 11471 q4ilqsil 11471 3 71 q71 17W7 7 It is starting to look like fememwgt in general and indeed this is the case We could prove this by induction noW but there is a slicker proof coming soon Why is the Mobius function useful o It is the inverse of Q in the incidence algebra check this o It generalizes inclusionexclusion o It behaves nicely under poset operations such as product o It has geometric and topological applications Even just the single number up tells you a lot about a bounded poset P it is analogous to the Euler characteristic of a topological space Monday 33 1 Network Flows De nition A network is a directed graph N V E with the following additional data 0 A distinguished source 3 E V and sink t E V o A capacity function c E A N A ow on N is a function f E A N that satis es the capacity constraints 1 0 S fe S ce Ve E E and the conservation constraints 2 f v fv W E V 87 where M Z fe7 fltvgt 2 re e77 an u The value of a ow f is the net ow into the sink lfl f t 7 ft f8 7 f 8 Let ST C V with S U T V 5 NT ll 3 E S and t E T The corresponding cut is ST 36E sEStES and the capacity of the cut is cST Ede eEE We proved the main result last time Theorem 1 MaxFlowMinCut Theorem Let f be a flow of maximum value and let 5T be a cut of minimum capacity Then cS T Acyclic and Partitionable Flows De nition 1 A ow f is acyclic if for every directed cycle C C D ie every set of edges 0 1112712137Hwxnilxrurnrlh there is some e E C for which fe 0 A ow f is partitizmable if there is a collection of s tpaths P1 Pm from such that for every e E E f i l e 6 Pi Here s tpath77 means path from s to t Proposition 2 o For every flow there exists an acyclic flow with the same value 0 Every acyclic flow is partitizmable Proof Suppose that some directed cycle C has positive ow on every edge Let h minfe l e E C De nefEgtbe e 7 h if e E C fe fe if e g C Then it is easy to check that fis a ow and that If we repeat this process it must eventually stop because the positive quantity EeeE fe decreases with each iteration which means that the resulting ow is acyclici This proves 1 i Given an acyclic ow f nd an s tpath P1 along which all ow is positive Decrement the ow on each edge of P1 doing this will also decrement Now repeat this for an stpath P2 etci Eventually we partition f into a collection of s tpaths of cardinality Applications of the MaxFlowMinCut Theorem Let G be a graph or directed graph and let st E VGi A family of stpaths Phi i i Pn in G is vertex disjoint if st for all ij and is edgedisjoint if N Z for all iji Every vertexdisjoint family is edgedisjoint but the converse is not true An stvertex cut is a set X E VG such that G 7 X contains no s tpathi Likewise an stedge cut is a set A Q E such that G 7 A contains no stpathi Theorem 3 Menger7s Theorem Let G be a graph or directed graph and let st E VG Then the maximum cardinality of a vertexdisjoint resp edgedisjoint family of stpaths equals the minimum cardinality of an stvertex cut resp edge cut In the former case we assume st are not adjacent Proof First of all an undirected graph can be considered as a digraph by replacing each edge my with a pair of antiparallel edges Ty So we may as well consider only the directed setting If we regard G as a network with source s and sink t in which every edge has capacity 1 then the edgeversion of Mengerls Theorem is immediate from the MaxFlowMin Cut Theorem and Proposition 2 For the vertex version we need to do a little surgery on C before applying MaxFlowMinCuti The trick is to separate each vertex 1 E VG st into an inbox 1 an an outterminal77 1 with a bottleneck between them so that only one path can pass through each vertex Speci cally de ne a digraph N by WN 87 U 1771 l I 6 WC 87th a A A EN 31 l s E U frt l at E a U Ny l1 6 190 a U 171 l1 6 VG and regard it as a network with source s and sink t and capacity function 1 if e 1 14 for some I E VG 06 00 otherw1sei Then an s tcut in N contains only nitecapacity edges hence corresponds to an s tvertex cut in G Now applying MaxFlowMinCut gives the desired result Back to Algebraic Combinatorics Here is two related minmax results on posets with the same avor as the MaxFlowMin Cut Theoremi A chain cover of a poset P is a collection of chains whose union is P The minimum size of a chain cover is called the width of Pi Theorem 4 Dilworth s Theorem Let P be a nite poset Then widthP max 3 l P has an antichain of size 3 Dilworthls Theorem can be proven using MaxFlowMin Cut but it involves a bit more work so here is a posettheoretic proof insteadi Proof The 2 direction is clear because if A is an antichain then no chain can meet A more than once so P cannot be covered by fewer than lAl chainsi For the more dif cult S direction we induct on n The result is trivial if n l or n 2 Let Y be the set of all minimal elements of P and let Z be the set of all maximal elementsi Note that Y and Z are both antichainsi First suppose that no set other than Y and Z is an antichain of maximum size Dualizing if necessary we may assume Y is maximumi Let y E Y and 2 E Z with y S 2 Then the maximum size of an antichain in P P 7 y z is lYl 7 1 so by induction it can be covered with lYl 7 l chains and tossing in the chain y 2 gives a chain cover of P of size Now suppose that A is an antichain of maximum size that contains neither Y nor Z as a subset De ne PIEPlIZaforsomeaEA P 16Plz aforsomeaEAi Then 0 P P 3e 0 otherwise A equals Z or Y o P4r U P P otherwise A is contained in some larger antichaini o P4r N P A otherwise A isn7t an antichaini So P4r and P are posets smaller than P each of which has A as a maximum antichaini By induction each has a chain cover of size So for each a E A there is a chain C C P4r and a chain C C P with a E C N C and Ca 0 l a e A is a chain cover of P of size D Monday 47 Group Representations De nition 1 Let G be a group and let V E lF be a nitedimensional vector space over a eld lF A representation of G on V is a group homomorphism p G A GLV That is for each 9 E G there is an invertible n X n matrix pg satisfying MawJUL Myh WM 6 G That7s matrix multiplication on the left side of the equation and group multiplication in G on the right The number n is called the dimension or degree of the representation 0 p speci es an action of G on V that respects its vector space structure 0 We often abuse terminology by saying that p is a representation or that V is a representation or that the pair p V is a representation 0 p is a permutation representation if pg is a permutation matrix for all g E G o p is faithful if it is injective as a group homomorphism Example 1 The regular representation Let G be a nite group With n elements and let lFG be the vector space of formal lF linear combinations of elements of G that is rGZahhlaher hEG Then there is a representation png of G on F0 called the regular representation de ned by 9 2 am Z ahgh hEG heG That is7 g permutes the standard basis vectors of lFG according to the group multiplication law Example 2 The de ning representation of G Let G 6n the symmetric group on n elements Then we can represent each permutation a E G by the permutation matrix With 17s in the positions iai for everyi E n and 07s elsewhere For instance the permutation 4716253 6 67 corresponds to the permutation matrix 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 Example 3 For any group G the trivial representation is de ned by pmvg In the n X n identity matrix Example 4 Let G ZkZ be the cyclic group of order k and let Q be a 16 root of unity not necessarily primitive Then G has a 1dimensional representation given by pz 4 Example 5 Let G act on a nite set X Then there is an associated representation on lFX the vector space With basis X given by M9 awxgt Z a1lt9 39 zeX meX For instance the action of G on itself by left multiplication gives rise in this way to the regular representation Example 6 Let G D the dihedral group of order 2n ie the group of symmetries of a regular ngon given in terms of generators and relations by ltS7 32 Tn 1 87 s T71 There are a bunch of associated faithful representations of Cl First we can regard s as a re ection and 7 as a rotation 1 0 cos 9 sin 9 MS 7 0 71 7 MT 7 7 sint9 cosg Where 9 27rni This is a faithful 2dimensional representationi Alternately we can consider the actions of G on vertices or on edges or on opposite pairs or on diameters These are all faithful ndimensional representations except for the last iif n is even then this representation is 2n dimensional and not faithfu i Example 7 The symmetric group 6 has a nontrivial 1dimensional representation the Sign represen tation given by 1 if a is even a pmgn 71 if a is odd Note that psigng det pdefg Where pdef is the de ning representation of SW In general if p is any representation then det p is a ldimensional representationi Note that For you algebraists a representation of G is the same thing as a left module over the group algebra lFGi Example 8 Let p V and p V be representations of G Where V E F V 2 WW The direct sum p69 3 G A GLV EB V is de ned by 3 EB 9v v yv yv for v E V 1 6 VA In terms of matrices 3 EB p g is a blockdiagonal matrix T M09 239 T Isomorphisms and Homomorphisms When two representations are the same More generally what is a map between representations De nition 2 Let p V and pV be representations of Cl A linear transformation 45 V A V is Gequjvariant if gab qbgi Equivalently g 459 v for all g E G v E V Or more precisely if less concisely pg P9 39 UH If you insist this is equivalent to the condition that the following diagram commutes for all g E G V gtV pawl L g V gt V 45 Abusing notation as usual we might write ab p A p In the language of modules these are just Gmodule homomorphismsi Accordingly the vector space of all Gequivariant maps V A V is denoted HomgV V This is itself a representation of Cl Example 9 One way in which G equivariant transformations occur is when an action naturally induces another action For instance consider the permutation action of G4 on the vertices of K4 which induces a 4dimensional representation pvi However this action naturally determines an action on the six edges of K4 which in turn induces a 6dimensional representation pal This is to say that there is a Gequivariant transformation p1 A pal De nition 3 Two representations p V and p V of G are isomorphic if there is a G equivariant map 45 V gt V that is a vector space isomorphismi Example 10 Let lF be a eld of characteristic 2 and let V lFQ with standard basis 6162 Let G 62 1221 The de ning representation p pdef of G on V is given by l 0 0 1 p02 0 1 7 M21 1 0 t On the other hand the representation a pmv EB psign is given on V by 1 0 1 0 012 7 0 1 021 7 0 71 i These two representations are in fact isomorphici Indeed p acts trivially on spanel 62 and acts by 71 on spanel 7 62 Since these two vectors form a basis of V one can check that 15 ll ll 71 il Our goal is to classify representations up to isomorphismi As we will see we can do this without having to worry about every coordinate of every matrix My 7 all we really need to know is the trace of My known as the Character of a representation For instance in this last example we can detect the isomorphism p E a by observing that tr p12 tr 012 2 tr p21 tr a21 0 is an isomorphism p A a Friday 222 The Chromatic Polynomial Let G E be a graph A hcolo39ring ofG is a function f V 7gt h the coloring is proper if y whenever vu E E The chromatic function of G is de ned as xG h of proper colorings of G Theorem 1 Let G be a graph with n vertices and c components Let 2G h 71quot7ChCTG 17 h0l Then 20 h xG h Proof First we show that the chromatic function satis es the recurrence 1 MG kkquot ifEZl 2 XG k 0 if G has a loop 3 XG k k 1XG5 k if e is a coloop 4 xG h xG 7 e h 7 xGe h otherwise If E 3 then every one of the h colorings of G is proper and if G has a loop then it has no proper colorings so 1 and 2 are easy Suppose e gay is not a loop Let f be a proper hcoloring of G 7 e If then we can identify as and y to obtain a proper hcoloring of Ge lf y then f is a proper hcoloring of G So 4 follows This argument applies even if e is a coloop In that case however the component H of G containing e becomes two components H and H of G 7 e whose colorings can be chosen independently of each other So the probability that in any proper coloring is lh implying A corollary by induction on lVl is that xG h is a polynomial in h and thus has the right to be called the chromatic polynomial of The graph G 7 e has n vertices and either c l or c components according as e is or is not a coloop Meanwhile Ge has n 7 1 vertices and c components By the recursive de nition of the Tutte polynomial 540 k 71quot CkCTG 1430 h if E ll 7 0 if e is a loop 7 l 7 h7l 1 ChCTGe l7 h 0 if e is a coloop 71 Chc TG 7 e l7 h 0 TGe l7 h 0 otherwise h if E ll 7 0 if e is a loop 7 h 7 1XGe h if e is a coloop xG 7 e h 7 xGe h otherwise which is exactly the recurrence satis ed by the chromatic polynomial This proves the theorem D This result raises the question of what this specialization of TM means in the case that M is a an arbitrary not necessarily graphic matroid Stay tuned Acyclic Orientations An orientation D of a graph G E is an assignment of a direction to each edge my E E either y or A directed cycle is a sequence x0 x1 1 i i 95771 of vertices such that 95195244 is a directed edge for every 239 Here the indices are taken modulo An orientation is acyclic if it has no directed cycles Let AG be the set of acyclic orientations of G and let 11G Theorem 2 Stanley 1973 For every graph G on n vertices we have 10 TG12071n71XG171 Proof The second equality is a consequence of Theorem 1 Plugging ac 2 and y 0 into the De nition of the Tutte polynomial we obtain the recurrence we need to establish in order to prove the rst equality A1 If E ll then 1G 1 A23 If e E E is a loop then 10 0 A2b If e E E is a coloop then 10 211Ge A3 If e E E is neither a loop nor a coloop then 10 1G E e 1Ge A1 holds because the number of orientations of G is 2lVl and any orientation of a forest in particular an edgelesss graph is acyclic For A23 note that if G has a loop then it cannot possibly have an acyclic orientation If G has a coloop e then e doesn t belong to any cycle of C so any acyclic orientation of Ge can be extended to an acyclic orientation of G by orienting e in either direction proving A2b The trickiest part is A3 Fix an edge e my E For each orientation D ofG let D be the orientation produced by reversing the direction of e and let A1 D e AG D e AG A2 D e AG D g AGi Clearly 10 lA1llA2li Let D be an acyclic orientation of G E e If D has a path from ac to y for short an ac ypath then it cannot have a y acpath so directing e as y but not e 335 produces an acyclic orientation of G all this is true if we reverse the roles of ac and y We get every orientation in A2 in this way On the other hand if D does not have either an ac ypath or a y xpath then we can orient e in either direction to produce an orientation in A1 Therefore 5 am 7e 3M Aal Now let D be an acyclic orientation of Ge and let D be the corresponding acyclic orientation of G E e 1 claim that D can be extended to an acyclic orientation of G by orienting e in either way Indeed if it were impossible to orient e as fy then the reason would have to be that D contained a path from y to ac but y and ac are the same vertex in D and D wouldn t be acyclic Therefore there is a bijection between AGe and matched pairs D in AG so 1 6 l195 ilAll Now combining 5 and 6 proves A3 D Some other related graphtheoretic invariants you can nd from the Tutte polynomial o The number of totally cyclic orientations ie orientations in which every edge belongs to a directed cycle HW problem The flow polynomial of G whose value at k is the number of edgelabelings f E A k 7 1 such that the sum at every vertex is 0 mo o The reliability polynomial the probability that the graph remains connected if each edge is deleted with independent probability p o The enhanced chromatic polynomial which enumerates all qcolorings by improper edges g 3 Z tryEE l frfy frVelq This is essentially Crapo s cobounda39ry polynomial and provides the same information as the Tutte polynomial And more the canonical source for all things Tutte is T Brylawski and J Oxley The Tutte polynomial and its applications Chapter 6 of Matpoid applications N White editor Cambridge Univ Press 1992 Basis Activities We know that TM ac y has nonnegative integer coefficients and that TM l l is the number of bases of M These observations suggest that we should be able to interpret the Tutte polynomial as a generating function for bases that is there should be combinatorially de ned functions i e A N such that 7 TW 962 Z avian BX BEM In fact this is the case The tricky part is that and 53 must be de ned with respect to a total order on the ground set E so they are not really invariants of B itself However another miracle occurs the righthand side of 7 does not depend on this choice of total order lndex the ground set of E as 51 e and totally order the elements of E by their subscripts De nition 1 Let B be a basis of M 0 Let c E B The fundamental cocircuit Cquot 51 B is the unique cocircuit in E B U 51 That is Cel B Ej l BelU Ej E We say that 51 is internally active with respect to B if 51 is the minimal element of Cel B 0 Let c E B The fundamental circuit Cez B is the unique circuit in B U 51 That is CelB Ej l B5jU 51 E We say that 51 is externally active with respect to B if 51 is the minimal element of Cel B 0 Finally we let 53 and denote respectively the number of externally active and internally active elements with respect to B Here s an example Let G be the graph with edges labeled as shown below and let B be the spanning tree 52 54 55 shown in red The middle gure shows Cel B and the righthand gure shows Cquot 55 B e1 e2 e4 e5 93 Then C51B 51 54 55 so 51 is externally active Ces B 52 53 55 so 53 is not externally active Therefore eB 1 Meanwhile Ceg B 52 63 so el is internally active Ce4 B 51 54 so 63 is not internally active C55 B 51 53 55 so 53 is not internally active Therefore 1 Theorem 3 Let M be a matmid on E Fix a total ordering of E and de ne 239e A N as above Then 7 holds Thus in the example above the spanning tree B would contribute the monomial my xlyl to TG x The proof which I ll omit is just a matter of bookkeeping It s a matter of showing that the generating function on the righthand side of 7 satis es the recursive de nition of the Tutte polynomial Friday 2808 Geometric Lattices and Matroids Warning If A is a set and e isn t then I am going to abuse notation by writing A U e and A e instead of A U e and A e when no confusion can arise Recall that a matroid closure operator on a nite set E is a map A gt A on subsets A Q E satisfying la AQAA 1b A g B j A g B 1c e E A e E AU f gt f E AU e the exchange condition A matroid M is then a set E the ground se 77 together with a matroid closure operatorl A closed subset of M ie a set that is its own closure is called a E of Mt The matroid is called simple if ll and all singleton sets are closed Theorem 1 1 Let M be a simple matroid with nite ground set E Let LM be the poset of flats o M ordered by inclusion Then LM is a geometric lattice under the operations AB A B AVB A U B 2 Let L be a geometric lattice and let E be its set of atoms Then the function A e E E l e S V A is a matroid closure operator on Proof For assertion 1 we start by showing that LM is a lattice The intersection of ats is a at an easy exercise so the operation A O B makes LM into a meetsemilatticel lt s bounded with O and l E so it s a lattice by 12508 Prop 2 Meanwhile A U B is the meet of all ats containing both A and Bi By de nition of a simple matroid the singleton subsets of E are atoms in Every at is the join of the atoms corresponding to its elements so LM is atomicl The next step is to show that LM is semimodularl Claim lfFELMandeEEFthenFltFel lndeed ifF g F Q Fe FUe then for any f E F F we have e E Ff C F by 1c so F F e proVing the claiml On the other hand if F lt F then F F e for any atom e E F Fl So we have exactly characterized the covering relations in It follows that L is ranked with rank function rF minlBl B c E F VB Such a set E is called a basis of F We now need to show that r satis es the submodular inequalityl Let F F be ats and let G F Fl Let G lt GVe1 lt GVe1e2 lt lt GVe1epF G lt Gve 1lt Gve 1ve 2 lt lt Gve 1vvefF be maximal chains so that 2 rF ErG p and rFErG ql But thenmFF so F g Fve 1gg Fve 1vvefFvF where each 3 is either lt or l So rF F E rG S p 11 which when combined with 2 implies submodularityl For assertion 2 it is easy to check that A gt A is a closure operator and that A A for lAl S 1 So the only nontrivial part is to establish 1c Note that if L is semimodular e E L is an atom and x Z 5 then x e gt 5 because Mac e 7 Mac 3 re7rxe170 1 Accordingly suppose that e E A but 5 E A U Let x VA E L Then x lt x f and x lt x e S x f which implies that x f x e and in particular f S x e A U 5 proving that A gt A is a matroid closure operator D In View of this bijection we can describe a matroid on ground set E by the function A gt MA where r is the rank function of the associated geometric lattice It is standard to abuse notation by calling this function r also Formally De nition 1 A matroid Tank function on E is a function r 2E A N satisfying Ba MA W and 3b 7 A7 B 2TA BrAU B for all A B Q E Example 1 Let n and 0 S k S E and de ne 7 A mink This clearly satis es 3a and 3b The corresponding matroid is called the uniform matroid Ukn and has closure operator A A if lAl lt k E 1f lAl 2 k So the ats of M of the sets of cardinality lt k as well as of course E itself Therefore the lattice of ats looks like a Boolean algebra Q7 that has been truncated at the km rank For n 3 and k 2 this lattice is M5 for n 4 and k 3 it is the following If S is a set of n points in general position in FIG then the corresponding matroid is isomorphic to Ukn This sentence is tautological in the sense that it can be taken as a de nition of general position Indeed if F is in nite and the points are chosen randomly in some reasonable analytic or measuretheoretic sense then LS will be isomorphic to Uk with probability 1 On the other hand 1F must be sufficiently large in terms of n in order for W to have n points in general position As for isomorphic here s a precise de nition De nition 2 Let M M be matroids on ground sets E E respectively We say that M and M are isomorphic written M E M if there is a bijection f E A E meeting any hence all of the following conditions 1 There is a lattice isomorphism LM E LM 2 7 A for all A Q E Here a l a E 3 fA fA for all A Q E In general every equivalent de nition of matroid and there are several more coming will induce a corresponding equivalent notion of isomorphic Graphic Matroids One important application of matroids is in graph theory Let G be a nite graph with vertices V and edges E For convenience we ll write e my to mean e is an edge with endpoints m y this should not be taken to exclude the possibility that e is a loop ie m y or that some other edge might have the same pair of endpoints De nition 3 For each subset A C E the corresponding induced subyrdph of G is the graph 01A with vertices V and edges A The graphic mdtroid or complete connectivity matroid MG on E is de ned by the closure operator 4 A e my E E l m y belong to the same component of 01A Equivalently e my E A if there is a path between m e consisting of edges in A for short an Apdth For example in the following graph 14 E A because 12 24 C A 1 1 1 2amp3 2amp3 23 4 5 4 5 4 5 GVE A K Proposition 2 The operator A gt A de ned by 4 is d matroid closure operdtor Proof It is easy to check that A Q A for all A and that A C B gt A Q B If e my E A then m y can be joined by an Apath P and each edge in P can be replaged with an Apath giVing an Apath between m an y Finally suppose e my E A but e E A U Let P be an A U fpath in particular f E P Then P U f is a cycle from which deleting f produces an A U epath between the endpoints of D Friday 44 Group Actions and Poly Theory How many different necklaces can you make with four blue two green and one red bead It depends what different means The second necklace can be obtained from the rst by rotation and the third by re ection but the fourth one is honestly different from the rst two 000 If we just wanted to count the number of ways to permute four blue two green and one red beads the answer would be the multinomial coef cient 7 7 gt 7 105i 421 412111 However what we are really trying to count is orbits under a group action Let G be a group and X a set An action of G on X is a group homomorphism a G A x the group of permutations of Xi Equivalently an action can also be regarded as a map G X X A X sending 91 to gr such that o 131 z for every I E X where lg denotes the identity element of G o ghz ghz for every gh E G and z E Xi The orbit of z E X is the set O gzlgEGCX and its stabilizer is S gEGlgzzCG which is a subgroup of Cl To go back to the necklace problem we now see that same really means in the same orbitlli In this case X is the set of all 105 necklaces and the group acting on them is the dihedral group D7 the group of symmetries of a regular heptagoni The number we are looking for is the number of orbits of D7i Lemma 1 For every I E X we have lellel Proof The element gr depends only on which coset of Sac contains 9 so lOgcl is the number of cosets which is lGllS li Proposition 2 Burnside s Theorem The number of orbits of the action of G on X equals the average number of xed points Z zeXlgz c gEG Proof For a sentence P let xP 1 if P is true or 0 if P is false the Garsia chi function Then 1 1 Number of orbits Z T E Z lel xeX l Tl l l zeX 1ZZXQII aceXgeG 1 ZZXltQII ZI6Xgxz7 EGaceX gEG l 9 ole cal Typically it is easier to count xed points than to count orbits directlyi Example 1 We can apply this technique to the necklace example above 0 The identity of D7 has 105 xed points 0 Each of the seven re ections in D7 has three xed points the single bead lying on the re ection line must be red and then the two green beads must be equally distant from it one on each side 0 Each of the six nontrivial rotations has no xed points Therefore the number of orbits is 105 73 7 E 7 9 lD7l 14 7 which is much more pleasant than trying to count them directly 7 Example 2 Suppose we wanted to nd the number of orbits of 7bead necklaces with 3 colors without specifying how many times each color is to be used 0 The identity element of D7 has 37 2187 xed points 0 Each re ection xes one bead which can have any color There are then three pairs of beads ipped and we can specify the color of each pair Therefore there are 34 81 xed points 0 Each rotation acts by a 7cycle on the beads so it has only three xed points all the beads must have the same color Therefore the number of orbits is 218778163 198 More generally the number of inequivalent 7bead necklaces with h colors allowed is k7 7 6k 1 i 14 As this example indicates it is helpful to look at the cycle structure of the elements of G or more precisely on their images ag E Gxi Proposition 3 Let X be a nite set and let a G A 6X be a group action Color the elements ofX with h colors so that C also acts on the colorings 1 For g E G the number of xed points of the action ofg is 1629 where g is the number of cycles in the disjointcycle representation of 19 2 Therefore 2 equivalence classes of colorings 2 hag gEG Let7s rephrase Example 2 in this notation The identity has cycleshape 1111111 so Z 7 each of the six re ections has cycleshape 2221 so Z 4 and each of the seven rotations has cycleshape 7 so Z 1 Thus 1 is an example of the general formula Example 3 How many ways are there to kcolor the vertices of a tetrahedron7 up to moving the tetrahedron around in space Here X is the set of four vertices7 and the group G acting on X is the alternating group on four elements This is the subgroup of 64 that contains the identity7 of cycleshape 1111 the eight permutations of cycle shape 31 and the three permutations of cycleshape 22 Therefore7 the number of colorings is k4 11k 12 i Friday 3 28 Network Flows De nition A network is a directed graph N V E with the following additional data 0 A distinguished source 3 E V and sink t 6 V o A capacity function 5 z E A N We want to think of an stnetwork as modeling a situation where stuff data traf c liquid electrical current etcriis owing from s to t The capacity of an edge is the amount of stuff that can ow through it or perhaps the amount of stuff per unit time This is a very general model that can be specialized to describe cuts connectivity matchings and other things in directed and undirected graphsi A ow on N is a function f z E A N that satis es the capacity constraints 1 0 S fe S Ce V6 6 E and the conservation constraints lt2 u 1 vv 6 v at where M Z fe7 fltvgt Z fe 213 21W That is stuff cannot accumulate at any internal vertex of the network nor can it appear out of nowhere The value of a ow f is the net ow into the sink lfl f t ft f8 f SA The second equality follows from the conservation constraintsi Typically welll assume that there are no edges into the source or out of the sink so t at lfl f t f8 Problem Given a network nd a ow of maximum value Observation If we can nd a path from s to t in which no edge is being used to its full capacity then we can increase the ow along every edge on that path and thereby increase the value of the ow by the same amount 0 1 0 1 m0 m1 The problem is that some ows cannot be increased in this way but are nevertheless not maximal The ow on the right above is an example In every path from s to t there is some edge 6 with fe 06 However the ow shown below evidently has a greater value namely 2 Observation Flow along an edge I can be regarded as negative ow from y to 1 Accordingly there is another way to increase owi Look for a path from s to t consisting of forward edges not being used to full capacity OR backward edges with positive owi Then increasing ow on the forward edges and decreasing ow on the backward edges will increase the value of the owi 01 01 m1 m2 The FordFulkerson Algorithm lnput A network N V E with source 8 sink t and capacity function 5 z E A Ni 1 Let f be the zero flow fe 0 for all edges 6 2 Find an augmenting path ie a sequence of vertices PI 10 57117127 H7In717rt such that for every 239 i 0 i i i n 7 l we have either 0 ei 111141 6 E and fei lt CEi 6 is a forward edge or o ei 114111 E E and fei gt 0 6139 is a backward edge 3 De ne f z E A N by Re fe 1 if 6 appears forward in P e fe 7 1 if 6 appears backward in P and fe fe if e g Pl Then it is easy to verify f satis es the capacity and conservation constraints and that li 4 Repeat steps 2 until no augmenting path can be found The next step is to prove that this algorithm actually works That is when it terminates it will have computed a flow of maximum possible value The dual problem to nding a maximum flow is nding a minimum cutl De nition Let N V E be an stnetworkl Let ST C V with S UT V S T 0 s E S andt 6 Ti The corresponding cut is ST BeE sEStES and the capacity of that cut is CST 256 eEE For example in the networ at which we have been looking we could take 5 8 a c T bdt as follows Then ST mm 23 and cw T 1 2 1 4 A cut can be thought of as a bottleneck through which all ow must pass ForAC V de ne f A Z fe fA 2 ts egAA eeAA Proposition 1 Let f be aflow and let A Q V Then 3 fAf A Zltfvf v7 veA In particular 5T is a cut then 3b f5f 5 f TfT Wt 30 lfl S CS7T In particular the maximum value of a ow is less than or equal to the minimum capacity of a cut a principle known as weak duality Proof We just need some careful bookkeeping For 3a fltAgtfltAgtlt Z fltegt Z 1 lt Z fltegt Z M 1 eEAA egAA eeAA eeAA 7 lt Z M 7 lt Z M 2175 veA 21W veA 7 Z lt Z fe 7 Z fegt 7 20 7 Nu mm 21 5 veA veA For 3b the conservation constraints 2 together with 3a imply that f57f 5 Zltfvif v f87f 8 lfl f t7ft f TfT veS For 3c the capacity constraints 1 imply that lfl f5f 5 S f5 E Z 66 CS7T eEST Proposition 2 Suppose that f is a flow that has no augmenting path Let S v E V l there is an augmenting path from s to v T V S Then s E S t E T and C5 T In particular f is a maximum flow and 5 T is a minimum cut Proof Note that t g S precisely because f has no augmenting path By 3b we have m 7 fltsgt7rltsgt 7 Z fltegt7 Z fe 7 Z e eESS eESS eESS But fe Ce for every e E 5T otherwise 5 would be bigger than what it actually is so this last D quantity is just CST The nal assertion follows by weak duality We have proven Theorem 3 For any network N the FordFulkerson Algorithm terminates in nite time and outputs a maximum flow f and a minimum cut 5T such that CS T Bdonday 218 The Tutte Polynomial Let M be a matroid with ground set E Recall that we can delete or contract an element e E E to obtain respectively the matroids M E e amd Me on E e whose basis systems are ewe B l Be em aw Me Be l B E M e E B Thus deletion is de ned whenever e is not a coloop and contraction is de ned whenever e is not a loop De nition 1 The Tutte polynomial of M is compute recursively as 1 HEamp 1 TMTMxy xTMe ifeisacoloop y TM E e if e is a loop TM E e TMe otherwise for any e E E If M MG is a graphic matroid we may write TG instead of This is more of an algorithm than a de nition and at this point it is not even clear that TM is well de ned because the formula seems to depend on the order in which we pick elements to delete and contract However a miracle occurs it doesn t We will soon prove this by giving a closed formula for TM that does not depend on any such choice In the case that M is a uniform matroid then it is clear at this point that TM is wellde ned by 1 because up to isomorphism M E e and Me are independent of the choices of e E E Example 1 Suppose that M U n that is every element of E is a coloop By induction TMx y x Dually if M E U0n ie every element of E is a loop then TMx y y Example 2 Let M 112 the graphic matroid of the digon two vertices joined by two parallel edges Let e E E then TM TM E e TMe TU1l TUol x y Example 3 Let M E 123 the graphic matroid of K3 as well as the matroid associated with the geometric lattice H3 M5 Applying l for any e E E gives TltU2lt3gtgt TltU2lt2gtgt Tam x2 x y On the other hand WWWTW NQ Iyf In general we can represent a calculation of TM by a binary tree in which moving down corresponds to deleting or contracting M M e Me M e f M ef Me f Mef Example 4 Here is a nonuniform example Let G be the graph below b 1 One possibility is to recurse on edge a or equivalently on b c or d When we delete a the edge 51 becomes a coloop and contracting it produces a copy of K3 Therefore TGia 95952 xy by Example 3 Next apply the recurrence to the edge I in 011 The graph Gaib has a coloop c contracting which produces a digon Meanwhile MGab E 113 Therefore TGa7b xxy and TGab xyy2i Putting it all together we get TG TGiaTGa TGiaTGaibTGab xx2xy xxy WM212 zg2z 2zyxyz m2 xyj ltD xxy xy9 On the other hand we could have recursed rst on 5 getting TG TGieTGe TG757cTGiecTGeicTGec x3 x2xy xxy yxy zg2z 2zyxyz x3 x2 xy xxy yxy We can actually see the usefulness of TM even before proving that it is wellde ned Proposition 1 TM 1 1 equals the number of bases of M Proof Let bM TM 11 Then 1 gives 1 if E 2 MM JG 3 ifeisacoloop bge if e is a loop bM 7 e bMe otherwise which is identical to the recurrence for that we observed on Friday 215 D Many other invariants of M can be found in this way by making appropriate substitutions for the indeter minates x y in In particular if we let CM TM 2 2 then 1 if E Z CM 2cG5 if e is a coloop 2c 5 if e is a loop CM 7 e CMe otherwise so CM 2lEl This suggests that TM ought to have a closed formula as a sum over subsets A Q E with each summand becoming 1 upon setting as 1 and y 17for example with each summand a product of powers of x 7 1 and y 7 1 In fact this is the case Theorem 2 Let r be the Tank function of the mat39mid M Then 2 TW 962 2061TEgt TAgtyiD AHW A93 The quantity rE 7 rA is the comnk of A it is the minimum number of elements one needs to add to A to obtain a spanning set of M Meanwhile A 7 rA is the nullity of A the minimum number of elements one needs to remove from A to obtain an acyclic set Accordingly 2 is referred to as the the comnknullity generating function As an exercise work out TG x y for the graph G of Example 4 you shoudl get the same answer as above Proof of Theorem 2 Let x y denote the generating function on the righthand side of We will prove by induction on n that TM obeys the recurrence 1 for every ground set element e hence equals Let r and r denote the rank functions on M 7 e and Me respectively For the base case if E 3 then 2 gives 1 If e is a 1001 then rA rA rA U 5 for every A C E 5 s0 TM Z x 71rEgt7rAgty 71A7TAgt AgE Z x 71TEgt7TAgty 7 UMPMA 7 Z x 71TEgt7TBgty 71A7TBgt A93 1393 egA eEB Z x 71rEe7rAy 7 1A7rA 7 Z x 7 1rEe7rAgty7 1A17rA AgEe AgEe 7 lt1 y 71gt Z x 71gt ltEegt4ltAgtlty 71gt A 4W AQEV 7 e If e is a coloop then 7 HA rA rA U 5 7 1 for every A C E 5 s0 Z x 71TETAy 71WTA AgE Z x 71rEgt7rAgty 7 1A7TAgt 7 Z x 71rEgt7rBgty 71A7TBgt egAgE eeBgE Z x 7 1r Eegt1gt7rAgty7 1A7T Agt AgEe 7 Z x 7 1T Ee1gt7r A1gt y 7 1A17T A1gt AgEe Z x 7 1rEe17rAgty 7 1A7T Agt 7 Z x 7 1T Eegt7r Agty 71A7T Agt AgEe A Ee 95 7171 Z x 71r Eegt7r Agty 71A7T Agt A Ee Finally suppose that e is neither a 1001 nor a coloopi Then rA rA and 7 HA rA U 5717 Therefore TQM Z x 71rEgt7rAgty 71A7TAgt AgE Z 95 71rEgt7rAgty71A7TAgt 7 96 717 E77 AU8y 71AUe7rAUe AgEe Z 71TE8TAy 71WTA 7 71T E1T A1y71A17T A71 AgEe Z x 71rEegtrAgty 7 UMPTA 7 7 Z x 71r Eegt7rAgty 71A7r A AgEe AgEe TM 7 e TMei Wednesday 220 The Tutte Polynomial De nition 1 Let M be a matroid with ground set E and let 5 E E The Tutte polynomial TM TM x y is computed recursively as follows T1 If E 3 then TM 1i T23 If e E E is a loop then TM y TMei T2b If e E E is a coloop then TM x TM 7 e i T3 If e E E is neither a loop nor a coloop then TM TM 7 e TMei We prove that TM is wellde ned by giving a closed formula for it the comnknullityquot generating function Theorem 1 Let 7 be the Tank function of the mat39mid M Then 1 TW 962 Z 96 1TEgt TAgtyi D AHW AgE Proof Let x y denote the generating function on the righthand side of We Will prove by induction on n that TM obeys the recurrence of De nition 1 for every ground set element e hence equals Let T and T denote the rank functions on M 7 e and Me respectively For T1 if E 3 then 1 gives l For T23 let e be a loop Then TA 7 A 7 A U e for every A C E e so TOW Z x 1TEgtTAgty UlAliMA Ag Z x 1TEgtETAgty UlAleMA Z x 1TEgtETBgty UlAleMB Ag BgE eEA eEB Z x 1rEegterAgty millerA Z x 1rEegterAgty D AHIerA A Ee A Ee lt1lty 71 Z x 71gt ltEegtrltAgtlty 71gt A rW A Ee 7 e For T2b let e be a coloopi Then 7 A 7 A 7 A U e 7 l for every A C E e so TM Z x 1TEgtETAgty UlAleMA Ag Z x 1TEgtTAgty UlAliMA Z x 1TEgtTBgty UlAliMB eEAgE eEBgE Z x 1T Eegt1gtirAgty UlAlirKA AgEe Z x DU Ee1gt7r A1gty UlAHleUKAHU AgEe The quantity TEgt 7 TAgt is the comnk of A it is the minimum number of elements one needs to add to A to obtain a spanning set of M Meanwhile lAl 7 TAgt is the nullity of A the minimum number of elements one needs to remove from A to obtain an acyclic set Z 9571y ltEegt1er ltAgty7muslinA Z x71rltEegtewltAgty7mumA ACEe AgEe 95 711 Z x 71r Eegtr Ay 71lAlr Agt c e Finally suppose that e is neither a loop nor a coloop Then rA rA and r A rA U e 71 so TQM Z x 71rEgt7rAgty 71lAl7rAgt AgE Z 71rE7rAy71Al7rA 71rE7rAUey 71AUel7rAUe AgEe 7 Z 95 71rltEegterltAgty 71AerltAgt 7 95 7 1r E17rA1y 71A17ltr ltAgtelgt AgEe Z I71rltEegterltAgty7DimerA Z x71r ltEegtewltAgty7 DuneA AgEe AgEe TM7eTMe D Which is T3 As a consequence we can obtain several invariants of a matroid easily from its Tutte polynomial Corollary 2 For every matroid M we have number of bases of M number of independent sets of M number of spanning sets of M Proof We ve already proved 1 and 2 but they also follow from the coranknullity generating function Plugging in x 2 y 2 Will change every summand to 1 Plugging in x 1 an y 1 Will change every summand to 0 except for those sets A that have corank and nullity both equal to 0 7 that is those sets that are both spanning and independent The veri cations of 3 and 4 are analogous D A little more generally we can use the Tutte polynomial to enumerate independent and spanning sets by their cardinality 2 Z 11 qTMT1q 11 Ag independent 3 Z 11 qTMT1 111 1 Ag spanning Another easy fact is that TM is multiplicative on direct sums TM1 EB M2 TM1TM2i The Chromatic Polynomial Let G E be a graph A hcoloring ofG is a function f V 7gt h the coloring is proper if y Whenever verices v and w are adjacent Let 310 denote the set of proper colorings of G The function h gt lKMGH is called the chromatic function xG h o If G has a loop then its endpoints automatically have the same color so xG h 0 o If G Kn then all vertices must have different colors There are k choices for f1 h 7 1 choices for f2 etc so xK h Mk 7 lh 7 2 h 7 n1 0 At the other extreme let G E the graph With n vertices and no edges Then AE h h o If Tn is a tree With n vertices then pick any vertex as the root this imposes a partial order on the vertices in Which the root is l and each nonroot vertex v is covered by exactly one other vertex pv its parent There are k choices for the color of the root and once we know there are k 7 1 choices for Therefore xTn h Mk 7 l 1i o xG H h xG hXH h Where denotes disjoint union of graphs Theorem 3 For every graph G we have MG k 1 G 1k39TG 1 kao where nG is the number of vertices of G Wednesday 430 The RSK Correspondence De nition 1 Let A b n A standard Young tableau of shape A is a lling of the Ferrers diagram of A with the numbers 1 2 l l l n that is increasing lefttoright and toptobottoml We write SYT A for the set of all standard tableaux of shape A and set F lSYTAl For example if A 33 then f 5 the members of SYTA are as follows 135134125124123 246256346356456 The RSK cu l 7 for D lquot S h t d Vnuth constructs for every permutation w E G a pair RSKw P of standard tableaux of the same shape A b n The idea is to rowinsert the numbers 101102 1107 into P one by one and to use Q to record the order in which cells are added Example 1 Let w 57214836 E 63 We start with a pair P of empty tableauxl Step 1 Rowinsert wl 5 into Pl We do this in the obvious way Since it s the rst cell added we add a cell containing 1 to Q Step 2 Rowinsert 112 7 into Pl Since 5 lt 7 we can do this by appending the new cell to the top row and adding a cell labeled 2 to Q to record where welve put the new cell in Pl 1 P Q Step 3 Rowinsert wg 2 into Pl This is a bit trickier We canlt just append a 2 to the rst row of P because the result would not be a standard tableaul The 2 has to go in the top left cell but that already contains a 5 Therefore the 2 bumps the 5 out of the rst row into a new second rowl Again we record the location of the new cell by adding a cell labeled 3 to Step 4 Rowinsert w4 1 into Pl This time the new 1 bumps the 2 out of the rst rowl The 2 has to go into the second row but again we canlt simply append it to the right Instead the 2 bumps the 5 out of the second row into the new third rowl 1b 10 101 Step 5 Rowinsert w5 4 into P The 4 bumps the 7 out of the rst row The 7 however can comfortably t at the end of the second row without any more bumping 16 Step 6 Rowinsert wt 8 into P The 8 just goes at the end of the rst row 48 2M u in 1 2 1f 5 Step 7 Rowinsert w7 3 into P 3 bumps 4 and then 4 bumps 7 1 3 8 1 2 6 2 4 3 5 5 7 4 7 1g Step 8 Rowinsert W3 6 into P 6 bumps 8 into the second row 1 3 6 I 1 2 6 I 2 4 8 I 3 5 8 I 5 7 4 7 0 A crucial feature of the RSK correspondence is that it can be reversed That is given a pair P Q we can recover the permutation that gave rise to it Example 2 Suppose that we were given the pair of tableaux in 1h What was the previous step To get the previous Q we just delete the 8 As for P the last cell added must be the one containing 8 This is in the second row so somebody must have bumped 8 out of the rst row That somebody must be the largest number less than 8 namely 6 So 6 must have been the number inserted at this stage and the previous pair of tableaux must have been those in lg Example 3 Suppose P is the standard tableau with 18 boxes shown on the left 1 2 5 81018 3 41112 6 713 9 1517 ii 14 Suppose in addition that we know that the cell labeled 16 was the last one added because the corresponding cell in Q contains an 18 Then the bumping path77 must be as shown on the right That is the 16 was bumped by the 15 which was bumped by the 13 and so on To nd the previous tableau in the algorithm we push every number in the bumping path up and toss out the top one l 3 6 9 14 That is we must have gotten the original tableau by rowinserting 10 into the tableau just showni Since the correspondence is reversible we have the following fact Theorem 1 The RSK correspondence is a bijection 6 U SYT gtlt SYT1 AFn Some Nice Properties of RSK Here is an immediate consequence of Theorem 1 Corollary 2 SAMOA nl To con rm this for n 3 here are all the SYT7s with 3 boxes Note that f3 f1gt1gt1 l and fed 2 and 12 12 22 6 3 This calculation ought to look familiar Another neat fact about the RSK correspondence is this Proposition 3 Let w E G If RSKw P Q then RSKw 1 QP In particular the number of involutions in 6 is Min Generalized RSK and Schur Functions The RSK correspondence can be extended to obtain more general tableaux than just SYT sl We can think of a permutation in twoline notation ilel 12345678 57214836lt57214836gtl What if we allowed generalized permutations ilel things of the form 797041042quot3904n lt2 414 b2 b where aibi E n and the ordered pairs a1b1luanbn are in lexicographic order but repeats are allowed Example 4 Consider the generalized permutation 7112444555 w 241133224 We can rowinsert the elements of the bottom row into a tableau P while recording the elements of the top row in a tableau Q Q etc The tableaux PQ we get in this way will always be weakly increasing eastward and strictly increasing southwardithat is they will be columnstrict tableaux Moreover their weights will be 1PIa1quot391anv IQIb1quot39Ibn Meanwhile a generalized permutation w as in 2 can be encoded by an n X n matrix M E Nnxn with ma h l ah i7 bh i For example the generalized permutation w of Example 4 corresponds to the integer matrix 0 1 0 OMOOO 1 1 0 0 0 1 0 0 1 GOOD COCO Therefore7 Zlt Z 2 ya 28mm A PESYTO QESYTQ A Corollary 4 The Schur functions form an orthonormal Zbasis for A under the Hall inner product Friday 11808 De nition A partially ordered set or poset is a set P equipped with a relation 3 that is re exive antisymmetric and transitive That is for all x y 2 E l x S x re exivity 2 If x S y amd y S x then x y antisymmetry 3 If x S y and y S 2 then x S 2 transitivity We ll usually assume that P is nite Example 1 Boolean algebras Let 1 2 n a standard piece of notation in combinatorics and let Q7 be the power set of We can partially order Q7 by writing S S T if S Q T Y The rst two pictures are Hasse diagrams They don t include all relations just the covering relations which are enough to generate all the relations in the poset As you can see on the right including all the relations would make the diagram unnecessarily complicated De nitions Let P be a poset and z y E P o x is covered by y written 95 lt y if x lt y and there exists no 2 such that x lt 2 lt y o The interval from x to y is xy2 P 953233 This is nonempty if and only if x S y and it is a singleton set if and only if x The Boolean algebra Q7 has a unique minimum element namely 3 and a unique maximum element namely Not every poset has to have such elements but if a poset does we ll call them 0 and 1 respectively De nition A poset that has both a O and a l is called bounded An element that covers 0 is called an atom and an element that is covered by l is called a coatorn For example the atoms in Q7 are the singleton subsets of De nition A subset C C P is called a Chain if its elements are pairwise comparable It is called an antichain or clutter if its elements are pairwise incomparable 12 13 23 13 23 a a e a 23 f gt94 gt94 1 2 1 2 1 2 3 1 2 a W chain antichain antichain neither Ranked Posets One of the many nice properties of n is that its elements fall nicely into horizontal slices sorted by their cardinalities Whenever S lt T it is the case that lTl 5 1 A poset for which we can do this is called a ranked poset However we can t de ne ranked in this way because it is tautological lnstea De nition A poset is ranked if every maximal chain has the same cardinality A poset is graded if it is ranked and bounded If P is a graded poset its rank function r P A is de ne Mac length of any chain from O to 95 Here length measures the number of steps not the number of elements 7 iiei edges rather than vertices in the Hasse diagrami Note Maximal chain and maximum chain are not synonyms Maximal means not contained in any other while maximum means of greatest possible size Every maximum chain is certainly maximal but not necessarily vice versaithat s precisely what it means for a poset to be ranke An easy consequence of the de nition is that if x lt y then ry Mac 1 proof left to the reader De nition Let P be a ranked poset with rank function r The rankgenerating function of P is the formal power series FPII Z a xeP Thus for each k the coefficient of qlC is the number of elements at rank k We can now say that the Boolean algebra is ranked by cardinality In particular Fa q Z 11 1 11 Sch Of course if you expand this polynomial out it is palindromic because the coefficients are a row of Pascal s Triangle That is 7 is ranksymmetric In fact much more is true For any poset P we can de ne the dual poset Pquot by reversing all the order relations or equivalently turning the Hasse diagram upside down It s not hard to prove that the Boolean algebra is selfdual iiei Q7 1 from which it immediately follows that it is ranksymmetric The following is a nonranked poset an important example to have around called N5 Example 2 The partition lattice Let ll be the poset of all set partitions of E g two elements of H5 are S 134 2 5 abbr S 134l25 T l3 4 25 abbr T 13l4l25 The sets 134 and 25 are called the blocks of S We can impose a partial order on Hn by putting S S if every block of T is contained in a block of S for short T re nes S 1234 123 123M 124m 134m 234m 12 34 13 24 14 23 gtk v39 lt t v gtVr 12w 1 23 13m 1234 13W 23m4 1423 24MB 34m2 2 3 1l2l3l4 o The covering relations are of the form merge two blocks into one o H is graded With 0 1 2 n and l 12 n The rank function is MS n7 o The coef cients of the rankgenerating function of H are the Stirling numbers of the second kind Sn k number of partitions of into k blocks That is Fnq FHJQ 2301 Mamet k1 For example F301 1 Sq q2 and F401 1 6q 7112 q Friday 418 Characters of the Symmetric Group We worked out the irreducible characters of 64 ad haul Weld like to have a way of calculating them in genera 1 Recall that a partition of n is a sequence A A11 1 1 A1 of weakly decreasing positive integers whose sum is n We write A b n to indicate that A is a partition of n The number of partitions of n is denoted For A b 71 let CA be the conjugacy class in 6 consisting of all permutations with cycle shape A Since the conjugacy classes are in bijection with the partitions of n it makes sense to look for a set of representations indexed by partitionsl De nition 1 Let M M1HlMm k 71 The Ferrers diagram of shape M is the top and leftjusti ed array of boxes with M1 boxes in the ith rowl A Young tableau of shape M is a Ferrers diagram with the numbers 121 1171 placed in the boxes one number to a box Two tableaux T T of shape M are raw equivalent written T N T if the numbers in each row ofT are the same as the numbers in the corresponding row of TA A tabloid of shape M is an equivalence class of tableaux under rowequivalence A tabloid can be represented as a tableau without vertical lines separating numbers in the same rowl We write shT M to indicate that a tableau or tabloid T is of shape M1 1 3 6 1 3 6 2 7 2 7 4 5 4 5 Ferrers diagram Young tableau Young tabloid A Young tabloid can be regarded as a set partition Th1 1 1 Tm of n in which Mix The order of the blocks Tl matters but not the order of digits within each block Thus the number of tabloids of shape M is lt71 7 71 M M1Mm The symmetric group 6 acts on tabloids by permuting the numbers Accordingly we have a permutation representation MM V of 6 on the vector space V of all Clinear combinations of tabloids of shape M1 Example 1 For n 3 the characters of the representations MM are as follows A 111 21 3 M 3 1 1 1 1 M 21 3 1 0 M111 6 0 0 lCAl l 3 2 Many familiar representations of 6 can be expressed in this forml 0 There is a unique tabloid of shape M T 1 Every permutation xes T so PM g ptriv o The tabloids of shape M 11H i 1 are just the permutations of Therefore P111 g pregA o A tabloid of shape M n 7 11 is determined by its singleton parti So the representation pH is isomorphic to the action of 6 on this part by permutation that is pain E PdefA For n 3 the table in 1 is triangular which implies immediately that the characters M are linearly independent It s not hard to prove that this is the case for all no De nition 2 The lexicographic order on partitions AM b n is de ned as follows A gt M if for some h gt 0 A1 M17 A1A2 M1M27 A1quot39k71 1quot39k717 1quot39kgtl41quot39Mk Abbreviate XW by XH henceforth Since the M are permutation representations we can calculate XH by counting xed points That is XMC tabloids T l shT M wT T for any w E C Proposition 1 Let A M F n Then 1 XAltCA f 039 2 XHC 0 only if A S M in lexicographic order Proof To show that X C 0 let w 6 CA we must nd a tabloid T of shape A xed by w Indeed we can take T to be any tabloid whose blocks are the cycles of wi For example if w 1 3 6 2 7 4 5 6 67 then T can be either of the following two tabloids On the other hand w xes a tabloid T of shape M if and only if every cycle of w is contained in a row of P In particular the sum of any r parts of A must be less than or equal to the sum of some r parts of M hence less than or equal to the sum of the rst r parts of M which implies that A S M Corollary 2 The characters Xu 1 M b n form a basis for ClG Proof The number of these characters is dim CZGi Moreover Proposition 1 implies that the pn gtlt pn matrix X XHCHHL is triangular hence nonsingulari D We can transform the rows of the matrix X into a list of irreducible characters of 6 by applying the GramSchmidt process measuring orthogonality of course with the inner product Indeed the triangularity of X means that we will be able to label the irreducible characters of 6 as iylvfn so that 2 0217 XVgtG 07 lt2VXHgtG0 ifVltM1 Example 2 Recall the table of characters 1 of the representations pH for n 31 We will use this to produce the table of irreducible characters For brevity let7s omit the commas between the parts of partitions 1 First M3 111 va is irreducible We therefore call it quotqu Second for the character Mm we observe that ltX217 23gtG 1 Applying GramSchmidt we construct a character orthonormal to 23 521 X21lt3 2707411 Notice that this character is irreduciblei Finally for the character X011 we have H ltX1117 23gtG ltX1117 221gtG Accordingly we apply GramSchmidt to obtain the character E0 5111 X111 563 25621 17 1711 which is 1dimensional hence irreduciblei In summary the complete list of irreducible characters labeled so as to satisfy 2 is as follows A 111 21 3 23 1 1 1 Xtriv gm 2 0 71 H 1 H H C111 Xsign To summarize our calculation we have shown that 1 1 1 1 0 0 1 1 1 M 310 110 2 0 71KM W3 6 0 0 1 2 1 1 71 1 W 3 K that is XMZKAMOA A The numbers K1 are called the Kostka numbers We will eventually nd a combinatorial interpretation for them which will imply easily that the matrix K is unitriangulari Wednesday 227 Mobius Inversion Let P be a poseti Recall that we have de ned the Mz39ibius function of P n P X P A Z by l npxx l for all x E Pt 2 If I i y then 130641 0 3 If x lt y then We 2 7 Sim mac 2 We saw last time that if P is a product of n chains a distributive lattice then A 71 if x is the join of 1 atoms 0 MP 96 0 otherwise In particular Ma a 71 Also if L L q is the modular subspace lattice and fnq MLUA l then we saw that fn q 71 116 for n S 4 Why is the Mobius function useful It is the inverse of Q in the incidence algebra check this It implies a more general version of inclusionexclusion called Mo39bius inversion lt behaves nicely under poset operations such as product It has geometric and topological applicationsi Even just the single number hp tells you a lot about a bounded poset P it is analogous to the Euler characteristic of a topological space Theorem 1 Mobius inversion formula Let P be a poset in which every principal order ideal is nite and let fg P A C Then 1 996 21 W E P ltgt x ZMy 901 W E P 131 ny 1b 996 21 W E P ltgt x ZMI y9y W E P 342 3421 Proof A trivial observation in linear algebra77 istanleyi We regard the incidence algebra as acting Clinearly on the vector space V of functions f P A Z by f 106 Z My elml yin a f96 Zaxyfy yin for oz E P In terms of these actions formulas la and lb are respectivelyjust the trivial observations 2a 2b We just have to prove that these actions are indeed actions iiei 0 lfal fl and fa lfal Indeed f a my Ba was ymx 13y Z Z axz zyfx rSyzEMyl Z Zawvm my 23y mg Di az zy f a my 23y and the other veri cation is analogous D In the case of 7 the proposition says that gm ZN W1in gt M ZEUWMB W1in BgA BgA Which is just the inclusionexclusion formula So Mobius inversion can be thought of as a generalized form of inclusionexclusion that applies to every poset Example 1 Here s an oldiebutgoodie counting derangements or permutations a E 37 With no xed points For S C 71 let fSa E 37 l 7239 239 i z ES 950 E 37 l 7239 239 ifz39ES It s easy to count 95 directly If s 5 then a permutation xing the elements of S is equivalent to a permutation on S so 95 n E s It s hard to count directly However 93 Z My RDS Rewritten in the incidence algebra HQ this is just 9 Thus f M g or in terms of the Mobius inversion formula 1b fS 2 MS RgtgltRgt Z 71gt Rt swn 7 W Z lt71gtHltn 7 r R25 R25 7 s The number of derangements is then Which is given by the wellknown formula i mm 7 r 7 0 Example 2 You can also use Mobius inversion to compute the Mobius function itself In this example we ll do this for the lattice Lnqi As a homework problem you can use a similar method to compute the M obius function of the partition lattice Let V F2 let L L q and let X be a Fqvector space of cardinality 95 yes cardinality not dimension De ne 9W number of Fqlinear Inaps lt1 V A X such that kerlt1 D W xn dimwi Choose a basis B for W and extend it to a basis B for V Then lt1 must send every element of B to zero but can send each of the n 7 dirn W elements of M B to any of the as elements of X Let number of Fqlinear Inaps lt1 V A X such that kerlt1 W Then 9W zij fU so by Mobius inversion fW 2 mm UM U VQUQW In particular if we take W to be the zero subspace 0 O we obtain f0 Z MLltOUgtx d mU Ugv 3a 2 ML Uhnirw where r rank function of L UEL one toone linear Inaps lt1 V A X 3 3 961I4x42 39xiqn ll Choose an ordered basis 11 i vn for V and send each 11 to a vector in X not in the linear span of lt1gtv1 v171 This is just an identity of polynomials in the ring if you like So we can equate the constant coefficients in 3a and 3b which gives mm 1 AWN The Characteristic Polynomial De nition 1 Let P be a nite graded poset with rank function r and suppose that n The characteristic polynomial of P is de ned as XPx Zm wzrw zEP This is an important invariant of a poset particularly if it is a lattice 0 We have just seen that XLn4 96 7 96 71W 7 106 7 112 9c 7 If o If P is a product of n chains then the elements Xmas gm 2 z 7 m 0 H7 has a nice characteristic polynomial which you will see soon The characteristic polynomial is a specialization of the Tutte polynomial Theorem 2 Let L be a geometric lattice with atoms E Let M be the corresponding matroid on E and r its rank function Then XLx 7 71TMgtTM 17 I 0 Proof We have lt71gtTltMgtTltM 1 w Arm Zlt7xgtTltMgt7TltAgtANAHW Ag ZxrMgt7rAgt1lAl AgE Z Z1A xrltMgterltKgt KEL 493 A MK so it suf ces to check that MLUA To do this we use Mobius inversion on L For K E L let M 2 HM ACE AgK So 9 f Q and f g a in KL Then l but if J y 0 then 9J 0 because the sum ranges over all subsets of the atoms lying below K so by Mobius inversion this time 1a we have NO Z w KW W11 13K as desired D Monday 33 Crosscuts Recall that the Mobius algebra AL of a lattice L is the vector space of formal Clinear combinations of elements of L with multiplication given by the meet operation We showed last time that AL E ClLl as rings because the elements Ex Eyltx uy 95 satisfy EEEy 61151 where 61y is the Kronecker delta 7 De nition 1 Let L be a lattice A A 7 An upper crosscut ofL is a set X C L 1 such that if y E L X 1 then y lt x for some as E X i A lower crosscut of L is a set X C L such that if y E L X 0 then y gt x for some as E X Proposition 1 Rota s Crosscut Theorem Let L be a nite lattice and let X be an upper crosscut Then 1 L Z Ulyl YgX Y6 Dually ifX is a lower crosscut then 1b ML Z U yl YgX VYi Proof Let x E L We have the following equation in the Mobius algebra of L my tel Ham Mm 25y cEX acEX ygac yEY where Y y E L l y i x for all x E X But Y because X is an upper crosscuti That is 2 Hdix Ei 2min acEX Therefore On the other hand 3 Haw ZHWAA xEX AgX Now extracting the coefficient of O on the righthand sides of 2 and 3 yields 1a The proof of 1b is simi art D We already know that un 71 What if L is distributive but not Boolean Proposition 2 Let L be a dist ributiue lattice that is not Boolean Then uL 0 Proof The set X of atoms of L is a lower crosscuti Since L is not Boolean it has a joinirreducible element b E Xi But b i V X because b i a for all a E X this is Lemma 2 of the lecture notes from 12807 In particular V X y i so the sum on the righthand side of 1b is empty U More generally ML 0 if L is a lattice in which i is not a join of atoms or dually if 0 is not a meet of coatoms i The crosscut theorem will also be useful in studying hyperplane arrangementsi A Topological Application Proposition 3 Let P be a chain nite bounded poset and let cl 0x0ltx1ltltxll the number of chains of lengthi between O and Then 4 MP Zuni Proof The incidence algebra makes the proof almost triViali Recall that cl 7110 7 ll0 Since sufficiently high powers of n vanis The expression 4 looks like an Euler characteristici lndeed let P be a nite poseti The order complex of P is de ned as the simplicial complex A AP Whose vertices are elements of P and Whose faces are chains of Pi Then Proposition 3 implies that uP is the reduced Euler characteristic of Al Another nice fact is the following result due to l Folkman 1966 Whose proof used the crosscut theoremi Theorem 4 Let L be a geometric lattice of rank r and let P L 0 Then ZlML ifi r 7 2 0 otherwise H1APZ 2 where H denotes reduced simplicidl homology Hyperplane Arrangements De nition 2 Let K be a eld and n 2 1 A linear hyperplane in Kquot is a vector subspace ofcodimension 1 An a ine hyperplane is a translate of a linear hyperplane A hyperplane arrangement A is a nite collection of distinct hyperplanes The number n is called the dimension of A Example 1 The lefthand arrangement A1 is linear it consists of the lines 95 0 y 0 and x y The righthand arrangement A2 is af ne it consists of the four lines 95 y x 7y y l and y 7 Each hyperplane is the zero set of some linear form so their union is the zero set of the product of those 3 linear forms We can specify an arrangement concisely by that product called the de ning polynomial of A as an algebraic variety in fact For example the de ning polynomials of A1 and A2 are avgx 7 y and avgx 7 y 7 1 respectively Example 2 Here are some 3D arrangements pictures produced using Maple The Boolean arrangement Q7 consists of the coordinate hyperplanes in nspace so its de ning polynomial is acle 957 Here s 3 The braid arrangement Q7 consists of the hyperplanes x1 7 xj in nspace so its de ning polynomial is x 7 xj 1 lltjS7l Here s Brg Every hyperplane in 7 contains the line spanned by the allones vector If we project R4 to the quotient by that line then A4 ends up looking like this The Intersection Poset De nition 3 Let A C K be an arrangement lts intersection poset LA is the poset of all intersections of subsets of A ordered by reverse inclusion This poset always has a 0 element namely K It has a 1 element if and only if HeA H y ll such an arrangement is called central Proposition 5 Let A C K be an arrangement The following are equivalent 0 A is central 0 A is a translation of a linear arrangement 0 LA is a geometric lattice Proof Linear arrangements are central because every hyperplane contains 6 E K Conversely if A is central and p E HeA H then translating everything by 7p produces a linear arrangement If A is central then LA is bounded It is a joinsemilattice with join given by intersection hence it is a lattice Indeed it is a geometric lattice it is clearly atomic and it is submodular because it is a sublattice of the chain nite modular lattice LK 7 that is the dual of the lattice of all subspaces of B When A is central we may as well assume linear the matroid associated with LA is naturally represented by the normal vectors to the hyperplanes in A Therefore all of the tools we have developed for looking at lattices and matroids can be applied to study hyperplane arrangements The dimension of an arrangement cannot be inferred from the intersection poset For example if A1 is as above then LA1 E LBr3 but dimA1 2 and dim Brg 3 A more useful invariant of A is its rank rank A de ned as the rank of LAi Equivalently de ne W C K to be the subspace spanned by the normal vectors up Then rankA dim W De nition 4 An arrangement A is essential if rankA dim A In general the essentialization essA is the arrangement H W l H e A C W Equivalently if V WL HeA H then rankA n 7 dim V and we could de ne the essentialization of A as a quotient HV l HEA C KnV Observe that essA is essential and that LA is naturally isomorphic to LessAi Wednesday 12308 Posets More Examples Example 1 Young s lattice A partition is a sequence A A1 Ag of weakly decreasing positive integers ie A1 2 2 Ag gt 0 For convenience set A 0 for all i gt A Let Y be the set of all partitions partially ordered by A 2 o if A 2 o for all i 12 This is an in nite poset but it is locally nite ie every interval is nite There s a nice pictorial way to look at Young s lattice lnstead of thinking about partitions as sequence of numbers view them as their corresponding Ferrers diagrams northwestjusti ed piles of boxes whose i h row contains A boxes For example 5542 is represented by the following Ferrers diagram Then A 2 o if and only the Ferrers diagram of A contains that of o The top part of the Hasse diagram of m B11 B E D11 E3 D1 D Q De nition An isomorphism of posets PQ is a bijection f P A Q such that x S y if and only if S We say that P and Q are isomorphic written P E Q if there is an isomorphism P A An automorphism is an isomorphism from a poset to itse Young s lattice Y has a nontrivial automorphism given by conjugation This is most easily described in terms of Ferrers diagrams reverse the roles of rows and columns It is easy to check that if 2 M then X 2 M where the prime denites conjugation Example 2 The clique poset of a graph Let G V E be a graph with vertex set A clique of G is a set of vertices that are pairwise adjacent Let KG be the poset consisting of set partitions all of whose blocks are cliques in G ordered by re nement 123 12 34 13 24 234 G KG This is a subposet of H a subset of H7 that inherits its order relation This poset is ranked but not graded since there is not necessarily a 1 Notice that H7 the complete graph on n vertices De nition A poset L is a lattice if every x y E L have a unique meet as y and join as V y That is acAymaxz L 23xy xVyminz L 22xy Note that eg ac y ac if and only if ac S y These operations are commutative and associative so for any nite M C L the meet M and join VM are wellde ned elements of L In particular every nite lattice is bounded with 0 L and l VL Example 3 The Boolean algebra 7 is a lattice with S T S T and S T S U T Example 4 The complete graded poset Po1 a has n l and 11 gt 0 elements at rank 239 for everyz39 gt 0 with every possible order relation ier9c gt ry gt ac gt P315 This is a lattice if and only if no two consecutive 11 s are 2 or greater Example 5 The clique poset KG of a graph G is in general not a lattice because join is not wellde ned Meet however is wellde ned One could therefore call the clique poset a meetsemilattice It can be made into a lattice by adjoining a brandnew 1 element In the case that G K7 the clique poset is a lattice namely the partition lattice H Example 6 Lattices don t have to be ranked For example the poset N5 is a perfectly good lattice Friday 52 The Frobenius Characteristic Let R be a ring Denote by CZRGn the vector space of RValued class functions on the symmetric group Gni If no R is speci ed7 we assume R C De ne Cos GBCWGn n20 We make CZG into a graded ring as follows For f1 6 CZGn1 and f2 6 CZGM7 we can de ne a function f1 f2 6 ca nl gtlt Gm by f1 1020017102 f1w1f2w2 There is a natural inclusion of groups Gm gtlt Gm Gn1n27 so we can de ne f1 f2 6 CZGMM by means of the induced character 6 f1 39 f2 Indg m f1 f2 since the formula for induced characters can be applied to arbitrary class functions This product makes CZG into a graded Calgebrai We won7t prove this For a partition A b n7 let 1A be the indicator function on the conjugacy class CA C Gm and let GA G11 gtlt G1112 gtlt gtlt Gn7z1n C 5w For w E Gm denote by Aw the cycleshape of w7 expressed as a partition De nition 1 The Frobenius Characteristic is the map Ch I Czc6 A AC de ned on f 6 C465 by 1 7 Chf 5 Z fwpw we6n Equivalently7 lt gt ch f M 6 where 1 is the class function 6n A A de ned by 1 WW pAw Theorem 1 1 ch is a ring isomorphism 2 ch is an isometry ie it preserves inner products ltf79gt6n ltchf7chygtAl 3 ch restricts to an isomorphism CZZG A A2 4 1A gt gt pAZ 5 Inng XmV H hA lt6 Indg e e 7 The irreducible characters of Sn are the ch 1s 8 For all characters x we have chX XmV wchx llll prove a few of these assertionsi Recall that 2 lCAl TLlZ Therefore 1 Ch x a 2 PA IDA2A wECA which proves assertion It follows that Ch is at least a graded Cvector space isomorphism since 11 and pk21 are graded Cbases for CZG and A respectively To show assertion 2 it suf ces to check it on these basesi Let 1 M F n then 1 7 1 lt1A71ugt6n 5 Z 1Aw1uw glCAl SM SM2A7 wEG lt10 pigt ltLA Pugt 6A 29 le A Jaz 127 2H A Jaz M SAMZ Next we check that Ch is a ring homomorphism hence an isomorphism Let f E G g E Gk and n j k1 en chf y Indgfme y7 gt6 where 1 is as in ltf gResgX6k1Jgt6 W by Frobenius reciprocity 1 Z f 9ltw7 mam 1 101E67X6k 1 7 1 7 7 Z fw PM E 2 91 1012 wee xeGk chfchg1 More Fundamental Results 1 The Murnaghan Nakayama Rule We now know that the irreducible characters of 6 are X Ch 13 for 1 F n The Murnaghan Nakayama Rule gives a formula for the value of the character X on the conjugacy class OH in terms of m hook tableaux Here is an example of a rimhook tableau of shape 1 543 3 l and content 12 6332 11 1 1 1 4 4l 1 2 3 3 1 2 3 1 2 6 5 Note that the columns and row are weakly increasing and for each i the set Hi T of cells containing an i is contiguousi Theorem 2 Murnaghan Nakayama Rule 1937 n A 7 1ht H T x one 2 HH lt gt1 rimehook tableaux T i1 of shape A and content L For example the heights of H1 H5 in the rimhook tableau above are 4 3 2 1 1 1 There are an even number of even heights so this rimhook tableau contributes 1 to xACH An important special case is when M 11 1 ie since then X CH X 16 ie the dimension of the irreducible representation S of Sn indexed by A On the other hand a rimhook tableau of content M is just a standard tableau So the Murnaghan Nakayama Rule implies the following Corollary 3 dim S f This begs the question of how to calculate f which you may have been wondering anyway There is a beautiful formula in terms of hooks For each cell 1 in the Ferrers diagram of A let hz denote its hook length the number of cells due east of due south of or equal to I In the following example h z 6 Theorem 4 Hook Formula of Frame Robinson and Thrall 1954 Let A b n Then nl F 7 H 111 xeA Example 1 For A 5 433 1 b 16 as above here are the hook lengths 9 7 6 3 l l l 7 5 4 l l 5 3 2 4 2 l 1 Therefore 14 A 2288 f 97265242322214 Example 2 For A nn b 2n the hook lengths are n1n n71 2 top row nil n72 1 bottom row Therefore 1M 2nl 671 n1lnl n1 n which is the nth Catalan number as we already know Monday 4 14 Let G be a nite group All representations are nitedimensional and over C Here s the machinery we developed on Friday Character formulas We proved that 1 may 9 Xpy m y 2 Xpy Xpy 3 Mumy XpyXpy 4 momma y Xpy Xpyl An important missing piece is a formula for the character of Homg p p Fixed spaces We de ned the xed space of a representation G as VG v E V l 91 h V9 6 G and observed that Homg V W HomcV WGi The inner product For X41 6 CZG we de ned 1 7 ltx7 1 Zxg y gEG and proved the formulas l 39 C 7 5 dlmC V 7 ZXpg7 gEG 6 0977 XWgtG dimc HOmG 7 l Schur7s Lemma and the Orthogonality Relations What happens when p and p are irreducible representations Proposition 1 Schurls Lemma Let G be a group and let p V and p V be nitedimensional repre sentations of C over a eld lF l fp and p are irreducible then every Gequivariant 45 V A V is either zero or an isomorphism 2 If in addition lF is algebraically closed then g I10mGVVg lF Zf 7 p 0 otherwise Proof For 1 recall that kerqb and imqb are Ginvariant subspaces But since p rho are simple there are not many possibilities Either kerqb 0 and im 45 W when 45 is an isomorphismi Otherwise ker 45 V or imqb 0 either of which implies that 45 0 For 2 let 45 E Homg V i If p 2 p then 45 0 by l and we re done Otherwise we may as well assume that V V i Since lF is algebraically closed 45 has an eigenvalue A Then 45 7 AI is Gequivariant and singular hence zero by So 45 All We7ve just shown that the only G equivariant maps from V to itself are scalar multiplication by some A D Theorem 2 Let p V and p V be nitedimensional representations of C over C i fp and p are irreducible then ltX X gt 1 if P E 77 p G 0 otherwise ii If phi l l pin are distinct irreducible representations and n n P M ED EB m WW i T 1 I then n 09 szgtc mi ltXp7 XpgtG Em i1 In particular ltXp XpgtG 1 if and only ifp is irreducible iii If Xp Xp then p E p iv If phi l l n is a complete list of irreducible representations of G then n N d39 7 Preg 69 P mm 139 1 and consequently n Zltdimm2 101 i1 V The irreducible characters e characters of irreducible representations form an orthonormal basis for CZG In particular the number of irreducible characters equals the number of conjugacy classes of G Example 1 Find all the irreducible characters of 64 There are ve conjugacy classes in 64 corresponding to the cycleshapes 1111 211 22 31 and 4 The squares of their dimensions must add up to 164 24 The only list of ve positive integers with that property is 1 1 2 3 3 We start by writing down some characters that we knowi Cycle shape 1111 211 22 31 4 Size of conjugacy class 1 6 3 8 6 X1 Xtriv 1 1 1 1 1 X2 Xsign 1 1 1 1 1 Xdef 4 2 0 1 0 Xre 24 0 0 0 0 Of course va and Xsign are irreducible since they are 1dimensionali On the other hand Xdef can t be irreducible because 64 doesnlt have a 4dimensional irrepl lndeed ltXdef7 XdefgtG 2 which means that pdef must be a direct sum of two distinct irrepsi If it were the direct sum of two copies of the unique 2dimensional irrep then ltXdef Xdefgtc would be 4 not 2 by ii of Theorem 2 We calculate ltXdef7 XtrivgtG 17 ltXdef7 XsigngtG 0 Therefore X3 Xdef 7 va is an irreducible character The other 3dimensional irreducible character is X4 X3 8 Xsign we can check that X4 X4gtG 1i The other irreducible character X5 has dimension 2 We can calculate it from the regular character and the other four irreducibles7 because Xreg X1 X2 3X3 X4 2X5 So here is the complete character table of G4 Cycle shape 1111 211 22 31 4 Size of conjugacy class 1 6 3 8 6 X1 1 1 1 1 1 X2 1 71 1 1 71 X3 3 1 71 0 71 X4 3 71 71 0 1 X5 2 0 2 71 0 Now7 the proof of Theorem 2 Assertion follows from part 2 of Schur s Lemma together with Proposition 67 and ii follows because the inner product is bilinear on direct sumsi For iii7 Maschke s Lemma says that every complex representation p can be written as a direct sum of irreduciblesi Their multiplicities determine p up to isomorphism7 and can be recovered from Xp by assertion ii For iv7 recall that Xng 1g 1G1 and Xregg 0 for g f 19 Therefore 1 7 1 mg mg Zxregym9 lmHOG chm m gEG so pi appears in preg with multiplicity equal to its dimensioni That the irreducible characters are orthonormal hence linearly independent in CZG follows from Schur7s Lemma together with assertion The hard part is to show that they in fact span CZGi We will do this next time Wednesday 35 Regions of Hyperplane Arrangements Let A C Rquot be a real hyperplane arrangement The regions of A are the connected components of Rquot A R UHeA H Each component is the interior of a bounded or unbounded polyhedron in particular it is homeomorphic to R We write 7 A number of regions of A We d also like to count the number of bounded regions However we must be careful because if A is not essential then every region is unbounded Accordingly call a region relatively bounded if the corresponding region in essA is bounded and de ne MA number of relatively bounded regions of A Note that bA 0 if and only if essA is central Example 1 Let A1 and A2 be the 2dimensional arrangements shown on the left and right of the gure below respectively Then MAI 6 Wu 0 TltA2gt10 wig 2 Example 2 The Boolean arrangement Q7 consists of the n coordinate hyperplanes in R The complement R n is 951 957 l x y 0 for all 239 and the connected components are the open orthants speci ed by the signs of the n coordinates Therefore Mg 2 Example 3 Let A consist of m lines in R2 in general position that is no two lines are parallel and no three are coincident Draw the dual graph G the graph whose vertices are the regions of A with an edge between every two regions that share a common border A G Let 7 MA 1 of vertices of G b MA 5 of edges of G f of faces of G Then 1a 1 r m m27m2 lb f1f because each bounded region contains exactly one point where two lines of A meet and 1c 4f71 257r7b V because each unbounded face has four sides 161 Note that the number r 7 b of unbounded regions is just 2m Take a walk around a very large circle You will enter each unbounded region once and will cross each line twicei Therefore from 1c and 1b we obtain 1e em2f71 mQ Now Euler s formula for planar graphs says that v 7 e f 2 Substituting in 1a 1b and 1e and solving for r gives 7 m2 m 2 7 2 m273m2 7 71171 2 7 2 and therefore I r 7 2m Example 4 The braid arrangement Brn consists of the hyperplanes x1 xj in R The complement R Br consists of all vectors in R with no two coordinates equal and the connected components of this set are speci ed by the ordering of the set of coordinates as real numbers yx Therefore MB n Our next goal is to prove Zaslavsky s theorems that the numbers TA and bA can be obtained as simple evaluations of the characteristic polynomial of the intersection poset LA Deletion and Restriction Let A be a hyperplane arrangement If A is central then we know that LA is a geometric lattice I ll write MA for the corresponding matroid represented you will recall by the normal vectors 7 to the hyperplanes H E A i Let x E LAi Recall that this means that x is an af ne space formed by the intersection of some subset of A De ne arrangements AxH AlH2x AEWlWH x HeHAE Example 5 Let A be the 2dimensional arrangement shown on the left with the line H and point p as shown Then A17 and AH are shown on the right XX The reason for this notation is that LAx and LAx are isomorphic respectively to the principal order ideal and principal order lter generated by x in LAi 9M 9quot LA LA M H We say that A55 is the restriction of A to 95 Notice that rank A equals either rankA 7 1 or rank A according as H is or is not a coloop in the matroid of A since MA MA 7 Fly Proposition 1 Let A be a real arrangement and H E A Let A A and A AH Then 2 TM TM TM and 3 MA 7 bA MA if rankA rankA 7 0 if rankA rank A 1 Proof Consider what happens when we add H to A to obtain A Some regions of A will remain the same while others will be split into two regions The regions in the rst category each count once in both rA and rAi The regions in the second category each contribute 2 to rA but they also correspond bijectively to the regions of A This proves By the way if and only if H is a coloop then it borders every regionof A so rA 2rA in this case Now what about bounded regions If H is a coloop then A has no bounded regions 7 every region of A will contain a line so every region of A will contain a ray Otherwise the bounded regions of A come in three avors First the regions not bordered by H eg 1 below correspond bijectively to bounded regions of A through which H does not pass Second for each region R of A bordered by H the region R O H is bounded in A where R denotes the topological closure Moreover R comes from a bounded region in A if and only if walking from R across H gets you to a bounded region of A Yes in the case of the pair 2 and 3 which together contribute two to each side of 3 no in the case of 4 which contributes one to each side of D This looks a lot like a Tutte polynomial deletioncontraction recurrence However we only have a matroid to work with when LA is a geometric lattice that is when A is central otherwise LA is not even a bounded poset On the other hand LA is certainly ranked by codimension for every arrangement so we can work instead with its characteristic polynomial which as you recall is de ned as 4 MW XL 4k Z MOa kdim xeLA Proposition 2 DeletionRestriction Let A be a real arrangement and H E A Let A A and A AH Then 5 MW XAk XAk Proof coming next time Monday 428 Last time7 we saw broadly how to use triangularity arguments to show that e7 3A and pk are bases for the ring A of symmetric functions the rst two Z bases7 the second two Qbases Triangularity does not work for the basis ILA because the complete homogeneous symmetric functions have so many terms For example7 in degree 37 hg 1 1 1 7213 H 11 2 31 lei h111 1 3 6 mlll and it is not obvious that the basechange matrix has determinant 1 although it does We need a new tool to prove that ILA is a Z basisi De ne a ring endomorphism w z A A A by wei hi for all i7 so that we h This is wellde ned since the elementary symmetric functions are algebraically independent recall that A E Re17 e27 i i Proposition 1 f for all f E A In particular the map w is a ring automorphism Proof Recall the generating functions 1 Et Zektk H1tzn kgo n21 2 Ht thtk Hail kgo n21 Using the sum formulas in 1 and 2 gives 3 EtH7t Z Zektkhnkitn k 2t Zenwkekhwki ngt0 160 ngt0 160 On the other hand7 the product formulas in 1 and 2 say that EtH it 1i Equating coef cients of t gives 4 271 kekhnk 0 0m 21 160 Applying m we nd that 0 271 kwekw hnk 160 71 7khkwhnk Ms SH 0 71khnkwhk 160 n 1n Z1nikhnewhkgt 160 and comparing this last expression with 4 gives whk eki D Corollary 2 hA is a graded Zbasis for A Moreover AR 2 Rh1h2i i By the way the equation 4 can be used recursively to express the ekls as integer polynomials in the hkls and Vice versal A Bunch of Identities The Cauchy kernel is the formal power series 9 H 17 ziyjfll 13121 As welll see the Cauchy kernel can be expanded in many different ways in terms of symmetric functions in the variable sets and For a partition A b n let mi be the number of is in A and de ne 2A lm1m1l2m2m2l 5A ilm2m4quot 7 For example if A 332lll then 2A 133l211l322l 216 The notation comes from the fact that this is the size of the centralizer of a permutation a 6 6 with cycleshape A that is the group of permutations that commute with 0 Meanwhile 5A is just the sign of a permutation with cycleshape A Proposition 3 We have the identities 5 H 141ml thmmy EM 1321 A A 2A lt6 H Hm Zammmy 2am 13121 A A A where the sums run over all partitions A Proof For the rst identity in 5 H 1 MAI H Ha 7 mrl 121 1321 13921 y7 H 13921 kzo m lt7 H Emmy 121 1620 Zh m y A since the coef cient on the monomial ylflylgg in 7 is hmth For the second identity in 5 we need some more trickeryl Recall that an 42 43 l 1 1 i if 7 0g 4 was n q 2 3 Therefore log H l iziyjfl lOg H 1 Iiyj i 10g1 Iiyj 13121 23121 1121 In It 1 i Z In mzlnzl n21 mzl Z pnzpny n21 n and n exp ZMWW TL n21 n 21anltzgtmltygtgt 7 kl n kZO n21 LEG My 2W D A 2A The proofs of the identities in 6 are analogous and left to the reader Corollary 4 We have s hn 9 AH 2A 9 en 51 and A Min 10 wp SAP Proof For 8 we start with the identity of 5 z thmmy Z W W A A 2 Set yl t and yk 0 for all k gt 1 This kills all terms on the left side for which A has more than one part so we get WW 2 mm Z L An A 2A and extracting the coefficient of t gives Starting with 6 and doing the same thing yields As Brian pointed out you can t obtain 10 just by applying w to 8 and comparing with 9 as I had mistakenly claimed in class Here is a better reason In what follows w is going to act on the zils while leaving the yfs alonei Using 5 and 6 we obtain 2 Hikipmy Zh m y w ltZ AImkygt w Egkwp if yv A A A A A 2A and equating coefficients of p y2 as shown yields the desired result D The Hall Inner Product De nition 1 The Hall inner product lt on A is de ned by declaring hi and mm to be dual bases lthA7mMgt 6AM 0 Two bases ui vi are dual under the Hall inner product if and only if 1 7 Z um L121 1 7 W A 0 In particular l A b n is an orthonormal basis for AR so lt is an inner product 7 that is a 2 nondegenerate bilinear formi o The involution w is an isometry iiei lta 12gt ltwawbgti It sure would be nice to have an orthonormal basis for Ag In fact the Schur functions are such a thing The proof of this statement requires a marvelous combinatorial tool called the RSK correspondence for Robinson Schensted and Knuth Friday 12508 De nition A poset L is a lattice if every nite subset of ac y E L have a unique meet ac y and join ac yi That is acymaxzEL l 23mg achminzEL l 22xyi Note that eg ac y ac if and only if ac S y These operations are commutative and associative so for any nite M C L the meet M and join VM are wellde ned elements of L In particular every nite lattice is bounded with 0 L and 1 VL Proposition 1 Absorption laws LetL be a lattice and 9c y E L Then xVzy ac and xxy 9c Proof left to the reader Proposition 2 Let P be a poset that is a meetsemilattice ie every nonempty B Q P has a wellde ned meet AB and has a 1 Then P is a lattice ie every nite nonempty subset ofP has a wellde ned join Proof Let A Q P and let B b E P l b 2 a for all a E A Note that B y ll because 1 E El I claim that B is the unique least upper bound for At First we have B 2 a for all a E A by de nition of B and of meeti Second if ac 2 a for all a E A then ac E B and so ac 2 AB proving the claimi D De nition 1 Let L be a lattice A sublattice of L is a subposet L C L that a is a lattice and b inherits its meet and join operations from L That is for all ac y E we have xALyxLy and acVLyxLyi Example 1 The subspace lattice Let q be a prime power let qu be the eld of order q and let V F a vector space of dimension n over qu The subspace lattice LVq L q is the set of all vector subspaces of V ordered by inclusion We could replace qu with any old eld if you don t mind in nite posetsi The meet and join operations on L q are given by W W W O W and W W W W i We could construct analogous posets by ordering the normal subgroups of a group or the prime ideals of a ring or the submodules of a module by inclusion However these posets are not necessarily ranked while L q is ranked by dimension The simplest example is when 11 2 and n 2 so that V 0 0 0 1 l 0 l Of course V has one subspace of dimension 2 itself and one of dimension 0 the zero spacei Meanwhile it has three subspaces of dimension 1 each consists of the zero vector and one nonzero vectori Therefore L22 E M5i Note that L q is selfdual under the antiautomorphism W A Wt An antiautomorphism is an isomor phism P A P3 Example 2 Bruhat order and weak Bruhat order Let 37 be the set of permutations of ice the symmetric groupi Write elements of 37 as strings 7102 an of distinct digits eg 47182635 E 63 lmpose a partial order on 37 de ned by the following covering relations 1 a lt 7 if 7 can be obtained by swapping 71 with 7111 where 71 lt 7111 For example 4718E35 lt 4718 35 and 4 82635 gt 4 82635 2 a lt 7 if 7 can be obtained by swapping a with 7 wherez39 lt j and aj a 1 For example 47182635 lt 47183625 If we only use the rst kind of covering relation we obtain the weak Bruhat order 321 321 312 231 312 231 132 213 132 213 123 123 Bruhat order Weak Bruhat order The Bruhat order is not in general a lattice while the weak order is although this fact is nontrivial By the way we could replace 6 with any Coxeter group although that s a whole nother semester Both posets are graded and selfdual and have the same rank function namely the number of inversions W7 The rankgenerating function is a very nice polynomial called the qfactorial ij liltjand 71 gt01 n F641111q1qq21II117 H 11 Distributive Lattices De nition A lattice L is distributive if the following two equivalent conditions hold xszxyxz Vxy2 L xVyzxVyxz Vxy2 L 17111 1711 Proving that these conditions are equivalent is not too hard but is not trivial it s a homework problem 1 The Boolean algebra n is a distributive lattice because the settheoretic operations of union and intersection are distributive over each ot er 2 M5 and N5 are not distributive N5 M5 aVcbb xVy22 llbVllCll ac2yz0 In particular the partition lattice H7 is not distributive for n 2 3 recall that H3 E M5 3 Any sublattice of a distributive lattice is distributive In particular Young s lattice Y is distributive because it is locally a sublattice of 7 4 The set D7 of all positive integer divisors of a xed integer 71 ordered by divisibility is a distributive lattice proof for homework De nition Let P be a poset An order ideal of P is a set A Q P that is closed under going down ie if x E A and y S x then y E A The poset of all order ideals of P ordered by containment is denoted JPi The order ideal generated by 951 i i i 957 E P is the smallest order ideal containing them namely x1iiix gt yEP l nyl for somei By the way there is a natural bijection between JP and the set of antichains of P since the maximal elements of any order ideal A form an antichain that generates it abcd b d as ed a c P JP Proposition The operations A B A U B and A B A O B make JP into a distributive lattice partially ordered by set containment Sketch of proof All you have to do is check that A U B and A O B are in fact order ideals of P Then JP D is just a sublattice of the Boolean algebra on P Wednesday 423 Frobenius Reciprocity Let H C G be nite groups and let X be characters of G and H respectively The restricted character of 1 on H is 1 Resg Wh 00 and the induced character of X on G is 1 2 Indi y W Z Xva lykl k G E k lgkeH Theorem 1 Frobenius Reciprocity ltlnd x gtG ltX Resg Proof lt1nd X7 gtG 13 21ndgxy g gEG 1 G i Z xFlgwm bylt2gtgt kEGk 1ngH 7 T k 1 k GHHMEMEG g xltgt lt y k igk t 1 7 7 h h iiei khk l Gng xmw lt 79 gt 1 See Monday s notes for an application and there Will be more later Symmetric Functions De nition 1 Let R be a commutative ring typically Q or Z A symmetric function is a polynomial in Rzli i In that is invariant under permuting the variables For example if n 3 then up to scalar multiplication the only symmetric function of degree 1 in 111213 is 11 12 13 In degree 2 here are two I I I 7 11121113I2I Every other symmetric function that is homogeneous of degree 2 is a Rlinear combination of these two because the coef cients of I and 1112 determine the coef cients of all other monomialsi Note that the set of all degree2 symmetric functions forms a vector space ln degree 3 the following three polynomials form a basis for the space of symmetric functions 1 13 as 1 12 111 1 13 111 1313 121 111213r Each member of this basis is a sum of the monomials in a single orbit under the action of Ggr Accordingly we call them monomial symmetric functions and index each by the partition whose parts are the exponents of one of its monomialsr That is 1311712713 Ii 13 137 m21111213 1 12 111 1 13 111 1313 121 m11111z27 Is 111213 In general for A A1 r r r Ag we de ne A A A m 11rrr1n Z Iaila quot39xa 0102Clnl But unfortunately this is zero if E gt n So we need more variables In fact we will in general work with an in nite set of variables 1112 r r r De nition 2 Let A b n The monomial symmetric function m is the power series 7 A1 A2 A4 mki 1al1a2n1azr a1azCP That is m is the sum of all monomials whose exponents are the parts of Ar Another way to write this is m E 10 rearrangements 0 of A where 10 is shorthand for 1 11 2 r Here we are regarding A as a countably in nite sequence in which all but nitely many terms are Or We then de ne Ad Aggy degreed symmetric functions with coefflts in R AARA 0120 Each Ad is a nitedimensional vector space with basis mk l A b d dimc Ad pd the number of partitions of d and the dimension does not change even if we zero out all but d variables so for many purposes it is permissible and less intimidating to regard Ad as the space of degreed symmetric functions in d variablesr Moreover A is a graded ring In fact let 600 be the group whose members are the permutations of 1112 r r with only nitely many non xed points that is 600 j 6 711 Then A Rllzl7127 7ll6w This understandably bothers some people In practice we rarely have to worry about more than nitely many variables when carrying out calculations Where is all this going The punchline is that we are going to construct an isomorphism F AQ 69 CZQGn n20 called the Frobenius characten39stic Thus will allow us to translate symmetric function identities into statements about representations and characters of Gm and Vice versa Important Families of Symmetric Functions Throughout this section7 let A A1 2 A2 2 2 M b n 1 Monomial symmetric functions These we have just seen 2 Elementary symmetric functions For k E N we de ne ek E HIS E IiIIiZHIik mu1 SCN 5E5 0lti1lti2ltmltik Sk where there are k 1 s in the last expression In particular 60 1 We then de ne E 6 Z For example7 1111I2Is2 I I 2I1121113I2131114quot39 m22m117 21 11I213393911121113I2131114quot39 m213m1117 11111I2133 ms 3m216m1117 et cetera Observe that 3 Et 2 HQ in Ztkek 13921 kgo 3 Complete homogeneous symmetric functions For k E N we de ne hk to be the sum of all monomials of degree 16 hk H15 E zilziznzik E m mult ise ts SCN ses Dagny31 AHc s k We then de ne hA hA1quot39hw For example7 hm 611 and h21 h1h2 e177111 m2 e1611 62 6111 i 621 ms 2m21 3min The analogue of 4 for the homogeneous symmetric functions is 1 4 HtHmZtkhki 13921 1 kgo In many situations7 the elementary and homogeneous symmetric functions behave dually As we Will see7 the sets EA l A F d and hA l A F d are Z module bases for Adi Monday 324 The Big Face Lattice Let A A be the following two af ne line arrangements in R Are they isomorphic They have the same intersection poset and therefore the same characteristic polynomial which happens to be k2 7 5k 6 but nonisomorphic dual graphsonly the dual graph of A has a vertex of degree 4 Therefore weld like to have some notion of i Ulllulplll in of real l1 perplaue Al that quot quot 39 between these two De nition 1 Let A H1 i i i Hn C Rd be a hyperplane arrangement and let 1 i i i Zn be linear forms such that Hi E 6 Rd l 0 Let c chi i i cn where Ci 6 70 for each if Consider the system of equations and inequalities gt 0 ifci lt 0 ifci 7 0 if c 0 If the solution set of this system is nonempty it is called a face of A and c is called a covectori The set of all faces is denoted Example Let A 2 Let H1 and H2 be the z and yaxes respectively so that we may take 41 y y and 21 y If The members of yQA are as follows Name Set Covector Origin 0 0 00 Positive zaxis 1 0 z gt 0 0 Negative zaxis 1 0 z lt 0 70 Positive y axis 0y y gt 0 0 Negative y axis 0y y lt 0 07 1st quadrant zy z gt 0y gt 0 2nd quadrant zy z lt 0y gt 0 7 3rd quadrant zy z lt 0y lt 0 77 4th quadrant zy z gt 0y lt 0 7 The set yQA has a natural partial ordering given by F S F whenever F E F where the bar denotes closure in the usual topology on Rail Equivalently if 50 are the covectors of F F respectively then Ci 6 020 for every ii Proposition 1 The partially ordered set yQA U 0l is a ranked lattice called the big face lattice of A Note The adjective big modi es lattice not face For example the Hasse diagram of 232 is shown on the left of the gure belowi Since the Hasse diagram can be quite messy it is typically more useful to draw a picture of A in Which each face is labeled by its covector as on the rig ti l 0 7 H 7 7 0 0 0 0 70 0 0 W 00 00 quot 0 0 If F is a face of A With covector c then the af ne span of F of A is an intersection of hyperplanes in A namely those for Which Ci 0 Therefore we can recover the intersection poset LA from The coatoms of are the regions of Rd A The corresponding maximal covectors consist entirely of 7s an 77s With no 07s e can recover the dual graph of A from yA because two maximal covectors represent adjacent regions if and only if they differ in exactly one digiti Monday 421 Restricted and Induced Representations De nition 1 Let H C G be nite groups and let p G A GLV be a representation of G Then the restriction of p to H is a representation of G denoted Resf p Likewise the restriction of X Xp to H is a chartacter of H denoted by Resg Notice that restricting a representation does not change its character OTOH whether or not a representation is irreducible can change upon restriction Example 1 Let C denote the conjugacy class in 6 of permutations of cycleshape A Recall that G 63 has an irrep whose character 1 Xp is given by 1110111 27 W021 07 W03 1 Let H ng Q 63 This is an abelian group isomorphic to ZSZ so the twodimensional representation Resg p is not irreducible Speci cally let w e27 393 The table of irreducible characters of ng is as follows 1C 123 132 1 va 1 1 X1 1 w of X2 1 w2 w Now it is evident that ResgiJ 2 71 71 X1 X2 Note by the way that the conjugacy class C3 C 63 splits into two singleton conjugacy classes in ng a common phenomenon when working with restrictions Next we construct a representation of G from a representation of a subgroup H C G De nition 2 Let H C G be nite groups and let p H A GLW be a representation of H De ne the induced representation lnd p as follows 0 Choose a set of left coset representatives B 121 br for H in G That is every 9 E G can be expressed uniquely as g bjh for some bj E B and h E H Let HGH be the Cvector space with basis B Let V CGH c W 0 Let g E G act on bi Eu 6 V as follows Find the unique bi E B and h E H such that 912 bjh and put gbi w bj hw This makes more sense if we observe that g bjhb1 so that the equation becomes bjhbgl 12429 w b ca hw o Extend this to a representation of G on V by linearity Proposition 1 lnd Qz is a representation of G that is independent of the choice of B Moreover for all g E G 1 71 Xindgp9 W 2 M70 9k k G E k lgkeH Proof First we verify that lnd p is a representation Let gg E G and bi E w E V Then there is a unique bj E B and h E H such that 1 912 bjh and in turn there is a unique 1 E B and h E H such that 2 g bj bgh We need to verify that 3 9 9 bi w 9 9 bi w lndeed 9 g b ca w 912 hm m9 h hwi On the other hand by l and 2 gbi bjhb1 and g bzhbgl so g g bi w bghhb1 bi E w bg Him as desired Now that we know that lndg p is a representation of G on V we nd its character on an arbitrary element 9 6 Ci Regard lnd pg as a block matrix with 7 row and column blocks each of size dimW and corresponding to the subspace of V of vectors of the form bi w for some xed bin The block in position M is o a copy of ph if gbi bjh for some h E H 0 zero otherwise Therefore xlndgwgg tr 9 cmH W W a cmH c w Z Xph ism gbbh EheH Z Xpb1gbi ism bfyheH 1 m E Z Xpaz 1b lgbih iE7 heH 121 gbIEH 1 71 7 Z Xpltk 9k lHl keG 151 ngH Here we have put k bih which runs over all elements of G The character of lnd Qz is independent of D the choice of B therefore so is the representation itselfi Theorem 2 Frobenius Reciprocity Let H C G be nite groups Let X be a chammcter ofH and let 1 be a character of G hen lt1nd X7 gtG 06 R683 gtHA Example 2 Sometimes Frobenius reciprocity suf ces to calculate the isomorphism type of an induced representationi Let 1b X1 and X2 be as in Example 1 We would like to compute lndg XL By Frobenius reciprocity G G ltlndH X1 gtG ltX1 ResH 1 But 1 is irreducible Therefore it must be the case that lndg X1 1b and the corresponding representations are isomorphic The same is true if we replace X1 with Xgi Proof next time Friday 2108 Modular and Semimodular Lattices De nition 1 A lattice L is modular if for every x y z E L with x S 2 l xVy2xyz It is upper semimodular if for every x y E L 2 xylty gtxltxy Last time we showed that modular gt semimodular Lemma 1 Suppose L is semimodular and let x y 2 E L far lt y then either sz sz or 95 V2 lt sz Proof Let in as 2 Note that x S w 3 y Therefore either 11 x or w y o lfwythenx22y Soszyxzyz o lfwx then szyxlty Therefore szltxzyyz D Theorem 2 L is semimodular if and only if it is ranked with a rank function r satisfying 3 we v y m M s me my my e L Proof Suppose that L is a ranked lattice with rank function r satisfying If x y lt y then x y gt as otherwise as 2 y and x y On the other hand ry rx y 1 so by 3 T06 V y T06 S My N96 A y 1 which implies that in fact as y gt x The hard direction is showing that a semimodular lattice has such a rank function First observe that if L is semimodular t en 4 xyltxygtxyltxy Denote by CL the maximum length of a chain in L We will show that L is ranked by induction on CL Base case If CL 0 or CL 1 then this is trivial Inductive step Suppose that CL n 2 2 Assume by induction that every semimodular lattice with no chain of length CL has a rank function satisfying First we show that L is ranked LetO x0ltx1ltltxn1ltxn l beachainofmaximumlength Let0y0lty1ltltym1ltym l be any maximalT chain in L We wish to show that m n Let L 951 and L 31 By induction these sublattices are both ranked Moreover cL n 7 1 If an yl then we are done by induction since the interval L 951 is a lattice and cL n 7 1 On the other hand if x1 y yl then let 21 x1 yl By 4 21 covers both 951 and y1 Let 2122 1 be a maximal chain in L thus in L O L Remember that the length of a chain is the number of minimal relations in it which is one less than its cardinality as a subset of L So for example C n n not n lThe terms maximum and maximal are not synonymous Maximum means of greatest possible cardinality while 77 maximal means not contained in any other such object In general maximum is a stronger condition than maximal Since L is ranked and 2 gt 951 the chain 21 i i i T has length n7 2 So the chain y121u T has length n71 On the other handAL is ranked and y1y2 i i l is a maximal chain so it also has length n 7 1 Therefore the chain 0y1 i i 1 has length n as desired Second we show that the rank function r of L satis es Let x y E L and take a maximal chain as y c0 lt c1 lt lt 7171 lt cn 95 Note that n Mac 7 rx Then we have a chain ycoVySC1Vy SCnVyxVy By Lemma 1 each 3 in this chain is either an equality or a covering relation Therefore the distinct elements cl y form a maximal chain from y to x y whose length must be S n Hence rx y 7 ry S n Mac 7 rx y and so N96 V y N96 A y S n T06 My D The same argument shows that L is lower semimodular if and only if it is ranked with a rank function satisfying the reverse inequality of 3 Theorem 3 L is modular if and only if it is ranked with a rank function r satisfying 5 rltxVygtrltxAygt 7 rltxgtrltygt my e L Proof If L is modular then it is both upper and lower semimodular so the conclusion follows by Theorem 2 On the other hand suppose that L has rank function r satisfying Let x S 2 E L We already know that x y 2 S x y 2 On the other hand rx rx ryz7rxyz 7 me my rz 7 my v2 7 was A w z 2 me my m2 7 we v yv 2 7 we Ag 7rltzvygtiltzgt7rltwizgt TWVWM implying D Geometric Lattices Recall that a lattice is atomic if every element is the join of atoms De nition 2 A lattice is geometric if it is upper semimodular and atomic The term geometric comes from the following construction Let E be a nite set of nonzero vectors in a vector space V Let LE W0 E l W Q V is a vector subspace which is a poset under inclusion In fact LE is a geometric lattice homework problem lts atoms are the singleton sets l s E E and its rank function is 7 Z dimZgt where Z denotes the linear span of the vectors in l A closely related construction is the lattice La E W O E l W Q V is an af ne subspace An af ne subspace of V is a translate of a vector subspace for example a line or plane not necessarily containing the origin In fact any lattice of the form La E can be expressed in the form LE where E is a certain point set constructed from E homework problem However the rank of Z E La E is one more than the dimension of its af ne span making it more convenient to picture geometric lattices of ran Example 1 Let E be the point con guration on the left below Then La E is the lattice on the right which in this case is modular abcd 039 abc ad bd cd 0 a b c d o o o a b c Wednesday 42 Dilworthls Theorem and Graph Theory A chain cover of a poset P is a collection of chains whose union is P Theorem 1 Dilworth s Theorem In any nite poset the minimum size of a chain couer equals the maximum size of an antichain If we switch chain 7 and antichain the result remains true and becomes nearly trivial Proposition 2 Trivial Proposition In any nite poset the minimum size of an antichain couer equals the maximum size of an chain This is much easier to prove than Dilworth s Theorem Proof For the 2 direction if G is a chain and A is an antichain cover then no antichain in A can contain more than one element of C so A Z On the other hand let A at E P the longest chain headed by as has length i then is an antichain cover whowe cardinality equals the length of the longest chain in P B These theorems have graph theoretic consequences The chromatic number xG of a graph G is the smallest number k such that G has a proper h coloring The clique number wG is the largest size of a clique in G a set of pairwise adjacent vertices Since each vertex in a clique must be assigned a different color it follows that 1 MG 2 MG always however equality need not hold for instance for a cycle of odd length The graph G is called perfect if wH xH for every induced subgraph H Q G De nition 1 Let P be a nite poset lts comparability graph Gp to be the graph G with vertices P and edges myleyorrrZZl lt doesnlt matter whether or not we require the chains to be pairwise disjoint Equivalently G p is the underlying undirected graph othe transitive closure of the Hasse diagram of P The incomparability graph G p is the complement of G p that is x y are adjacent if and only if they are incomparable For example if P is the poset Whose Hasse diagram is shown on the left then Gp is P plus the edges f f d c a b c a d b e c e a P GP 5p A chain in P corresponds to a clique in G p and to a coclique in G p Lik vise an antichain in P corresponds to a coclique in G p and to a clique in G p Observe that a covering of the vertex set of a graph by cocliques is exactly the same thing as a proper coloring Therefore the Trivial Proposition and Dilvvorth s Theorem say respectively that Theorem 3 Comparability and incomparability graphs of posets are perfect Theorem 4 Perfect Graph Theorem LovasZ 1972 Let G be a nite graph Then G is perfect if and only if G is perfect Theorem 5 Strong Perfect Graph Theorem SeymourChudnovsky 2002 Let G be a nite graph Then G is perfect if and only if it has no obuious bad counterexamples ie induced subgraphs of the form C or G where r 2 5 is odd The GreeneKleitman Theorem There is a wonderful generalization of Dilvvorth s theorem due to C Greene and D Kleitman 1976 Theorem 6 Let P be a nite poset De ne two sequences ofpositiue integers A12g aa1a2am by A1Akmax01UU0k CZ QP chains u1 ak maxA1 U UAkz A Q P disjoint antichains Then 1 A and u are both partitions of P 239e weakly decreasing sequences whose sum is 2 A and u are conjugates 239e Mij A121 For example consider the following poset Then A 372272 and u 441 Dilworth s Theorem is now just the special case M E Wednesday 312 Modular Elements Let L be a lattice Recall that L is modular if it is ranked and its rank function r satis es 1 We ry rIVyrxM for every ac y E L This is not how we rst de ned modular lattices but we proved that it is an equivalent condition see notes from 130 and 21 De nition 1 An element x E L is a modular element if 1 holds for every y E L Thus L is modular if and only if every element of L is modular o The elements 0 and l are clearly modular in any lattice o If L is geometric then every atom or is modular lndeed for y E L if y 2 ac then y xVy and ac acy whileifyZacthenyAx0andyacgty o The coatoms of a geometric lattice however need not be modular Let L H recall that l ln has rank function r7r n E Let ac 12 34 y 13l24 E H4 Then rx ry 2 but rx y rl 3 and rx y r0 0 So or is not a modular element Proposition 1 The modular elements of l ln are exactly the partitions with at most one nonsingleton block Proof Suppose that 7r E l ln has one nonsingleton block B For 0 E H let XCEolC B YCEolC B Then wAaC BlCEXUili B 7roU CUY CEX WUlHWVUl lenlBl1lYl nilBHlH XlHll WHUL proving that 7r is a modular element For the converse let BC be nonsingleton blocks of 7r then let 0 have the two nonsingleton blocks ik jJ where ij E B and hi E C Then ro 2 and r7r o r0 0 but r7r o r7r 1 lt r7r ro E r7r 0 so 7r is not a modular element D The usefulness of a modular element is that if one exists we can factor the characteristic polynomial of L Theorem 2 Let L be a geometric lattice of rank n and let 2 E L be a modular element Then 2 MW X6zk39 Z MLOyknTTZTTy y yAz6 l ll skip the proof which uses calculation in the Mobius algebra see Stanley HA pp SW52 Corollary 3 Let L be a geometric lattice and let a E L be an atom Then mas k 71gt Z M xgtkrltLgtHltrgt 5c cZa We already knew that h E 1 had to be a factor of XLh because XL1 ExeL uLO ac 0 Still it s nice to see it another way Corollary 4 Let L be a geometric lattice and let 2 E L be a coatom that is a modular element Then XLW k 5X zk where e is the number of atoms a E L such that a i 2 Example 1 Corollary 4 provides another way of calculating the characteristic polynomial of H Let 2 be the coatom with blocks n7 l and n which is a modular element by Proposition 1 There are n E 1 atoms a i 2 namely the partitions whose nonsingleton block is i n for some i E n E 1 so we obtain XnnUr k 7 n 1Xn71k and by induction X11710 k lxk mmaf nirl Supersolvable Lattices Let L be a geometric lattice with atoms A Recall from 2 that if 2 is a modular element of L then the characteristic polynomial of L factors XLk X6zk39 Z MLanknirziry y yAz6 Of course we can always apply this for an atom 2 Corollary 3 But as we ve seen with H something even better happens if 2 is a coatom we can express XLh as the product of a linear form the bracketed sum with the characteristic polynomial of a smaller geometric lattice namely 0 If we are extremely lucky L will have a maximal chain of modular elements Oz0ltz1lt ltxn1ltxni In this case we can apply Corollary 4 successively with 2 95771 2 9572 2 951 to split the characteristic polynomial completely into linear factors XLW k 5n71X6xn1k k 57mm 5n72X6xn2k k emxk nal 39 39 k i 50 where e atoms a of 195144 a i 951 aEAlaSIz1 aile De nition 2 A geometric lattice L is supersolvable if it has a modular maximal chain that is a maximal chain 0 950 lt 951 lt lt 957 1 such that every x is a modular element A central hyperplane arrangement A is called supersolvable if LA is supersolvable 0 Any modular lattice is supersolvable because every maximal chain is modular 0 H7 is supersolvable because we can take or to be the partition whose unique nonsingleton block is i 1 Thus the braid arrangement Brn is supersolvable 0 Let G C4 a cycle with four vertices and four edges and let A Act Then LA is the lattice of ats of the matroid U34 iiei LF 4 W 3 with HF minlFl 3 This lattice is not supersolvable because no element at rank 2 is modular For example let x 12 and y 34 then Mac My 2 but Mac y 3 and Mac y 0 Theorem 5 Let G E be a simple graph Then AG is supersolvable if and only the vertices of G can be ordered v1 i i 1 such that for everyz39 gt 1 the set C vj ljgi vlvj E E forms a clique in G I ll omit the proof which is not too hard see Stanley pp 55757 An equivalent condition is that G is a Chordal graph if C Q G is a cycle of length 2 4 then some pair of vertices that are not adjacent in C are in fact adjacent in C By the way it is easy to see that if G satis es the condition of Theorem 5 then the chromatic polynomial xG k splits into linear factors Consider what happens when we color the vertices in order When we color vertex v1 it has lCll neighbors that have already been colored and they all have received different colors because they form a clique Therefore there are k 7 lCll possible colors available for v1 and we see that 71 MG 1 Has 7 la Friday 425 Symmetric Functions We continue our catalog of important symmetric functions We have already seen 1 the monomial sym metric functions A A A Iairai quot1117 m a1azClP 2 the elementary symmetric functions 5k g Ii11i2quot391ik7 5A5A1quot395A4 0lti1lti2ltlti k and 3 the complete homogeneous symmetric functions hk zilziznzik h h1hz 0lti1 i2 miik 4 Power sums These are de ned by PkrfII mk7 FA pA1quot39PAZ For example in degree 2 P2 77127 P11 11I2quot392m22m11 While p2p11 is a Qvector space basis for AQ it is not a Z module basis for A2 To put this in a more elementary way not every symmetric function with integer coef cients can be expressed as an integer combination of the powersums for example mu p11 7 p22 5 SChur functions The de nition of these power series is very different from the preceding ones and it looks quite weird at rst However the Schur functions turn out to be essential in the study of symmetric functions De nition 1 A columnstrict tableau T of shape A or ACST for short is a labeling of the boxes of a Ferrers diagram with integers not necessarily distinct that is o weakly increasing across every row and o strictly increasing down every column The partition A is called the shape of T and the set of all columnstrict tableaux of shape A is denoted CSTA The content of a CST is the sequence a 011012 where ai is the number of boxes labelled i and the weight of T is the monomial IT I zlz 2 For example here are two CST s and one tableau that is not an CST of shape A 32 l1l1l3l lllllll l1l2l3l 23 48 14 2 2 X1 X2 X3 Xi X4Xs Not a SST De nition 2 The Schur function corresponding to a partition A is 1 2 IT TECSTA It is far from obvious that 81 is symmetric but in fact it is We will prove this shortly Example 1 Suppose that A is the partition with one part so that the corresponding Ferrers diagram has a single row Each multiset of n positive integers with repeats allowed corresponds to exactly one CST in which the numbers occur left to right in increasing order Therefore 1 80 hn Em Abn At the other extreme suppose that A 11 1 is the partition with n singleton parts so that the corresponding Ferrers diagram has a single column To construct a CST of this shape we need n distinct labels which can be arbitrary Therefore 2 S111 5n m111 Let A 21 We will express 81 as a sum of monomial symmetric functions No tableau in CSTA can have three equal entries so the coef cient of mg is zero For weight zazbzc with a lt b lt 5 there are two possibilities shown below all H H Finally for every a f b E N there is one tableau of shape A and weight 1211 7 either the one on the left if a lt b or the one on the right if a gt 12 Proposition 1 51 is a symmetric function for all A Therefore the coef cient of mul is 1 Therefore 821 2771111 m21 Proof First observe that the number 3 CAva HT 6 CSTO l IT ID H depends only on the ordered sequence of nonzero exponents in a For instance for any A h 8 there are the same number of ACST s with weights zlzgz z and zlzgz z because there is an obvious bijection between them given by changing all 37s to 77s or vice versa To complete the proof that 81 is symmetric it suf ces to show that swapping the powers of adjacent variables does not change CAa That will imply that 81 is invariant under every adjacent transposition k k 1 and these transpositions generate the group 600 This is precisely the statement that s is a quasisymmet c function We will prove this by a bijection which is easiest to show by example Let A 9 74 32 We would like to show that there are the same number of A CST s with weights 2 3 2 3 3 4 7 3 7 4 3 TAT T TaTaTDrl and 1 a OTBr Let T be the following A CST 11123l5l6l6l6l 23456l7l7l 3456 466 LL Observe that the occurrences of 5 and of 6 each form snakes from southwest to northeasti 11123l5l6l6l6l 23456l7l7l 3456 466 LL To construct a new tableau in which the numbers of 57s and of 67s are switched we ignore all the columns containing both a 5 and a 6 and then group together all the other strings of 57s and 67s in the same rowi Then we swap the numbers of 57s and 67s in each of those contiguous blocksi This construction allows us to swap the exponents on 1k and zk1 for any h concluding the proof Theorem 2 For each n 2 1 the sets mAlAbn eAlAbn hAlAbn and sAlAbn are all Zhases for A 239e bases for AZ as afree Zmodule and pAlAbn is a Qhasz39s for A 239e a basis for AQW as a vector space Moreover e1e2 and h1h2 generate A as a polynomial algebra over R Sketch of proof It is more or less obvious that the m are a Z basis To show that the Schur functions are a Z basis we show that they can be obtained from m by a unitrz39ahgular change of basis Speci cally we write each Schur function as an integer linear combination of monomial symmetric functions as SA E KAHmH F A n and then show that the matrix XML is triangular with is on the main diagonal therefore it is invertible and its inverse has integer entries Note that by the de nition of Schur functions the coef cient XML is the number of columnstrict tableaux with shape A and content h these are the socalled Kostka numbers Of course to do this we have to specify an ordering on the partitions Rather than the lexicographic total order we have worked with before it turns out to be convenient to work with a partial order as fo lows De nition 3 Let A A1 A1 and h M1 hm be partitions of n We say that A dominates h written A E h if E S m and A1 2 M17 A1A2 2M1M27 A1mMZM1mMo Proposition 3 KM 1 for all A Moreover KM 0 unless A E h The proof of this fact is a homework problemi As a corollary the matrix of Kostka numbers is unitriangular for any total order such as the lexicographic order which re nes dominance A similar result holds for the elementary symmetric functions If we write EA ZBk mH M then the coef cients BAH have a nice combinatorial interpretation and it turns out that 1 if X BAM M 7 0 1f M EX where X denotes the conjugate or transpose of A The proof that the p form a Q basis is analogous although in this case the change of basis has non17s on the diagonal and so is not invertible over Z but it is invertible over The h s are different They have lots and lots of terms so the coef cients of the transition matrix are all nonzero and we can7t use triangularity to prove that they are a basis However we can do something else cleveri Friday 215 More Matroid Constructions 2 Direct sum Let E1 E2 be disjoint sets and let Q be a basis system for a matroid M1 on E1 The direct sum M1 EB M2 is the matroid on E1 U E2 with basis system BlUBQ l 31 E 1 B2 E 2 l ll omit the routine proof that this is a basis system If M1 M2 are linear matroids whose ground sets span vector spaces V1 V2 respectively then M1 EBMQ is the matroid you get by regarding the vectors as living in V1 EB V2 the linear relations have to come either from V1 or from V2 lf G1 G are graphs with disjoint vertex sets then MG1 EB MGg E MGl 02 where denotes the disjoint union Actually something more is true you can identify any vertex of 01 with any vertex of G and still get a graph whose associated graphic matroid is MG1EBMG2 such as G in the following gure G 32 G Corollary Every graphic matroid arises from a connected graph Direct sum is additive on rank functions for A1 Q E1 A2 Q E2 we have TMleaMz A1 U A2 TM1A1 TMz A2 The geometric lattice of a direct sum is a Cartesian product of posets LM1 EBMQ E LM1 gtlt LM2 subject to the order relations F1 F2 3 Ff F5 iii E S F in LMl for each i This is the operation you constructed in problem set 1 problem As you should expect from an operation called direct sum and as the last two equations illustrate pretty much all of the properties of M1 EB M2 can be deduced easily from those of its summands De nition 1 A matroid that cannot be written nontrivially as a direct sum of two smaller matroids is called connected or1 indecomposdble Proposition 1 Let G E be a loopless graph Then MG is indecomposdble if and only G is 2connected not only is it connected but it can t be disconnected by deleting a single vertex The only if77 direction is immediate the discussion above implies that M G 63 M H H where H ranges over all the blocks maximal 2connected subgraphs of G 3The rst term is standard but I prefer indecomposable to avoid potential confusion with the graphitheoretic meaning of connected We ll prove the other direction later Remark If G E H as graphs then clearly MG E The converse is not true if T is any tree or even forest on n vertices then every set of edges is acyclic so the independence complex is the Boolean algebra Q7 and for that matter so is the lattice of ats In light of Proposition 1 it is natural to suspect that every 2connected graph is determined up to isomor phism by its graphic matroid but even this is not true the 2connected graphs below are not isomorphic but have isomorphic matroids More on this later 3 Deletion and contraction De nition 2 Let M be a matroid on E with basis system Q and let 5 E E 1 If e is not a coloop then the deletion of e is the matroid M 7 e or M e on E 5 with bases BlB egB 2 If e is not a loop then the contraction of e is the matroid Me or M e on E 5 with bases BelB BEE Again the terms come from graph theory Deleting an edge of a graph means what you think it means while contracting an edge means to throw it away and to glue its endpoints together G G e Ge Notice that contracting can cause some edges to become parallel and can cause other edges namely those parallel to the edge you re contracting to become loops ln matroid language deleting an element from a simple matroid always yields a simple matroid but the same is not true for contraction How about the linear setting Let V be a vector space over a eld 1F let E C V be a set of vectors with linear matroid M and let 5 E E Then M 7 e is just the linear matroid on E 5 while Me is what you get by projecting E 5 onto the quotient space VlFe For example if e is the ith standard basis vector then erase the ith coordinate of every vector in E 5 Deletion and contraction are reversed by duality M7e EMVe and Me EMquot 7el Example If M is the uniform matroid Ukn then M 7 e Ukn 7 1 and Me Uk1n 7 1 for every ground set elernent el Many invariants of matroids can be expressed recursively in terms of deletion and contraction The following fact is immediate from De nition 2 Proposition 2 Let M be a matroid on ground set E and let bM denote the number of bases of M For every e E E we have bM 7 e ife is a loop bM bMe ife is a coloop bM 7 e bMe otherwise Example If M Ukn then bM and the recurrence of Proposition 2 is just the Pascal relation n 7 n 7 1 n k 7 k k 7 1 1 This observation is the tip of an iceberg called the Tutte polynomial of a rnatroidl Wednesday 213 Independent Sets Bases and Circuits Recall that a matroid independence system J is a family of subsets of E such that la EJ lb ifIE andIQ1thenIE 1c ifIJE and 1 lt Ml then there existst JIsuchthatIUxE and that a matroid basis system Q is a family of subsets of E such that for all B B E 2 ml lBl 2b for all e E B B there exists 5 E B B such that B e U 5 E 2c for all e E B B there exists 5 E B B such that B e U e E l Homework 2a and 2b ltgt 2a and 2c If G is a graph with edge set E and M MG is its graphic matroid then f A Q E l A is acyclic A Q E l A is a spanning forest of G If S is a set of vectors and M MS is the corresponding linear matroid then f A Q S l A is linearly independent A Q S l A is a basis for spanSl Proposition 1 Let E be a nite set 1 If f is an independence system on E then maximal elements of J is a basis system 2 I Q is a basis system then f 23 is an independence system BE 3 These constructions are mutual inue39rses Proof Exercise We already have seen that an independence system on E is equivalent to a matroid rank functionl So Proposition 1 asserts that a basis system provides the same structure on El Bases turn out to be especially convenient for describing the standard operations on matroids that we ll see soonl One last way of de ning a matroid there are many morel De nition 1 A matroid Circuit system 39 on E is a family of subsets of E such that for all C C E 39 3a C Q C and 3b for all e E C O C C U C e contains an element of 39 In a linear matroid the circuits are the minimal dependent sets of vectors Indeed if C C are such sets and e E C O then we can nd two expressions for e as nontrivial linear combinations of vectors in C and in C and equating these expressions and eliminating e shows that C U C e is dependent hence contains a circuit In a graph if two cycles C C meet in an edge e 95y then C e and C e are paths between as and y so concatenating them forms a closed path which must contain some cyclel Proposition 2 Let E be d nite set 1 If is an independence system on E then CglC eVC QC is a circuit system 2 If is a circuit system then I l C Q I VC E 39 is an independence system 3 These constructions dre mutudl inuerses So we have yet another equivalent way of de ning a matroid Operations on Matroids Some ways of constructing new matroids from old ones include duality direct sums and deletion and con traction But rst a couple of pieces of terminology De nition 2 Let M be a matroid and V a vector space over a eld F A set of vectors S C V represents M over F if the linear matroid MS associated with S is isomorphic to M A regular matroid is one that is representable over every eld For instance we will see that graphic matroids are regular For some matroids the choice of eld matters For example every uniform matroid is representable over every in nite eld but Ukn can be represented over qu if and only if h S q 7 1 so that there are enough nonzero vectors in F although this condition is not suf cient For example U2 4 is not representable over F2 Some matroids are not representable over any eld the smallest such has a ground set of size 9 De nition 3 Let M be a matroid with basis system Q The dual mdtroid Mquot or ML has basis system EB1B Note that 2a is clearly invariant under complementation and complementation swaps 2b and 2c Also it is clear that M M What does this mean in the linear setting Let S 11 27 C lF quot and let M We may as well assume that S spans lF quot That is r S n and the r X n matrix X with columns vz has full rank r Let Y be any n 7 r X n matrix with rowspaceY nullspaceX That is the rows of Y span the orthogonal complement of rowspaceX according to the standard inner product Then the columns of Y represent Mquot To see this rst note that rankY dim nullspaceX n 7 r and second check that a set of columns of Y spans its column space if and only if the complementary set of columns of X has full rank Example 1 Let S 11 v5 be the set of column vectors of the following matrix 1 X0 0 OHO 1 1 0 0mm 0 0 1 Notice that X has full rank it s in rowechelon form after all so it represents a matroid of rank 3 on 5 elements We could take Y to be the matrix 0 0 72 1 0 Y 7 1 1 71 0 0 Then Y has rank 21 Call its columns vi 1 1 1 vg then the pairs of columns that span its column space are viav viavZ v av v avZ v avZ Whose unstarred complements are precisely those triples of columns of X that span its column space In particular every basis of M contains v5 Which corresponds to the fact that no basis of Mquot contains 1 Example 2 Let G be a connected planar graph ie one that can be drawn in the plane With no crossing edges The planar dual is the graph 0 Whose vertices are the regions into Which G divides the plane With two vertices of Gquot joined by an edge 5 if the corresponding faces of G are separated by an edge e of G1 So 5 is drawn across 5 in the construction Some facts to check about planar duality o A C E is acyclic if and only if Equot Aquot is connected 0 A C E is connected if and only if Equot Aquot is acyclic1 o G is naturally isomorphic to G1 0 e is a loop bridge if and only if 5 is a bridge loop1 De nition 4 Let M be a matroid on E1 A loop is an element of E that does not belongs to any basis of M1 A coloop is an element of E that belongs to every basis of M1 In a linear matroid a loop is a copy of the zero vector While a coloop is a vector that is not in the span of all the other vectors1 Monday 12808 Birkhoff s Theorem De nition A lattice L is distributive if the following two equivalent conditions hold acyzxyxz Vacy2EL xVyzxVyxz Vacy2ELi Recall that an order ideal of P is a set I Q P such that if ac E I and y 3 ac then y E It The poset JP of all order ideals of P ordered by containment is a distributive latticei It is a sublattice of the Boolean algebra Q7 where n lPl and is itself ranked of rank n iiei n because it is possible to build a chain of order ideals by adding one element at a time abcd abs and b d N as cd 23 P JP De nition The ideal generated by 951 x1uix 7 yELlnyl for someii So eg a d a c cl in the lattice abovei De nition Let L be a lattice An element x E L is joinirreducible if it cannot be written as the join of two other elements That is if ac y 2 then either ac y or ac 2 e subposet not sublatticel of L consisting of all joinirreducible elements is denoted lrrLi Provided that L has no in nite descending chains every element of L can be written as the join of join irreducibles but not necessarily uniquely eigi M5 All atoms are joinirreducible but not all joinirreducible elements need be atomsi An extreme and slightly trivial example is a chain every element is joinirreducible but there is only one atomi As a less trivial example in the lattice below a b c cl are all joinirreducible although the only atoms are a an cl L rrL Theorem 1 Birkhoff 1933 Fundamental Theorem of Finite Distributive Lattices FTFDL Up to isomorphism the nite distributive lattices are exactly the lattices JP where P is a nite poset Moreover L E JlrrL for every lattice L and P E lrrJP for every poset P Lemma 2 Let L be a distributive lattice and let p E L be joinirreducible Suppose that p 3 a1 an Then p 3 al for some i Proof By distributivity we have ppa1Va pa1pan and since p is joinirreducible it must equal p al for some i whence p 3 a D Analogue If a prime p divides a product of positive numbers then it divides at least one of them This is in fact exactly what Lemma 2 says when applied to the divisor lattice Proposition 3 Let L be a distributive lattice Then every ac E L can be written uniquely as an irredundant join ofjoinirreducible elements Proof We have observed above that any element in a nite lattice can be written as an irredundant join of joinirreducibles so we have only to prove uniqueness So suppose that we have two irredundant decompo sitions 1 xp1VVpnq1Vqu with p qj E lrrL for all ij By Lemma 1 pl 3 qj for some j Again by Lemma 1 qj S p for some i lfi y 1 then pl 3 p which contradicts the fact that the p form an antichain Therefore p1 qj Replacing p1 with any joinirreducible appearing in 1 and repeating this argument we nd that the two decompositions must be identical D Sketch of proof of Birkho us Theorem The lattice isomorphism L A JlrrL is given by 96 P l P E Mall 10 S Il Meanwhile the joinirreducible order ideals in P are just the principal order ideals ie those generated by a single element So the poset isomorphism P A lrrJP is given by My ltygt These facts need to be checked as a homework problem Corollary 4 Every distributive lattice is isomorphic to a sublattice of a Boolean algebra whose atoms are the joinirreducibles in L Corollary 5 Let L be a nite distributive lattice TFAE 1 L is a Boolean algebra 2 lrrL is an antichain 3 L is atomic e every element in L is the join of atoms 4 Every joinirreducible element is an atom 5 L is complemented That is for each ac E L there exists y E L such that ac y 1 and ac y 6 L is relatively complemented That is whenever ac S y S 2 in L there exists u E L such that qu2 andyu Proof 6 gt 5 Trivial 5 gt 4 Suppose that L is complemented and suppose that 2 E L is a joinirreducible that is not an atom Let ac be an atom in 0 z and let y be the complement of ac Then ach21zz aczyzacyz by distributivity Since 2 is joinirreducible we must have y 2 z ie y 2 2 But then y gt ac and y ac ac y 0 a contradiction 4 ltgt 3 Trivial 4 gt 2 Atoms are Clearly incomparable 2 gt 1 By FTFDL since L JlrrLi 1 gt 6 leQYQZaresetsthenletUXUYZi ThenY UXandYUUZi D 0 We could dualize all of this shoW that every element in a distributive lattice can be expressed uniquely as the meet of meetirreducible elements This might be a roundabout way to shoW that distributiVity is a selfdual conditioni Friday 229 More on the Characteristic Polynomial De nition 1 Let P be a nite graded poset with rank function r and suppose that n The characteristic polynomial of P is de ned as XPx 2M0 ZWHWL zEP Theorem 1 Let L be a geometric lattice with atoms E Let M be the corresponding matroid on E and r its rank function Then XLx 1 MgtTM1xa0 This was proved last time Example 1 Let G be a simple graph with n vertices and c components so that its graphic matroid MG has rank n E c Let L be the geometric lattice corresponding to M The ats of L are the vertex nanced subgraphs of G the subgraphs H such that if e my E EG and x y are in the same component of H then e E We have seen before that the chromatic polynomial of G is xGh 71 75 he TG 17 h0 Combining this with Theorem 1 we see that XGk chUI k so there is not too much inconsistency between these two uses of the symbol x The characteristic polynomial is particularly important in studying hyperplane arrangements coming soon Mobius Functions of Lattices Theorem 2 The Mo39bius function of a geometric lattice alternates in sign Proof Let L be a geometric lattice with atoms E Let M be the corresponding matroid on E and r its rank function Substituting 95 0 in the de nition of the characteristic polynomial and in the formula of Theorem 1 gives ML XL 0 1TMTM10 But TM 1 0 2 0 for every matroid M because TM x y E Nb Meanwhile every interval 0 2 C L is a geometric lattice so the sign of ii 2 is the same as that of 71 2 or zero D In fact more is true the Mobius function of any semimodular not necessarily atomic lattice alternates in sign This can be proven algebraically using tools we re about to develop Stanley Prop 3101 or combinatorially by intepreting 71TMML as enumerating Rlabellings of L see Stanley 3127313 It is easier to compute the Mobius function of a lattice than of an arbitrary poset The main technical tool is the following ring De nition 2 Let L be a lattice The Mobius algebra AL is the vector space of formal Clinear combinations of elements of L with multiplication given by the meet operation So 1 is the multiplicative unit of AL For example if L Q7 then AL Chm 7 x1 x3 7 In general the elements of L form a vector space basis of AL consisting of idempotents since as x x for all x E L It looks like AL could have a complicated structure but actually Proposition 3 AL E ClLl as rings Proof This is just an application of Mobius inversion For as E L de ne Ex ZMy y 3431 By Mobius inversion 1 95 Egg 3431 For as E L let CE be a copy of C with unit 11 so we can identify ClLl with HEB CE De ne a Clinear map lt1 AL A ClLl by Ex gt 11 This is a vector space isomorphism and by 1 we have gtx gty 5 5 1 1 21 4mg 1135 23y 1135 23y vaAy so in fact lt1 is a ring isomorphism The reason the Mobius algebra is useful is that it lets us compute Mx y more easily by summing over a cleverly chosen subset of 9531 rather than the entire interva Proposition 4 Let L be a nite lattice with at least two elements Then for every 1 E L we have 2 Mx 0 ccAa6 Proof On the one hand 151 Eeb 510 by 151 a Mx 2 Mac a xEL Now take the coefficient of D On the other hand A corollary of Proposition 4 is the useful formula 2 ML Mali 7 2 MIX 6 Example 2 Let a E 1 E H Then the partitions as that show up in the sum of are the atoms whose nonsingleton block is i n for some i E n E 1 For each such as the interval 95 1 C H7 is isomorphic to Hn1 so 2 gives MIL 7w IMHH from which it follows by induction that MltHgtlt71gt 1ltn 7 1 Wasn t that easy Example 3 Let L L q and let A v1 i i i v E F l v 0 This is a codirnensionl subspace in F2 hence a coatom in Li H X is a nonzero subspace such that X A 0 then X must be a line spanned by some vector 951 i i i 9 With yon y 0 We may as well assume yon l and choose an i i i 95771 arbitrarily so there are 117quot1 such linesi Moreover the interval X C L is isomorphic to L 1qi Therefore Ln4 qquot 1MLn7111 and by induction Mm 47516

×

×

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

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Janice Dongeun University of Washington

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

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

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.