CS6535-2023
Matching Theory

Syllabus (being updated as the course proceeds):

• Module-0: Perfect Matchings and Matchable Graphs (1 week)
  Perfect Matchings & Matchable Graphs
  Tutte's Theorem  characterizing Matchable Graphs (and its proof due to Tutte & Lovasz)
  Petersen's Theorem
  Hall's Theorem (as a consequence of Tutte's Theorem)

• Module-1: Matching Covered Graphs (MCGs), Barriers and Tight Cuts (3 weeks)
  Barriers & the Core of a Matchable Graph (with respect to a barrier)
  The Kotzig Relation
  Matchable Edges, MCGs & Bicritical Graphs (and their characterizations in terms of barriers)
  The Dulmage-Mendelsohn Decomposition for Bipartite Matchable Graphs
  A strengthening of Petersen's Theorem
  Some important infinite families of MCGs
  Operations for constructing MCGs: Bi-subdivisions & Splicing
  The (Kotzig-Lovasz) Canonical Partition Theorem & the Canonical Partition of a MCG (& its proof using the Core)
  Odd Cuts, Separating Cuts and Tight Cuts
  Barrier Cuts and 2-separation Cuts
  The Tight Cut Decomposition Procedure, and Bricks & Braces
  Crossing versus Laminar Cuts, and Laminar Families of (Tight) Cuts
  The Uncrossing Lemma for Tight Cuts
  Lovasz's Unique (Tight Cut) Decomposition Theorem (and its proof due to Lovasz)
  Tight Cuts in Bipartite MCGs, and Braces (and their characterizations)
  The ELP (Edmonds, Lovasz & Pulleyblank) Theorem (and its brief history)
  Peripheral Tight Cuts, and Dulmage-Mendelsohn barriers (DM-barriers)
  Proof of the ELP Theorem using DM-barriers (due to Carvalho, Lucchesi and Murty; inspired by Szigeti's proof)
  An application of the ELP Theorem: Characterizing Tight Cuts in Cubic MCGs
  Essentially 4-edge-connected graphs & cubic graphs
  The Laminar ELP Theorem (only statement)
  Bi-contraction, bi-splitting, retracts and 2-stable retracts

• Module-4.1: Pfaffian Orientations (2 weeks)
  Skew-Symmetric Matrices (SSMs) and their Pfaffians
  Correspondence between SSMs and Weighted Digraphs
  Cayley's Theorem (only statement)
  Sign of a Perfect Matching (w.r.t. an orientation)
  Counting the Number of PMs using Pfaffian Orientations (POs)
  Valiant's Theorem (only statement)
  Pfaffian Digraphs, Orientations & Graphs
  Two Decision Problems: Pfaffian Recognition Problem (PRP) & Pfaffian Orientation Problem (POP)
  Oddly-oriented and evenly-oriented trails (with focus on cycles)
  POs of even cycles; Comparing the signs of two PMs
  Conformal subgraphs and cycles
  Equivalent definitions of POs using conformal cycles and M-alternating cycles
  K_{3,3} is NOT Pfaffian --- proof and ideas
  Intractable Collection of Conformal Cycles; Little's Theorem (only statement)
  Kasteleyn's Theorem (planar implies Pfaffian)
  Similarity of Orientations, and POs under similarity
  POs versus Separating Cuts
  POs versus Tight Cuts: reducing the POP to bricks & braces

• Module-2: Removability, Dependence and Ear Decompositions
  Revisiting the Ear Decomposition Theorem for Bipartite MCGs
  Conformal Subgraphs & Cycles
  An easy (but not very useful) "ear decomposition theorem" for all MCGs
  Two different viewpoints: adding ears versus deleting ears
  Removable Ears
  The Lovasz-Plummer Two Ear Theorem
  Dependence, Mutual Dependence & Removability
  Dependence Digraph & Reduced Dependence Digraph
  Source classes of cardinality one and two
  Even 2-cuts versus Source classes of cardinality two or more
  Removable classes: edges & doubletons
  Proof of the Lovasz-Plummer Two Ear Theorem
  Conformal Minors
  Lovasz's Primary Ear Decomposition Theorem
  Dependence Classes in Bricks
  Near-Bipartite Graphs versus Near-Bricks