Joint Pure Math/C&O Colloquium - Justin Toth

Tuesday, July 17, 2018 3:00 pm - 3:00 pm EDT (GMT -04:00)

Title: Using Linear Algebra to do Matching Theory

Speaker: Justin Toth
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

A matching in a graph is a set of edges with each vertex contained in at most one edge. A perfect matching is a matching in which each vertex is contained in some edge. One of the most fundamental theorems in graph theory is Tutte's classic result characterizing those graphs which have a perfect matching. If you ask any student of C&O for a proof they will give you a combinatorial proof using alternating paths, blossom circuits, and edge deletion and contraction. Yet Tutte's original proof was not of this nature. He studied a skew-symmetric matrix of indeterminants, now called the Tutte matrix, related to the underlying graph, and gave a linear-algebraic proof based on the properties of this matrix. We will present a proof in this spirit, more akin to what a Pure Math student might give, for Tutte's Theorem. We will then leverage this linear-algebraic prospective to show a randomized algorithm for matching based on sampling from a finite field.