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

### View Full Document

## 24

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

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

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

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

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

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

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I 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!"

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