Evalutation: 50% assignments + 50% project
More details to be added later.
Lecture-1: Perfect Matchings, Tutte's Theorem and Matching Covered Graphs (MCGs)
Lecture-2: The Canonical Partition Theorem (due to Kotzig and Lovász)
Lecture-3: Families, Operations and Hetyei's Ear Decompositions for Bipartite MCGs
Lecture-4 Part-I: Separating cuts, tight cuts and barrier cuts
Lecture-4 Part-II: Barrier cuts, 2-separation cuts and the ELP Theorem
Lecture-5: Separating cuts in bipartite graphs, and tight 3-cuts, are barrier cuts
Lecture-6 Part-I: Bricks & Braces, ELP Theorem statement(s), and important families (of bricks & braces)
Lecture-6 Part-II: Tight Cut Decomposition (TCD) procedure and Lovász's Unique Decomposition Theorem
Lecture-7 Part-I: Lovász's (1987) Unique Tight Cut Decomposition Theorem & its proof
Lecture-7 Part-II: Lovász's Unique Tight Cut Decomposition Theorem (proof continued)
Lecture-8: CLM (2002) Theorem (Lovász's Conjecture) & Subadditivity of the b function/invariant (number of bricks)
Lecture-9 Part-I: Subadditivity of b (no. of bricks) across separating cuts & proof (laminar case)
Lecture-9 Part-II: Subadditivity of b across separating cuts; proof continued (crossing case)
Lecture-10 Part-I: ELP (Edmonds-Lovász-Pulleyblank) Theorem (1982), related history & ingredients for CLM's proof
Lecture-10 Part-II: ingredients for CLM's proof of ELP Theorem, peripheral tight cuts & DM (Dulmage-Mendelsohn) barriers
Lecture-11 Part-I: Towards a proof of the ELP Theorem; a property of peripheral tight cuts
Lecture-12 Part-I: Existence of a well-behaved DM-barrier in matchable graphs with a special cut; CLM's proof of the ELP Theorem
Lecture-12 Part-II: CLM's (Carvalho-Lucchesi-Murty) proof of the ELP (Edmonds-Lovász-Pulleyblank) Theorem (continued)
Lecture-13 Part-I: Applications of the ELP Theorem (characterizing bicritical graphs, and tight cuts in 2-connected cubic graphs)
Lecture-13 Part-II: Characterizations of Braces (and of tight cuts in MCGs with two bricks) without proofs
Lecture-14 Part-I: Convex Polytopes, Linear Inequalities & Minkowski-Weyl Theorem
Lecture-14 Part-II: Edmonds' (1965) characterization of the Perfect Matching Polytope (without proof)