Duality 3

on YouTube ↗01h 05m

" summary

Shows that stab(G) equals Qstab(G) exactly when every induced subgraph satisfies Omega = Chi, proved by LP duality on the weighted clique problem and Lovász’s replication lemma which turns rational weights into unit-weight vertices; key is total dual integrality giving integer dual solutions so convex combinations of stable sets reconstruct points in Qstab. Notes SDP (theta body) equals stab iff perfect but doesn’t give a simple polytime recognizer. Gives a polyhedral proof that a 2-edge-connected subgraph can be turned into a TSP tour with cost factor ≤2 using matchings on odd-degree vertices and the T-join half-integrality.

AI-written summary · about

" chapters (11)

1. 0:00Stable sets and cliques
2. 2:41Introduction to perfect graphs
3. 5:11Polytope and SDP bounds
4. 8:21Bipartite graph examples
5. 12:11Comparability graphs
6. 16:15Weighted cliques and duality
7. 21:02Lovász replication lemma
8. 25:46Proving perfect graph theory
9. 35:46Perfect graph recognition
10. 44:55Graph entropy
11. 52:24TSP and combinatorial proofs

" related talks

• 44mCombinatorial Characterizations in Semidefinite Programming Duality: ...Gabor Pataki · Hyperbolic Polynomials and Hyperbolic Programming
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 43mApplied Hodge TheoryYuan Yao · Spectral Algorithms: From Theory to Practice 2014
• 28mImproved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) BicliquePasin Manurangsi · ITCS 2023
• 30mStrong Data Processing Inequalities: Applications to MCMC and Graphical ModelsMaxim Raginsky · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 04mFrom Proofs to Algorithms for Machine Learning ProblemsDavid Steurer · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)