Mathematical Sciences - Colloquium

Matroids are everywhere.  Vector spaces are matroids.  Matroids are useful in situations that are modelled by both graphs and matrices.  Bicircular matroids model generalized network flow problems whose algorithms are more efficient than those available for general linear programming codes.

Let G be a graph (loops and parallel edges allowed) with vertex set V = {1,2, …, n} and edge set E.  In the classical matroid associated with a graph, a set of edges is independent in the matroid if it contains no cycles, and the circuits of the matroid are the single cycles of G.  The bicircular matroid of G is the matroid B(G) defined on E whose circuits are the subgraphs which are subdivisions of one of the following graphs:

The bicircular matroid is known to be a transversal matroid and thus can be represented by a family of sets, called a presentation.  It has been known for some time that the maximal presentation of a transversal matroid is unique.  In general, a transversal matroid has many  minimal presentations.  We show how, given a graph G, one could find a minimal presentation for B(G) and, from that, find all other minimal presentations.

We demonstrate this with the graph

called a wheel on six vertices.  The problem reduces to searching for trees and single cycles.  This example led to the general classification of the minimal presentations of an arbitrary bicircular matroid.

Spring 2000 Colloquium Schedule | Mathematical Sciences home | The University of Montana home