Class Note for MATH 796 at KU 2
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 26 views.
Reviews for Class Note for MATH 796 at KU 2
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
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 If g is a basis system then f UBEQ2B is an independence system 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 C 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 F2 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 EBlB 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 Or O Or H CNN 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