Math 580A: Topics in Combinatorial Analysis
Matroid Theory Project
Fall 2026

To the | course page | assignments | extra material | corrections page.

Project

The idea of the project is to develop all the properties of a specific kind of matroid, that has never been studied previously, right alongside learning the properties of matroids as expounded by Oxley. I have two specific matroids in mind, both based on signed graphs. Let G be any connected graph (finite [of course?]).

  1. Pick a spanning tree T in G, make all its edges + (positive) and all other edges − (negative).
  2. Reverse I: the tree edges are negative and the cotree edges are positive.
  3. Related to I and II but different: Double the edges of the spanning tree, one positive and one negative. The other edges should all be positive.
  4. The negation of III: Double the edges of the spanning tree, one positive and one negative. The other edges should all be negative.

I plan to emphasize Example I in class work, which includes you students applying your new knowledge to those examples. Of course you have to know what to do with a signed graph; that's next.

I have a suspicion that III and IV are more interesting than I and II, but we'll see. We'll discuss III in class.

Signed graphs

Take a graph G and choose any fixed sign function σ : E(G) → {+, −}. That gives you a signed graph, Σ = (G, σ). A circle C (or cycle, polygon, etc.) is a connected subgraph of degree 2 at each of its vertices. I usually think of it as an edge set. The sign of C is the product of the signs of its edges, therefore C is positive or negative. The sign of a circle affects its role in the matroid. This matroid F(Σ), called the frame matroid, is a generalization of the cycle matroid of a graph (Oxley, §1.1). It has the following circuits: Your first assignment is to find the independent sets of the frame matroid.

Problems on Signed Graphs

Problems are for Example I or II above, as marked. They are for a general graph G, except as noted—but if you can't do a general solution, do some examples (and look for patterns; that's what math is).
General rule: Make your description as specific to the example as possible.

  1. Describe all the independent sets of F(Σ) (Ex. I).
    1. Do this for a specific graph, such as K4 or 5.
    2. Do it for another graph.
    3. Do it in general.
    You may skip (a, b), but be prepared to work with specific graphs, not only general theory.
  2. Describe all the bases of F(Σ) (Ex. II).
  3. Find all the edge sets of rank 2 in Ex. I.

To the | course page | assignments | extra material | corrections page.

To my home page.