Graph Theory, Lecture 47: Graph Minors III: Brambles and tree-width duality скачать в хорошем качестве

Graph Theory, Lecture 47: Graph Minors III: Brambles and tree-width duality

The need for certificates for large tree-width: how can we prove that a graph has no tree-decomposition of small width? The use of such certificates in the proof of the graph minor theorem. Notion of brambles and their order (3:30). Bramble of crosses in a grid (7:30). Duality Theorem 12.4.3 about tree-width and brambles, with Mazoit's proof via petals (from 10:20). Proof of easy implication, structural version: every bramble is covered by some part of every tree-decomposition (11:45-16:37). Quantitative statement of Theorem 12.4.3 entails loss of information over this structural version (16:40-22:20). Proof of hard implication of Theorem 12.4.3 from 24:40. Covers remainder of Chapter 12.4. Based on R.Diestel, Graph Theory, Springer GTM173, 6th edition 2025. Ebooks available at https://diestel-graph-theory.com under links "Standard eBook" and "Professional Edition".