Graph Theory, Lecture 48: Graph Minors IV: Other certificates of large tree-width скачать в хорошем качестве

Graph Theory, Lecture 48: Graph Minors IV: Other certificates of large tree-width

Recap: the use of certificates for large tree-width in the proof of the graph minor theorem. First certificate: large-order brambles; see Lecture 47. Second certificate: large highly connected vertex sets (from 2:00). Proof that these certify large tree-width, and that they exist in all graphs of large tree-width. Third certificate: large-grid minors - the Grid Theorem 12.6.3 (from 56:50). Application of the grid theorem: graphs with the Erdös-Pósa property, Theorem 12.6.5. Proof of Theorem 12.6.5 from grid theorem (1:06:55). The material covered in this lecture is not all covered in the book; but see Exercises 38-39 in Chapter 12. 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".