Nishad-Kothari-IIT-Madras

651 subscribers

237 videos

I am a graph theorist at the Dept. of Computer Science and Engineering at IIT Madras, and I love teaching and sharing knowledge. My homepage: https://sites.g...

Latest Videos

Matching Theory Lecture-30 Part-II Non-removability in bicritical graphs (CLM 2012) proof continued

Matching Theory Lecture-30 Part-I DM-barriers return; non-removability in bicritical graphs (CLM12)

Matching Theory Lecture-29 Part-IINon-removability in solid (Birkhoff - von Neumann) bricks; CLM 12

Matching Theory Lecture-29 Part-I Existence of removable edges in bricks (Lovász 83; CLM 99 proof)

Matching Theory Lecture-28 Structure of a brick w.r.t. two mutually-exclusive doubletons (CLM 1999)

Matching Theory Lecture-27 Part-II Monotonicity (proof continued); ELP Theorem (1982) to the rescue

Matching Theory Lecture-27 Part-I Monotonicity of b (# of bricks) w.r.t. deletion (CLM 2002) proofs

Matching Theory Lecture-26 Part-IMutual dependence in bricks (Lovász); Monotonicity of b (CLM 2002)

Matching Theory Lecture-26 Part-IIExistence of Delta (max. degree) minimal classes (an application)

Quantum photonic experiments & their connection to Matching Theory --- by Rishikesh Gajjala

Matching Theory Lecture-24 Part-I Mutual dependence (bipartite & bricks); Lucchesi-Murty result

Matching Theory Lecture-25 Part-II Application (solitude in 2-conn. cubic graphs --- Narayana 2025)

Matching Theory Lecture-25 Part-I Lucchesi-Murty --- minimal classes vs even 2-cuts (continued)

Matching Theory Lecture-24 Part-II Lucchesi-Murty --- minimal classes vs even 2-cuts (with proof)

Matching Theory Lecture-23 Part-I Removability vs separating cuts; CLM's (1999) Dependence Theory

Matching Theory Lecture-23 Part-II An application (solitude); Structural implications of dependence

Matching Theory Lecture-22 Part-I Non-removability in bipartite MCGs; adjacent non-removable edges

Matching Theory Lecture-22 Part-II Lovász-Vempala result & an application to near-bipartite bricks

Matching Theory Lecture-21 Course Part-II begins; Removable edges and minimal removable edge sets

Matching Theory Lecture-20 Part-I Separating cut decompositions; BvN vs odd-intercyclic

Matching Theory Lecture-20 Part-II MCGs free of conformal bicycles; BvN intersected with PM-compact

Matching Theory Lecture-19 Part-II Solid bricks are BvN; CLM (2004) proof via precedence relation

Matching Theory Lecture-19 Part-I CLM (2004) result --- Birkhoff - von Neumann graphs are solid

Matching Theory Lecture-18 Part-I Balas' (1981) characterization of BvN graphs (proof continued)

Matching Theory Lecture-18 Part-II Carvalho-Lucchesi-Murty (CLM 2004) --- solid bricks = BvN bricks

Matching Theory Lecture-17 Part-I Solid graphs, Birkhoff - von Neumann graphs and characterizations

Matching Theory Lecture-17 Part-II Balas' (1981) characterization of Birkhoff - von Neumann graphs

Matching Theory Lecture-16 Part-II Solid graphs, Birkhoff von-Neumann graphs and relaxations of PMP

Matching Theory Lecture-16 Part-IMatching Space (ELP & Naddef); Matching Lattice (Seymour & Lovász)

Matching Theory Lecture-15 Part-II A proof of Edmonds' Perfect Matching Polytope Theorem continued