Tutte seminar - Jim Geelen

Characterizing graphic matroids by a system of linear equations

Abstract:

Given a rank-r binary matroid M, we construct a system of O(r³) linear equations in O(r²) 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.