|
Chennai Combinatorics Colloquium Series Date: Friday, 28 February 2025 Time: 3:30 PM Venue: Seminar Hall A walk through the history and present of Perfect Matchings Nishad Kothari IIT Madras. 28-02-25 Abstract The study of perfect matchings goes back all the way to the Four Color Conjecture (1852) and related developments due to Tait (1880) and Petersen (1891). Since then, there have been lots of advances in the theory of perfect matchings, and during this talk, I intend to walk you through some of the major milestones. In particular, I will discuss the seminal contribution of Tutte (1947) characterizing those graphs that have a perfect matching, and that paved the way for Edmonds' (1965) algorithmic as well as polyhedral advances. Thereafter, I will describe the notion of pfaffian orientations introduced by theoretical physicists (1960s) to count the number of perfect matchings, and walk you through the major contributions of Little (1975), of McCuaig (2004), and independently, of Robertson, Seymour and Thomas (1999) pertaining to characterizing bipartite pfaffian graphs --- thus solving Polya's Permanent Problem (amongst many other equivalent formulations). Finally, I will discuss the breakthrough contributions of Lovász (1987) who characterized the matching lattice. In doing so, not only did Lovász once again establish the importance and elusive nature of the Petersen graph, but also provided the subject with solid theoretical foundations. One of Lovász's notoriously difficult conjectures was proved by Carvalho, Lucchesi and Murty (2002), and this set the three of them on a long journey (two decades or so) of laying further theoretical foundations that they used to solve other open problems and also to simplify many of the existing proofs --- including the aforementioned ones due to Little and Lovász. Their work has culminated in the recently published book "Perfect Matchings: A Theory of Matching Covered Graphs" by Lucchesi and Murty (2024). This talk is inspired by, and based on, their book. Note: This is the second talk in the Chennai Combinatorics Colloquium, a monthly meeting of Chennai's Combinatorics Enthusiasts, which will be held at a different venue in Chennai each time. The talk is two hours long with a break after an hour.
|
