Matroid Theory Project
Fall 2026

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. The signed graph Σ_I. Pick a spanning tree T in G, make all its edges + (positive) and all other edges − (negative).
2. The signed graph Σ_II. Reverse I: the tree edges are negative and the cotree edges are positive.
3. The signed graph Σ_III. 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 signed graph Σ_IV. 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, σ).

Define a signed graph to be complete if every two vertices are adjacent. They might be adjacent by a positive edge, a negative edge, or both. (It seems that complete graphs make the best examples; they give complexity of signs without complexity of the underlying graph.)

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:

• Positive circles.
• Union of two negative circles that have exactly one common vertex.
• Union of two disjoint negative circles, together with any minimal path between them. Note that "minimal" ≠ "minimum"; the length is irrelevant.

Your first assignment is to find the independent sets of the frame matroid.

Problems on Signed Graphs

Problems are for examples above, as indicated. 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(Σ_I).
   1. Do this for a specific graph, such as K_{4 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(Σ_II).
3. Find all the edge sets of rank 2 in Σ_I.
4. Assume the graph is complete.
   1. Find all the 4-element circuits in Σ_I.
   2. Find all the 4-element circuits in Σ_IV.
5. Assume the graph is complete. What are the flats of F(Σ_IV)?
6. Let Σ be connected. Describe the matroid components of F(Σ) in terms of the graph structure.

More about signed graphs

For the matroid theory we need contraction of edges, which requires switching. For two interesting applications we'll need vertex coloring and the representation by hyperplane arrangements in Rⁿ.

You will find complete descriptions in SGGM: "Signed graphs and geometry". The half edges and loose edges should be treated (for matroid purposes, and for graph contraction) as negative loops and positive loops, respectively.

To my home page.