Charles Kenney, Rutgers University

Abstract

Let G be a bipartite graph on (L,R). Say G is a minimal Hall violator with defect D if |L| = |R|+1+D, and for all l in L, there is an R-perfect matching in G-l. We characterize minimal Hall violators, then transition to a related definition of matroids. Examples and exercises for the audience included. This expository talk is based primarily on Section 1.3 in Lovasz and Plummer (Matching Theory).