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

### View Full Document

## 26

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

## Reviews for Class Note for MATH 796 at KU 2

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

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

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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