Class Note for MATH 796 at KU 9
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 17 views.
Reviews for Class Note for MATH 796 at KU 9
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
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 W 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 W 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 EVA 1 e
Are you sure you want to buy this material for
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'