### Create a StudySoup account

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

Already have a StudySoup account? Login here

# TpPrin Stochastic Modeling MATH 5490

UW

GPA 3.63

### View Full Document

## 31

## 0

## Popular in Course

## Popular in Mathematics (M)

This 4 page Class Notes was uploaded by Myrtice Robel on Tuesday October 27, 2015. The Class Notes belongs to MATH 5490 at University of Wyoming taught by Staff in Fall. Since its upload, it has received 31 views. For similar materials see /class/230313/math-5490-university-of-wyoming in Mathematics (M) at University of Wyoming.

## Reviews for TpPrin Stochastic Modeling

### 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: 10/27/15

UNIVERSITy Math 54905590 Spring 2003 M Department of 0 WYOMING Mathematics Information Theory E m Coding Theory and Cryptology Notes on Tutte Polynomials Eric Moorhouse UW revised 20 Feb 2003 Introduction These notes provide a very brief introduction to Tutte polynomials of matroids a notion which generalises that of the Tutte polynomial of a graph which specialises to the chro matic polynomial and which specialises to the weight enumerator of a code Our goal is to obtain the MacWilliams relations for linear codes by purely combinatorial means ie without character theory of abelian groups as traditional proofs have done since the orig inal 1962 proof This talk is intended as a supplement to my MATH 54905590 course where the MacWilliams relations will not be proven in class and intended primarily for the mathematics graduate students in that class Matroid theory was invented by Whitney 1935 as an abstraction of a matrix The earliest work on matroids was motivated by linear algebra with some inspiration supplied by graph theory The connections with graph theory were strengthened by later papers of Rado 1957 and Tutte 1958 1959 References PJ Cameron Codes matroids and trellises preprint http wwwmaths gmw ac ukquotpj CpreprintsCmt ps DJA Welsh Matroids Fundamental Concepts in Handbook of Combinatorics Vol I ed RL Graham et al Elsevier Amsterdam 1995 pp4817526 Matroids A matmid is a pair M X j where X is a nite set and j is a nonempty collection of subsets of X such that M1 whenever A Q B E 3 we have A E j and M2 exchange condition if A B E j and 1A1 g 1B1 then 3b 6 B such that A U b E 3 Members of j are called independent sets A basis is a maximal independent set Any two bases have the same cardinality called the mnk of M denoted by pX More generally for any subset A Q X the mnk of A is de ned by PltAgt we IgsalB Al IgA Where B is the collection of all bases of M Note that M induces a matroid structure of rank pA on each subset A Q M having I A I E 339 as its collection of independent sets The dual of M is the matroid M XfJ39 Whose bases are the complements of the bases of M thus the collection of bases of Mquot is B X B B E 3 Equivalently if we define a spanning set of M as any subset of X containing a basis then 3 is the set of complements of spanning sets of M The rank function p of Mquot is given by p A giezgkX 39 B Al maxlAl 7 B Al BEE gigg Al 7 131 13 o X Agtl 1117 900 9X39 A Uniform Matroids For 0 S k S n the uniform matroid Umk X 339 has n and 339 consists of all subsets I Q X of size at most k lts dual is clearly the uniform matroid UWWLk Linear Matroids Let N be a k gtlt n matrix over a field F and let X 1 2 n Let 339 be the collection of subsets I Q X such that the corresponding columns of A are linearly independent Then XfJ39 is a matroid Whose rank function pA is the dimension of the subspace of F spanned by the columns of A indexed by A Q X Note that N may have repeated columns so X is viewed as a multiset of vectors in Fl Graphical Matroids Let X be the set of all edges of a finite graph P and let 339 be the collection of all subsets of the edges of P Which do not contain any circuit Then M X 339 is a matroid and any such matroid is called graphical It is not hard to see that every graphical matroid is linear Tutte showed 1959 that graphical matroids are characterized by a short list of excluded minors compare With Kuratowski7s characterisation 1930 of planar graphs Loops and Coloops A loop in a matroid M X 339 is an element 6 E X such that e is dependent Note that loops have rank 0 and all other elements of X have rank 1 Loops in graphical matroids are loops in the usual graphical sense loops in linear matroids correspond to zero vectors 2 A coloop in a matroid M XfJ39 is an element e E X which belongs to every base of M equivalently e is a loop of the dual matroid A coloop in a graphical matroid is an edge not contained in any circuit a coloop in the linear matroid of a matrix N is a column of N which is not a linear combination of any of the other columns New Matroids from Old lf M1 X13391 and M2 X252 are matroids on disjoint elements ie X1 Xg g then we define the direct sum M1 M2 X1UX2 339 where 339 I1UI2 IZ E 31 it is not hard to see that this is a matroid This operation corresponds to forming the direct sum of two matrices or the direct sum of two graphs P1 69 P2 is formed from vertex disjoint copies of P1 and P2 with no edges between P1 and P2 If M X 339 is a matroid then M induces a matroid structure on each of its subsets A Q X defined by MlA A3lA where SM is the set of all I E 339 such that I Q A This is clearly a matroid it is denoted by MlA M restricted to A or M 39 A M delete A where A X 39A This operation amounts to in the case of linear matroids forming the submatriX of a matrix with a specified set A of columns or in the case of graphical matroids forming a subgraph by deleting all edges of the complementary subset A of edges If M XfJ39 is a matroid and A Q X then we may contract M by the subset A to obtain the contracted matroid MA A3A where A X A and IA is the set of all I Q A such that IU J E 339 for some and hence any basis J of MlA Equivalently the rank function of MA is given by pAB pAUB 7 pA for all B Q A This corresponds in the case of linear matroids to forming the quotient space of the column space of N by the subspace spanned by the columns corresponding to A It corresponds in the case of graphical matroids to the contraction of a graph P by a specified set of edges One also denotes MA M A the contraction of M to the complementary subset A X A The operations of deletion and contraction are dual in the sense that MAMA ie MlAMA I utte Polynomials The Tutte polynomial of the matroid M X 339 may be de ned directly by X 7 A A 7 A TM TMy Z a 71P P y 711 1M AgX The reason for using at 7 1 and y 7 1 here rather than simply an and y which would replace this by the closely related Whitney rank generating polynomial is to obtain the simplest possible expressions for a singleton X e in this case TM x or y according as pe 0 or 1 a loop or a coloop There is simple relationship between the Tutte polynomials of M and of its dual Mquot as we nd by a direct term by term comparison WWW 7 Z 6 71pltXgt7pltAgty 711A17ww AgX Z x 1 X11A17pltXAgty 71pltXgt7pltXAgt AgX Z 6 111317PltBgty 71pltXgt7pltBgt BgX TMyx The Tutte polynomial TM TM at y may also be de ned recursively by the processes of deletion and contraction using the rules TM1 69 M2 TM1TM2 TM TltM e TMe whenever e E X is neither a loop nor a coloop More generally we have TM ac 7 19X 9X 5TM e y 7 11 peTMe for all e E X although this gen eral reduction rule is not required for recursive determination of M This is because any matroid consisting of 7 loops and s coloops and no other elements necessarily has the form M6 M15 M0 BEBM0 e M1 M1 7 times 5 times where M0 and M1 are a loop and coloop respectively

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

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

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