Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am working through Oxley's Matroid Theory book. An exercise in the first section asks for representations of the cycle matroid of $(K_{5}\setminus\text{ two non-adjacent edges})$ over $GF[2]$ and over $GF[3]$. I could easily get at an answer for the former, but can't get an answer for the latter even after spending a few hours playing with it. I do not think that this question (which is unstarred) could be so very complicated. What could I be missing?

share|improve this question
add comment

1 Answer

up vote 0 down vote accepted

Assign arbitrary directions to the edges and construct the incidence matrix corresponding to this directed graph (with entries $0$, $1$ and $-1$). You can show that for any graph, this gives a representation of its cycle matroid, over any field (just replace $-1$ by the corresponding element in the field. For example, in $GF[3]$, you just replace $-1$ in the incidence matrix by $2$). This will mostly be explained later in the book, but it is not that difficult to prove yourself. Try proving it over $\mathbb{R}$ first and you can easily extend it to any field after that.

share|improve this answer
    
Thank you! Let me try that out. –  Math Noob Jan 16 '13 at 11:53
    
I think I see why this works. To construct this representation we just take the incidence matrix of the undirected graph, and flip exactly one $1$ in each column to $-1$ ($=2$ for $GF[3])$. This gives a cycle matroid of the graph for the following reason: Given any set of arcs whose underlying edges form a cycle, one can flip some subset of the arcs to get a directed cycle. Flipping an arc corresponds to multiplying its column by $-1$, and so every cycle in the graph corresponds to a circuit in the matroid, and conversely. Thank you, once again! –  Math Noob Jan 16 '13 at 12:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.