Evalutation: 100% assignments.
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)
Lecture-15 Part-I: A proof of Edmonds' Theorem characterizing the Perfect Matching Polytope
Lecture-15 Part-II: A proof of Edmond's Theorem characterizing the Perfect Matching Polytope (continued)
Lecture-16 Part-I: The Matching Space (ELP & Naddef), the PM Integer Cone & the Matching Lattice (due to Seymour & Lovász)
Lecture-16 Part-II: Solid graphs (and bricks), Birkhoff - von Neumann graphs and relaxations of the Perfect Matching Polytope
Lecture-17 Part-I: Solid graphs, Birkhoff - von Neumann graphs and their characterizations (without proofs)
Lecture-17 Part-II: Balas' (1981) graph-theoretical co-NP characterization of Birkhoff - von Neumann graphs (BvN) and its proof
Lecture-18 Part-I: Balas' (1981) characterization of BvN graphs (BvN if and only if NO conformal odd bicycle) proof (continued)
Lecture-18 Part-II: Carvalho-Lucchesi-Murty (CLM 2004) Solids bricks are the same as Birkhoff - von Neumann (BvN) bricks
Lecture-19 Part-I: Carvalho-Lucchesi-Murty (CLM 2004) result --- BvN graphs are solid, and its proof
Lecture-19 Part-II: Carvalho-Lucchesi-Murty (CLM 2004) result --- Solid bricks are BvN; proof via CLM's precedence relation
Lecture-20 Part-I: Separating cut decompositions & their non-uniqueness; BvN vs odd-intercyclic (and projective planar embeddings)
Lecture-20 Part-II: Birkhoff - von Neumann intersected with PM-compact: MCGs free of conformal bicycles (let's forget parity)
Lecture-21: Part-II of this offering begins (still Part-I of Lucchesi-Murty); Removable edges and minimal removable edge sets
Lecture-22 Part-I: Non-removability in bipartite MCGs; certificate for non-removability; pair of adjacent non-removable edges
Lecture-23 Part-II: An application of CLM's dependence theory to solitude; structural implications of dependence & mutual dependence
Lecture-24 Part-I: Mutual dependence in bipartite MCGs & bricks; Lucchesi-Murty result: minimal classes vs even 2-cuts
Lecture-24 Part-II: Lucchesi-Murty result (every minimal class, of cardinality three or more, includes an even 2-cut); proof continued
Lecture-25 Part-II: Narayana (2025) --- an application of Lucchesi-Murty result to solitude in 2-connected cubic graphs; Kotzig's Lemma
Lecture-26 Part-I: Mutual dependence in bricks (Lovász); Monotonicity of b with respect to deletion of removable classes (CLM 2002)
Lecture-26 Part-II: An application --- existence of Delta (max. degree) minimal classes; existence of removable edges in bricks (Lovász)
Lecture-27 Part-I: Monotonicity of b (number of bricks) with respect to deletion of removable classes (CLM 2002) with proofs
Lecture-27 Part-II: Monotonicity of b with respect to deletion (proof continued); ELP Theorem (1982) to the rescue
Lecture-28: Structure of a simple brick with respect to a pair of mutually-exclusive doubleton equivalent classes (CLM 1999)
Lecture-29 Part-I: Existence of removable edges in bricks --- except K4 and triangular prism (Lovász 1983); proof by CLM (1999)
Lecture-30 Part-II: Non-removability in bicritical graphs (CLM 2012) proof continued