Reinhard Diestel: Graph theory lectures
Reinhard Diestel: Graph theory lectures
  • Видео 54
  • Просмотров 10 987
Graph Theory, Lecture 52: Graph Minors VIII: Excluded-minor structure and the graph-minor theorem
Statement of the excluded-minor structure Theorem 12.6.6: near embeddings of graphs in surfaces (1:45).
Apex vertices, punctured surfaces, vortices and their depth (3:40-14:00).
All these three, plus allowing tree-structure, are necessary incredients to the structure theorem (19:00-45:00).
Statement of the Graph Minor Theorem 12.7.1: the finite graphs are well-quasi-ordered by the minor relation.
Sketch of proof of the graph minor theorem.
Covers the essence of Chapter 12.6-7.
Просмотров: 85

Видео

Graph Theory, Lecture 51: Graph Minors VII: Tangle-tree duality1:37:15Graph Theory, Lecture 51: Graph Minors VII: Tangle-tree duality
Graph Theory, Lecture 51: Graph Minors VII: Tangle-tree duality
Просмотров 7712 часов назад
The poset of oriented edges of a tree. The vertices of a tree correspond 1-1 to the consistent orientation of its edges. Definition of S-tree for a set S of separations of a graph (9:15). Tree-shape of graphs captured by its S-trees: equivalence of tree-decompositions with S-trees (24:20-25:20). S-trees displaying 'trees of tangles' (nested sets of separations distinguishing all tangles; 25:25-...
Graph Theory, Lecture 50: Graph Minors VI: Tangles - canonical trees of tangles via entanglements1:09:41Graph Theory, Lecture 50: Graph Minors VI: Tangles - canonical trees of tangles via entanglements
Graph Theory, Lecture 50: Graph Minors VI: Tangles - canonical trees of tangles via entanglements
Просмотров 7119 часов назад
Recap of splinters proof of the ToT Theorem 12.5.1: choices made in the proof make it non-canonical. Informal, algorithmic, notion of canonical (3:30). More formal notion in terms of invariants (6:05). Statement of Carmesin's Entanglement Theorem 12.5.8, which yields a canonical tree of tangles (13:20). Proof that the set of efficient distinguishers of any fixed pair of tangles is an entangleme...
Graph Theory, Lecture 49: Graph Minors V: Tangles - intuition, definition, properties1:37:27Graph Theory, Lecture 49: Graph Minors V: Tangles - intuition, definition, properties
Graph Theory, Lecture 49: Graph Minors V: Tangles - intuition, definition, properties
Просмотров 16319 часов назад
Motivation of notion of tangles from clustering, leading to formal definition (2:10-20:10). Informal announcement of two fundamental tangle theorems: the tree-of-tangles (ToT) theorem (22:24-26:24) and the tangle-tree duality (TTD) theorem (26:24-27:10). Notions of orianted separations, their partial ordering, and nestedness of separations (28:30-40:00). Fish Lemma 12.5.2 about crossing and nes...
Graph Theory, Lecture 48: Graph Minors IV: Other certificates of large tree-width1:20:05Graph 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
Просмотров 13021 час назад
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). Appl...
Graph Theory, Lecture 47: Graph Minors III: Brambles and tree-width duality1:31:09Graph Theory, Lecture 47: Graph Minors III: Brambles and tree-width duality
Graph Theory, Lecture 47: Graph Minors III: Brambles and tree-width duality
Просмотров 110День назад
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, s...
Graph Theory, Lecture 46: Graph Minors II: Tree-decompositions and tree-width1:12:08Graph Theory, Lecture 46: Graph Minors II: Tree-decompositions and tree-width
Graph Theory, Lecture 46: Graph Minors II: Tree-decompositions and tree-width
Просмотров 73День назад
Notion of tree-decomposition, motivated and discussed in detail. Aside on the process of generating new notions in mathematics (8:45-11:25). Basic properties of tree-decompositions (from 15:30). Notion of k-blocks (39:30). Theorem 12.3.7 that tree-decompositions can distinguish them efficiently (44:30). Notion of tree-width (48:00). Graphs of bounded tree-width are wqo. Notion of lean and linke...
Graph Theory, Lecture 45: Graph Minors I: The graph minor theorem, its proof for trees, and wqo1:10:40Graph Theory, Lecture 45: Graph Minors I: The graph minor theorem, its proof for trees, and wqo
Graph Theory, Lecture 45: Graph Minors I: The graph minor theorem, its proof for trees, and wqo
Просмотров 19614 дней назад
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 Theory, Lecture 44: Perfect graphs58:48Graph Theory, Lecture 44: Perfect graphs
Graph Theory, Lecture 44: Perfect graphs
Просмотров 20414 дней назад
Local/global reasons for high chromaticity. Notions of clique and independence number. Definition of perfect graphs, with justification (3:50-6:00). Motivation and statement of strong perfect graph theorem (from 8:30). Characterising graph properties by excluding subgraphs, minors etc (from 9:30). A secret about infinite graphs (11:00). Statement of weak perfect graph theorem, Theorem 5.5.4 (12...
Graph Theory, Lecture 43: Ramsey theory for induced subgraphs1:23:16Graph Theory, Lecture 43: Ramsey theory for induced subgraphs
Graph Theory, Lecture 43: Ramsey theory for induced subgraphs
Просмотров 24814 дней назад
Three strengthenings of Ramsey's theorem: finding monochromatic copies of H in G for (i) H not complete; (ii) H induced in G; (iii) when G has clique number no bigger than H. Theorem 9.3.1 solves (ii); our proof will solve (iii) at the same time. The induced Ramsey problem (ii) requires constructions rather than structural analysis (3:45). Layout (5:45) of proof of Theorem 9.3.1: bipartite embe...
Graph Theory, Lecture 42: The Regularity Lemma IV: the Removal Lemma58:59Graph Theory, Lecture 42: The Regularity Lemma IV: the Removal Lemma
Graph Theory, Lecture 42: The Regularity Lemma IV: the Removal Lemma
Просмотров 11621 день назад
Informal introduction to removal lemma. Statement of removal lemma (2:40). Proof, slowly developed, from 3:58. A surprising corollary of the removal lemma: the copies of H must be lumped together in any dense G that contains few copies of H (from 22:41). In particular (Theorem 7.6.4): if the copies of H are spread thinly over the graphs G in some class (in that every edge of G lies in at least ...
Graph Theory, Lecture 41: The Regularity Lemma III: the Counting Lemma1:17:57Graph Theory, Lecture 41: The Regularity Lemma III: the Counting Lemma
Graph Theory, Lecture 41: The Regularity Lemma III: the Counting Lemma
Просмотров 12128 дней назад
Terminology and notation needed for the counting and removal lemma. Rough version of the counting lemma; relation to probability (14:00). Special case of counting complete subgraphs (from 18:40). Statement of the counting lemma (28:00). Typical application of the CL: proof that G contains a copy of some given H (from 38:00). Proof of the counting lemma, slowly developed (from 56:18). Covers the...
Graph Theory, Lecture 40: The Regularity Lemma II: two simple applications49:01Graph Theory, Lecture 40: The Regularity Lemma II: two simple applications
Graph Theory, Lecture 40: The Regularity Lemma II: two simple applications
Просмотров 64Месяц назад
Recap, from Lecture 17 of the Erdös-Stone Theorem 7.1.2. Proof by regularity and blowup lemma, slowly developed (from 4:37). Theorem 9.2.2 that graphs of bounded maximum degree have linear Ramsey numbers (from 23.50). Proof by regularity and blowup lemma, slowly developed (from 28:13). Covers the second half of Chapter 7.5 and the main content of Chapter 9.2.
Graph Theory, Lecture 39: The Regularity Lemma I1:00:12Graph Theory, Lecture 39: The Regularity Lemma I
Graph Theory, Lecture 39: The Regularity Lemma I
Просмотров 82Месяц назад
Informal introduction and definitions required. Statement of the RL (14:00). Regularity graph, from 21:30. Blowup Lemma (simple version), with motivation of statement and proof slowly developed; from 28:00. Covers beginnings of Chapter 7.4-5. See the book for a proof of the RL.
Graph Theory, Lecture 38: Extremal graph theory III: Sparse graphs and linkability1:21:17Graph Theory, Lecture 38: Extremal graph theory III: Sparse graphs and linkability
Graph Theory, Lecture 38: Extremal graph theory III: Sparse graphs and linkability
Просмотров 138Месяц назад
(continuing Lecture 16) Recap: notion of dense and sparse graphs. Recap: Turán's Theorem 7.1.1 on forcing complete subgraphs (dense). Erdös-Stone's Theorem 7.1.2 (dense) on forcing an arbitrary fixed subgraph: the miraculous appearance of the chromatic number (Cor 7.1.3). Better bounds for forcing fixed bipartite subgraphs. The Erdös-Sós conjecture on forcing trees. Recap: forcing Kr minors (12...
Graph Theory, Lecture 36: Algebraic flows II: k-flows and colouring-flow duality1:30:33Graph Theory, Lecture 36: Algebraic flows II: k-flows and colouring-flow duality
Graph Theory, Lecture 36: Algebraic flows II: k-flows and colouring-flow duality
Просмотров 1512 месяца назад
Graph Theory, Lecture 36: Algebraic flows II: k-flows and colouring-flow duality
Graph Theory, Lecture 37: Algebraic flows III: Tutte's flow conjectures and 6-flow theorem45:52Graph Theory, Lecture 37: Algebraic flows III: Tutte's flow conjectures and 6-flow theorem
Graph Theory, Lecture 37: Algebraic flows III: Tutte's flow conjectures and 6-flow theorem
Просмотров 2512 месяца назад
Graph Theory, Lecture 37: Algebraic flows III: Tutte's flow conjectures and 6-flow theorem
Graph Theory, Lecture 35: Algebraic flows I: fundamentals1:18:45Graph Theory, Lecture 35: Algebraic flows I: fundamentals
Graph Theory, Lecture 35: Algebraic flows I: fundamentals
Просмотров 1422 месяца назад
Graph Theory, Lecture 35: Algebraic flows I: fundamentals
Graph Theory, Lecture 34: The Gallai-Edmonds matching theorem38:14Graph Theory, Lecture 34: The Gallai-Edmonds matching theorem
Graph Theory, Lecture 34: The Gallai-Edmonds matching theorem
Просмотров 1912 месяца назад
Graph Theory, Lecture 34: The Gallai-Edmonds matching theorem
Graph Theory, Lecture 33: The Erdös-Posa theorem1:12:31Graph Theory, Lecture 33: The Erdös-Posa theorem
Graph Theory, Lecture 33: The Erdös-Posa theorem
Просмотров 2082 месяца назад
Graph Theory, Lecture 33: The Erdös-Posa theorem
Graph Theory Lectures0:57Graph Theory Lectures
Graph Theory Lectures
Просмотров 5703 месяца назад
Graph Theory Lectures
Graph Theory, Lecture 32: Tree packing and covering, and matroidal duality in graphs1:26:48Graph Theory, Lecture 32: Tree packing and covering, and matroidal duality in graphs
Graph Theory, Lecture 32: Tree packing and covering, and matroidal duality in graphs
Просмотров 1233 месяца назад
Graph Theory, Lecture 32: Tree packing and covering, and matroidal duality in graphs
Graph Theory, Lecture 31: Algebraic planarity criteria, and duality of graphs1:27:29Graph Theory, Lecture 31: Algebraic planarity criteria, and duality of graphs
Graph Theory, Lecture 31: Algebraic planarity criteria, and duality of graphs
Просмотров 3373 месяца назад
Graph Theory, Lecture 31: Algebraic planarity criteria, and duality of graphs
Graph Theory, Lecture 30: Algebraic aspects of graphs II: duality of cycles and cuts1:26:08Graph Theory, Lecture 30: Algebraic aspects of graphs II: duality of cycles and cuts
Graph Theory, Lecture 30: Algebraic aspects of graphs II: duality of cycles and cuts
Просмотров 663 месяца назад
Graph Theory, Lecture 30: Algebraic aspects of graphs II: duality of cycles and cuts
Graph Theory, Lecture 29: Algebraic aspects of graphs I1:08:22Graph Theory, Lecture 29: Algebraic aspects of graphs I
Graph Theory, Lecture 29: Algebraic aspects of graphs I
Просмотров 3943 месяца назад
Graph Theory, Lecture 29: Algebraic aspects of graphs I
Graph Theory, Lecture 28: Random graphs III: threshold functions, and evolution of random graphs1:28:43Graph Theory, Lecture 28: Random graphs III: threshold functions, and evolution of random graphs
Graph Theory, Lecture 28: Random graphs III: threshold functions, and evolution of random graphs
Просмотров 933 месяца назад
Graph Theory, Lecture 28: Random graphs III: threshold functions, and evolution of random graphs
Graph Theory, Lecture 27: Random graphs II: Erdös's theorem, and properties of almost all graphs1:16:21Graph Theory, Lecture 27: Random graphs II: Erdös's theorem, and properties of almost all graphs
Graph Theory, Lecture 27: Random graphs II: Erdös's theorem, and properties of almost all graphs
Просмотров 803 месяца назад
Graph Theory, Lecture 27: Random graphs II: Erdös's theorem, and properties of almost all graphs
Graph Theory, Lecture 26: Random graphs I: elementary definitions and basic facts1:17:03Graph Theory, Lecture 26: Random graphs I: elementary definitions and basic facts
Graph Theory, Lecture 26: Random graphs I: elementary definitions and basic facts
Просмотров 1033 месяца назад
Graph Theory, Lecture 26: Random graphs I: elementary definitions and basic facts
Graph Theory, Lecture 25: Hamilton Cycles II: overview of Hamiltonicity results and conjectures1:03:46Graph Theory, Lecture 25: Hamilton Cycles II: overview of Hamiltonicity results and conjectures
Graph Theory, Lecture 25: Hamilton Cycles II: overview of Hamiltonicity results and conjectures
Просмотров 833 месяца назад
Graph Theory, Lecture 25: Hamilton Cycles II: overview of Hamiltonicity results and conjectures
Graph Theory, Lecture 24: Hamilton Cycles I: sufficient conditions for existence55:33Graph Theory, Lecture 24: Hamilton Cycles I: sufficient conditions for existence
Graph Theory, Lecture 24: Hamilton Cycles I: sufficient conditions for existence
Просмотров 583 месяца назад
Graph Theory, Lecture 24: Hamilton Cycles I: sufficient conditions for existence