### 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 263 at GW

### View Full Document

## 23

## 0

## Popular in Course

## Popular in Department

This 8 page Class Notes was uploaded by an elite notetaker on Saturday February 7, 2015. The Class Notes belongs to a course at George Washington University taught by a professor in Fall. Since its upload, it has received 23 views.

## Reviews for Class Note for MATH 263 at GW

### 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/07/15

Mathematics 263 Matroid Theory Notes September 5 2006 Matroid Theory was originally developed by Hassler Whitney The paper he wrote was called On the Abstract Properties of Linear Dependence77 published in the American Journal of Mathematics 571935 509 533 Motivating Example Let S be a nite set of vectors in a vector space V over a eld F Let U be a set of subsets of S that are linearly independent By convention capital roman font 1 B for sets Script caps J B for sets of sets Property of J 11 ll 6 J l2ifIEJandJCIthenJEJ l3 if J E J and 1 lt lJl then there is an E Jilsuch that JU E 3 l1 and I2 are called the Simplicial complex l3 is called the augmentation property To show a matrix whose columns are vectors from a vector space of a eld can represent a matroid we see that H and l2 are obvious Now to show l3 take any independent set in Span1 has at most 1 elements so not all elements of J are in Span1 any m in Jispan has the property that I U is linearly independent Let G be a graph G V E V the set of vertices E set of edges allow multiple edge and loops Let U be the set of sets of edges that do not contain closed paths Example m lt c gt ble 3 contains the empty set all singletons all pairs all triples except 1 b c and 0 16 H obvious l2 obvious l3 Proof to follow Background sets of edges that do not contain closed walks look like Fact A forest on n vertices with c components has n 7 c edges Now we will do the proof of IS Proof Let 7 E U with c1 and CJ components and let 1 n 7 c1 lt lJl n 7 CJ Thus CJ lt 01 If follows that not every edge of J connects two vertices in the same component of I So an edge a E J that joins in di erent components of I can be added without creating a closed path D De nition 1 A set system is a multiset of subsets of a nite set S Example 1 S 1273475 multiset is 1727 17273757274 De nition 2 A transversal of a set system 14171427 At is a set of elements b1L7 27 7 bt b1 6 Ahbg 6 A27 7bt 6 At An example of a transversal of the multiset from Example 1 is 17 27 57 4 Set systems dont have to have transversals Example 2 17 27 1727 17 2 has no transversals Partial transversals of a set system are the transversals of subsystems The partial transversals of a set system satisfy l1 and IS De nition 3 A Matroid is a nite set S together with a collection 3 of subsets ofS such that U 12 and 13 hold The sets in J are called independence sets So far we have seen vector matroids7 graph matroids7 and transversal matroids Example 3 Um with 0 S r S n and S is an n7seta set with n elements 3 consists of all subsets ofS with at most r elements This is know as a uniform matroid The special case Um is a free matroid in n elements 3 23the set of all subsets ofS Example 4 Let A be a matrix over F Let S be a set that indexes the columns Let the subset I of S be independent if the columns are distinct and linearly independent This gives a matroid in S Such matroids are representable over F De nition 4 Representable A Matroid M is representable over F if there is a vector space V over F and a map Lp S a V such that is independent in M ltgt leSl 8 and LpS is linearly independent Questions Which matroids are representable over a eld Conjecture 1 For a nite eld there are a nite number of minimal obstructions to representability over the eld Example 5 F GF3 Z3 Column 1 is a loop Column 234 are parallel Column 56 are parallel Some independent sets are 2257 Some dependent sets are 1237 567 De nition 5 Loop A loop in a matroid M is an element a with 3 De nition 6 Parallel Element a and b are parallel if neither are a loop but a7b 3 Example 6 Um has loops if and only ifr 0 0000 UOA Example 7 Um has parallel elements i r 1 11111 U15 De nition 7 A simple Matroid aka combinatorial geometry is a matroid that has no loops and no parallel elements De nition 8 Minimal Dependent Set A minimal dependent set is a set that if you remove any element would become an independent set De nition 9 Cycle A minimal dependent set in an arbitrary matroid M will be called a circuit of M and we shall denote the set of circuits ofM by C or September 7 2006 De nition 10 Restriction Matriod One way to get more matroids from a given matroid M on S let X Q S de ne sIX 11 6 37 Q X X with 3X satisfying 1 This de nes the restriction M X or equivalently the deletion M S 7 X De nition 11 Simpli cation of a Matriod The simpli cation of a Matriod M sometimes denoted siM or M is obtained from M by deleting all loops and all but one element from each set of parallel elements giues M giues siM De nition 12 Bases of a Matriod A bases of a matroid are the maximalwith respect to Q independent set Theorem 1 All bases have the same size Proof Let B17 B2 be in the set B of bases If B lt B27 then we could augment B1 With some element of B2 7 B17 contrary to B1 being maximal Example 8 Um S is an niset 3 consists of all subsets that contain at most r elements The bases are all the resubsets of S Note We can recover J from B J 1 There is a B E B with I Q B B determines M Which collections B are the collections of bases of a matroid Theorem 2 B is the collection of bases of a matroid on S if and only if B1 B a 0 32 No member ofB is contained in another B3 IfB1 and B2 6 B and 6 B1 7 B2 then there is a y 6 B2 7 B1 so that B1 7 Uy E B Note B3 is known as the Bases Exchange Proof B1 and B2 obvious B3 for 6 B1 7 B27 we have B1 7 7 B1 6 J7 and 31 7 ml lt lB2l7 apply l37 y 6 B2 7 B1 7 With B1 7 U y E J and since it has the right size it is in B D Theorem 3 B3 is equivalent to 33 known as the symmetric basis exchange axiom For B17B2 E B andd E B17B2 there is ay 6 B2 7B1 so that B17Uy EB and B2 7 y U 6 B De nition 13 Syzygy It is an identity involving determinants determinants in terms of columns A 1727 and detA 17x2 Syzygy is TL 1J27 7nlly17y27 7ynl Z illaim m7nlly177yi71717yi17 7ynl 2 1 Note If y17y27 7yn I7 then this is just the cofactor expansion to nd a determinant Theorem 4 We can replace B3 by 33 Middle Bases Axiom IfX Q Y Q S and there are B17B2 E B with X C B1 and B2 Q Y then there is a B3 6 B with X Q B3 Q Y De nition 14 The dependent sets are the sets that are not independent Note Supersets of dependent sets are dependent The dependent sets are completely determined by the minimal dependent sets De nition 15 Mininal Dependent Sets The circuits of a matroid are the minimal dependent sets Which collections C are the collection of circuits of a matroid Theorem 5 C is the collection of circuits of a matroid in S if and only if C1 6 C C2 no set in C properly contains another C3 if 01702 E C and a 6 C1 0 Cg then C1 U Cg 7 a contains a member of G GS is known as circuit elimination We can give a better approach to cyclic matroids graphic matroids via circuits Circuits in a graph satisfy Cl7 C27 and CS Take two circuits 01702 in a graph sharing the edge a Go around C1 in an direction and pick some vertex that C1 and Cg share for which they don7t share the next edge call this vertex it Let i be the next vertex in common Cg has two it to 1 paths and the part of C1 from u tot 1 gives the circuit in C1 U Cg 7 a Circuits are generally a very e icient way to describe a matroid Vb eAf a CgtHHlt g l hv This graph as 2 circuits7 a7b7c and 1767 g It also have 12 bases vb 8Afgt a gt o d o lt lc hvg This graph gives the same matroid as the previous graph Graph connectivity means nothing for matroidshigher connectivity does September 12 2006 Supersets of bases are spanning sets Dependent sets form a lter any superset of a set in the dependent sets are a dependent set Hyperplanes maximal nonspanning sets Counterpart of dimension De nition 16 For a matroid M on S with a set of independent sets 3 the rank rX of a subset ofX of S is rX IQXJE 3 Example 9 In UM TX S7quot r otherwis e Note that I is independent if and only ifrI M is completely determined by r Theorem 6 Rank Function A function f 2S 7 Z is the rank function of a matroid S if and only if R1 TM 0 R2 ifX C Y then rX S rY R3 rX rY 2 rXUY rXmYVXY R3 is known as local semimodularity The following is the counterpart of subspace or span De nition 17 M is clX alrX U rX Example 10 For matroids given by a sets S of vectors clX spanX f S Example 11 In UN 7 X le lt r CKX T S otherwise Theorem 7 I is independendt if and only if Va 6 1 clI 7 Theorem 8 If is independent then f0T E Ir 7 l 7 pl l1l71lt lll rI so clI 7 Converse to come later cl determines M since it determines 3 Theorem 9 cl 2S 7 23 is the closure operator of a matroid M on S if and only if ch VX7X C clX cl For X Q Y clX C clY cl3 clclX clX cl4 if E clX Uy 7 clX then y E clX U cl4 is Steinitz Maclane exchange axoim lnterpret for a matroid M on a set S of vectors 6 clX U y 7 clX means 041v1oavt y7vi 6X753 0 so y E clXU De nition 18 The closed sets or flat of a matroid is a set X with X clX ie flats are the images of cl Flats of rank 1 are called points Flats of rank 2 are called lines Flats of rank 5 are called planes Flats of rank rM 7 1 are called hyperplanes Note MM MS The rnatroid on GF23 Z23 s 00007011001170107170717171171 GHQ 070707 07070 is a loop For a single element a 00707 ex 17170 the elm 7 07070 cl07170717170 0170110717000700 A picture of all these ats This is a Fanoplane7 F77 PG27 2 The rst 2 stands for 2 dimensional geometry7 and the second 2 stands for GF2 Let V be a 3 dimensional vector space over F eld The rnatroid on V has GHQ 07 points are 1 dirnensional subspace lines are 2 dirnensional subspace The plance V gives PG27 ln PG27 F7 any two distinct lines intersect Look at lines u7w dimu dimw dimu w dimu f w 2 2 3 1 PG27 3

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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on 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."

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