Graph Theory, Lecture 47: Graph Minors III: Brambles and tree-width duality
Автор: Reinhard Diestel: Graph theory lectures
Загружено: 2024-12-12
Просмотров: 231
Описание:
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".
Повторяем попытку...
Доступные форматы для скачивания:
Скачать видео
-
Информация по загрузке:
