### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for MATH 796 at KU 9

### View Full Document

## 17

## 0

## 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

### 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

### 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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

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

#### "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."

### 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.