Centre for the Mathematics of Symmetry and Computation

Matroid Theory

Researcher

Gordon's current interests are based around:

  • developing exact structural characterisations for specific families of binary matroids
  • naturally complementing these important general results
  • providing a deeper insight into the structure of binary matroids

Matroids provide a unified approach to various notions of independence important across mathematics.

The concept of linear independence in a vector space is one of the most powerful tools in mathematics, with wide-ranging applications to almost every mathematical area.

The study of matroids arose from attempts to give a purely combinatorial definition of independence that would capture the power of linear algebra without reference to the algebraic structure underlying a vector space.

Thus a matroid is a collection of sets that "behaves like" the collection of linearly independent sets of vectors in a vector space, but does not necessarily arise from a vector space. Matroids can arise from graphs, from vector spaces, from linear codes, from transversals of a set system and in many other places.

Therefore matroid theory provides a unified setting for the study of the abstract properties of independence no matter where it occurs.

There is a rich structural theory of graphs based on the fundamental concept of a graph minor that illustrates the central importance of minor-closed classes of graphs. The concept of a graph minor has a natural counterpart in matroids and an analogous structural theory can be developed, at least for binary matroids (which includes both graphs and binary linear codes). 

This structural theory provides a very high level coarse description of any proper minor-closed class of graphs or binary matroids, but cannot be used to determine the fine-grained structure of any particular class.

 

Centre for the Mathematics of Symmetry and Computation

This Page

Last updated:
Tuesday, 24 August, 2010 4:16 PM

http://www.cmsc.uwa.edu.au/717122