Friday, March 25, 2011
3:30 pm, MC 5158

Jim Geelen
University of Waterloo

Characterizing graphic matroids by a system of linear equations

Given a rank-$r$ binary matroid $M$, we construct a system of $O(r^3)$ linear equations in $O(r^2)$ variables that has a solution over GF$(2)$ if and only if $M$ is graphic.

This is joint work with Bert Gerards. The talk will be self-contained.