Tutte Colloquium - Jim Geelen

Friday, March 18, 2016 3:30 pm - 3:30 pm EDT (GMT -04:00)

Title: Recognizing frame matroids

Speaker: Jim Geelen
Affiliation: University of Waterloo
Room: MC 5501

Abstract: A {\em frame} matrix is one that has at most two nonzero entries in each column.  In joint work with Rong Chen, Benson Joeris, and Peter Nelson we give a polynomial-time algorithm for the problem of deciding whether a given matrix is row-equivalent to a frame matrix. For matrices over the two element field this problem is equivalent to the problem of recognizing whether a given binary matroid is graphic, which was solved by Tutte in 1960.  In the talk I will discuss the motivation for the problem and give an overview of the  algorithm.  No prior exposure to
matroid theory is assumed.