Graph Theory, Lecture 45: Graph Minors I: The graph minor theorem, its proof for trees, and wqo
Автор: Reinhard Diestel: Graph theory lectures
Загружено: 2024-12-07
Просмотров: 547
Описание:
Recap: which graph properties can be characterised by excluding minors?
Notion of Kuratowski set (of graphs for a given minor-closed property), 6:45.
Statement (via minor-antichains) of graph minor theorem, Theorem 12.7.1 (7:00).
Notion of excluded-minor theorems (8:25). The myth of Wagner's Conjecture (8:55).
Algorithmic consequences of the graph minor theorem (10:40).
Two applications of the graph minor theorem: surface embeddability, and knotless embeddability in 3-space.
Notion of well-quasi-ordering (wqo, 17:25); expressing the graph minor theorem in these terms.
Basic wqo properties. Higman's lemma (28:50), with false 'obvious' proof (32:00-35:00).
Correct proof by minimal bad sequence method (37:00-45:00).
Embeddings of rooted trees, strengthening the graph minor relation for trees.
Proof of the 'graph minor theorem for trees': Kruskal's Theorem 12.2.1 that the trees are wqo by rooted-tree embedding.
Covers Chapter 12.1-2.
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".
Повторяем попытку...
Доступные форматы для скачивания:
Скачать видео
-
Информация по загрузке:
![Самая простая нерешённая задача — гипотеза Коллатца [Veritasium]](https://imager.clipsaver.ru/QgzBDZwanWA/max.jpg)
