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?]).
- Pick a spanning tree T in G, make all its edges + (positive) and all other edges − (negative).
- Reverse A: the tree edges are negative and the cotree edges are positive.
I plan to emphasize (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.
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:
- 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
All problems are for Example (I) above.
- Describe all the independent sets of F(Σ).
- Do this for a specific graph, such as K4 or 5.
- Do it for another graph.
- Do it in general.
You may skip (a, b), but be prepared to work with specific graphs, not only general theory.
-
-
-
-
To the
| course page
| assignments
| extra material
| corrections page.
To my home page.