Algebraic Tools for Graph Matchings - November 13, 2023

Learn about algebraic approaches to graph matching problems in this advanced mathematics seminar lecture that explores deterministic and probabilistic algorithms. Discover how to determine the existence of perfect matchings in bipartite graphs using matrix determinants with random number substitutions, and delve into the more complex non-bipartite case involving skew-symmetric matrices. Examine why matching patterns persist while non-matching elements cancel out in these mathematical structures. Follow along as the discussion progresses to derandomization techniques and the development of quasi-polynomial parallel algorithms, providing a comprehensive view of modern algebraic graph theory applications.