Class Note for MATH 796 at KU 3
Popular in Course
Popular in Department
This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 24 views.
Reviews for Class Note for MATH 796 at KU 3
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
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 B1UB2lBl 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 lt31 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 mm 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