Representing some non-representable matroids
|Speaker:||Stefan van Zwam|
|Affiliation:||CWI Amsterdam and University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
A matroid consists of a finite set, together with a partition of its subsets into "dependent" and "independent" ones, subject to some axioms. An important example is a finite set of vectors, where the "independent" subsets are precisely those that are linearly independent.
One of the major themes in matroid theory research is the representation question: given a matroid, can we find a dependency-preserving map from the finite set to a vector space? The answer depends very much on the (skew) field underlying the vector space, and many matroids are not representable at all!
Most research has focused on matroids representable over a (commutative) field. In particular, in 1996, Semple and Whittle introduced partial fields to study matroids that can be represented over several distinct fields. I will start my talk with an introduction to partial fields, and mention a few applications, including a very short proof of Tutte's characterization of the regular matroids.
The main theme of this talk is skew partial fields. These generalize partial fields by dropping the requirement that multiplication is commutative. The construction of matroid representations over commutative partial fields relies heavily on determinants, for which there is no straightforward generalization to the noncommutative case. To get around this, we will fall back on the way Tutte treated matroid representation, namely by something he called a chain group.
One feature of partial fields is that, whenever a matroid is representable over a partial field, it is also representable over a field. Not so for skew partial fields: I will exhibit a matroid that is representable over a skew partial field but not over any skew field! Hence skew partial fields provide a proper extension of the notion of representability, while preserving most traditional properties.
I will mention several open problems, including one which does not require any matroid theory to solve.
This talk is based on joint work with Rudi Pendavingh.
200 University Avenue West
Waterloo, ON N2L 3G1