Stefan Felsner

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 . 32 ,

**Lecture 1, Th. 21.10.2021 **

Youtube recording

3 trigger problems Introduction Fundamental definitions iso- and other morphisms types of subgraphs examples of graphs Solution of problem I

Youtube recording part 1 (62 min)

Youtube recording part 2 (26 min)

Cycle free graphs Solution of problem II Geometric graphs without disjoint edges Topological graphs, Thrackles Solution of problem III Rigid grids: paralell classes of edges - connectivity of auxiliary graph

Youtube recording - no audio

Degree sequences Charakterization of Havel and Hakimi The flip-graph of 2-switches Thm. of Erdös-Gallai Paths and cycles

Youtube recording

Distances Connectivity vertex- and edge-connectivityΚ(G)vsΚ'(G)The Theorem of Menger proof of the u-v variant

Youtube recording

The classical Menger's Theorem 8 variants of Menger's Theorem Ford-Fulkerson and König-Egervary Trees and Forests Characterizations of trees Spanning trees 3 algorithmic proofs for their existence

Youtube recording

BridgeIt The game A winning strategy based on spanning trees Cayley' Theorem on the number of trees Proof 1. Pitman; twofold counting of chains of rooted forests Proof 2. Clarke; refined counting and recursion

Youtube recording - audio dies 13 minutes before end

Proof 3. Prüfer; a bijection between trees and Prüfer codes Proof 4. Joyal; A bijection involving the cycle-forests of maps [n] --> [n]F_{2}vector spaces of graphsF_{2}orthogonality vertex and edge space cut and cycle space fundamental bases of cut and cycle space

Youtube recording

Lights-Off; an application ofF_{2}vector spaces Matrix-Tree Theorem Sketch of the proof via the Cauchy-Binet determinant formula Proof of the Matrix-Tree Theorem for digraphs arborescences reduction to digraphs withoutdeg(v) = 1for allv

Youtube recording

Eulerian paths and cycles Memory Wheels The deBruijn GraphBBEST Theorem Counting eulerian cycles in directed graphs_{n}(m)

Youtube recording

The number of eulerian cycles in deBruijn Graphs Eigenvalue version of the matrix tree theorem Path of lengthninBThe eigenvalues of the Laplacian of_{n}(m)BHamilton cycles The icosian game Dirac's theorem_{n}(m)

Youtube recording

Theorem of Erdös-Chvatal The hamiltonian closre Hamiltonian cycles in squares and cubes of trees Extremal graph theory Four fundamental parameters Mantel's theorem

Youtube recording

Turán's Theorem Proof 1: optimization - shifting weights Proof 2: short induction Proof 3: the 3 vertex property - characterizing maximizing examples Triangles in dense graphs Extremal functionsex(n,H)Theorems of Erdös-Stone and Erdös-Simonovits

Youtube recording

ex(n,CAn inequality for the independence number α The Wei inequality Two weakenings and Turán again 1. proof: random permutations 2. proof: analyzing Algo MAX 3. proof: analyzing Algo MIN_{4}) = O(n^{3/2})

Youtube recording

Ramsey Theory Monotone subsequences (Erdös Szekeres) Breaklines in domino tilings of the 6x6 board Theorems of Schur / van der Waerden / Ramsey (Ein Beitrag zu den Sätzen von Schur, Ramsey und Fermat: video) Graph-Ramsey Existence ofR(k,k)via induced colorings Existence ofR(k,k)by induction, binomial coefficients Probabilistic lower bound

Youtube recording

Which Ramsey numbers are known? The general set Ramsey numbers:RApplications of Ramsey numbers: The Happy Ending Problem (convex subsets) Esther Klein Lemma Theorem of Erdös Szekeres_{k}(t;n_{1},..,n_{t})N(n) < R_{4}(5,n)N(n) < RPlanar Graphs Drawings, crossings, the Jordan curve theorem_{3}(n,n)

Youtube recording

Kand_{5}Kare non-planar Dual Graphs Proofs of Euler's formula dual trees induktion angle sums_{3,3}

Youtube recording

Implications of Euler's formula The "Art Gallery Problem" Crossing numbers topological and straight bounds The Crossing Lemma

Youtube recording

Unit distances - an application of the crossing lemma Moon's probabilistic proof for drawings ofKwith few crossings Theorems of Kuratowski and Wagner Proof of Kuratowski 3 connectivity lemma subdivision lemma_{3}n

Youtube recording

Whitney's Theorem (unique embedding) Hanani-Tutte Theorem (independent odd crossings) Transforming drawings Thez-vector of a drawing The vector space of drawings The vector spaces ofKand_{5}K_{3,3}

Youtube recording

Kissing coins representations of planar triangulations (Koebe's Theorem) Radii and angles The iteration and its convergence Laying out the triangles Separator theorems

Youtube recording

Centerpoints of point sets The cups and belts of a circle representation Expected size of a separator An application of small separators: max weighted matching Two lemmas about weight increasing alternating paths The running time

Youtube recording

Planar drawings on linear size grids Schnyder woods on triangulations Definition and existence Trees and regions Barycentric coordinates Chromatic numbers Alternative definitions Two lower bounds

Youtube recording

Graphs with no triangle and large χ - further constructions Mycielski-Construction Split-graphs The expected χ of random graphs Upper bounds Greedy colorings Bounding χ by Δ and by degeneracy Bounding χ by pathlength in orientations (Gallai-Roy)

Youtube recording

Geometric intersection graphs χ-boundedness interval graphs and square graphs rectangle intersection graphs (Asplund-Grünbaum) Intersection graphs of pseudodisks

Youtube recording

Line graphs and edge colorings Examples Matchings : Theorem of Kőnig-Egerváry Chromatic index of bipartite graphs (Kőnig) Perfect graphs

Youtube recording

Vizing's Theorem Theorem of Tait Connection to Hamiltonicity Counterexample of Tutte List colorings Lower and Upper Bounds Example: Bipartite graphs Survey of results on planar graphs

Youtube recording

Planar graphs Upper bound of 5 (Thomassen) Lower bound of 5 (Mirzakhani) Kernels Some remarks on stable matchings Galvin's Theorem: List-edge colorings of bipartite graphs

Youtube recording

Stable matchings: Gale-Shapley Theorem Galvin's Theorem: wrap-up Fractional chromatic number (A book: Fractional Graph Theory by Scheinerman and Ullman) b-colorings Fractional chromatic number χ_{f}odd cycles lower bounds b-cliques and fractional clique number ω_{f}

Youtube recording

Chromatic and clique numbers via 0-1 programs LP-relaxation and duality χ_{f}= ω_{f}Bounding the integrality gap: χ <= (1+ln α)χ_{f}Colorings and homomorphisms Kneser graphs Fractional chromatic number of Kneser graphs

Youtube recording

A connection (equivalence) with the Erdös-Ko-Rado Theorem Chromatic number of Kneser graphs (a topological argument) Perfect graphs The bipartite collection: 4 fundamental classes of perfect graphs

Youtube recording

The Berge conjectures Chordal graphs clique separators - simplicial vertices - tree representation - perfect elimination ordering perfectness The perfect graph theorem ω-perfectness - α-perfectness - product perfectness minimally imperfect graphs

Youtube recording

Tree width Tree decompositions and tree width Tree width as max clique of chordal supergraph Tree width as value of the Robber and Cops game tree width of grids Algorithmic implications 3-colorability for graphs of bounded tree width Courcelle's Theorem Minors and the Graph Minor Theorem

Zurück zur Vorlesungsseite.