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.