Wintersemester 2021/22
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     
       Fundamental definitions
          iso- and other morphisms
          types of subgraphs
          examples of graphs
      Solution of problem I
Lecture 2, Fr. 22.10.2021
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
Lecture 3, Th 28.10.20121
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
Lecture 4, Fr 29.10.2021
Youtube recording
         vertex- and edge-connectivity 
         Κ(G) vs Κ'(G)
         The Theorem of Menger
           proof of the u-v variant
Lecture 5, Th 04.11.2021
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
Lecture 6, Fr 05.11.2021
Youtube recording
           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
Lecture 7, Th 11.11.2021
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]
	F2 vector spaces of graphs
	   F2 orthogonality
	   vertex and edge space
	   cut and cycle space
           fundamental bases of cut and cycle space
Lecture 8, Fr 12.11.2021
Youtube recording
           Lights-Off; an application of F2 vector spaces
      Matrix-Tree Theorem
           Sketch of the proof via the Cauchy-Binet determinant formula
	   Proof of the Matrix-Tree Theorem for digraphs
	      reduction to digraphs with outdeg(v) = 1 for all v
Lecture 9, Th 18.11.2021
Youtube recording
     Eulerian paths and cycles
        Memory Wheels 
           The deBruijn Graph Bn(m)
        BEST Theorem 
           Counting eulerian cycles in directed graphs
Lecture 10, Fr 19.11.2021
Youtube recording
        The number of eulerian cycles in deBruijn Graphs
	   Eigenvalue version of the matrix tree theorem
	   Path of length n in Bn(m)
	   The eigenvalues of the Laplacian of Bn(m)
   Hamilton cycles
       The icosian game
       Dirac's theorem
Lecture 11, Th 25.11.2021
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
Lecture 12, Fr 26.11.2021
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 functions ex(n,H)
      Theorems of Erdös-Stone and Erdös-Simonovits
Lecture 13, Th 02.12.2021
Youtube recording
     ex(n,C4) = O(n3/2)
   An 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
Lecture 14, Fr 03.12.2021
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)  
       Existence of R(k,k) via induced colorings
       Existence of R(k,k) by induction, binomial coefficients
       Probabilistic lower bound
Lecture 15, Th 09.12.2021
Youtube recording
     Which Ramsey numbers are known?
     The general set Ramsey numbers: Rk(t;n1,..,nt)
     Applications of Ramsey numbers: The Happy Ending Problem (convex subsets)
         Esther Klein Lemma
         Theorem of Erdös Szekeres
            N(n) < R4(5,n)
            N(n) < R3(n,n)
   Planar Graphs
        Drawings, crossings, the Jordan curve theorem
Lecture 16, Fr 10.12.2021
Youtube recording
         K5 and K3,3 are non-planar
         Dual Graphs
         Proofs of Euler's formula
	    dual trees
	    angle sums 
Lecture 17, Th 17.12.2021
Youtube recording
        Implications of Euler's formula
        The "Art Gallery Problem"
        Crossing numbers
           topological and straight
	   The Crossing Lemma
Lecture 18, Fr 17.12.2021
Youtube recording
           Unit distances - an application of the crossing lemma
	   Moon's probabilistic proof for drawings of K3n with few crossings
        Theorems of Kuratowski and Wagner
           Proof of Kuratowski
           3 connectivity lemma
	   subdivision lemma
Lecture 19, Th 06.01.2022
Youtube recording
      Whitney's Theorem (unique embedding)
      Hanani-Tutte Theorem (independent odd crossings)
         Transforming drawings
	 The z-vector of a drawing
	 The vector space of drawings 
	 The vector spaces of K5 and K3,3
Lecture 20, Fr 07.01.2022
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
Lecture 21, Th 13.01.2022
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
Lecture 22, Fr 14.01.2022
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
Lecture 23, Th 20.01.2022
Youtube recording
        Graphs with no triangle and large χ - further constructions
	The expected  χ of random graphs
	Upper bounds
	   Greedy colorings
	   Bounding  χ by Δ and by degeneracy
           Bounding  χ by pathlength in orientations (Gallai-Roy)
Lecture 24, Fr 21.01.2022
Youtube recording
      Geometric intersection graphs
          interval graphs and square graphs
          rectangle intersection graphs (Asplund-Grünbaum)
          Intersection graphs of pseudodisks
Lecture 25, Th 27.01.2022
Youtube recording
      Line graphs and edge colorings
          Matchings : Theorem of Kőnig-Egerváry
          Chromatic index of bipartite graphs (Kőnig)
          Perfect graphs
Lecture 26, Fr 28.01.2022
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
Lecture 27, Th 03.02.2022
Youtube recording
          Planar graphs
             Upper bound of 5 (Thomassen)
             Lower bound of 5 (Mirzakhani)
          Some remarks on stable matchings
	  Galvin's Theorem: List-edge colorings of bipartite graphs
Lecture 28, Fr 04.02.2022
Youtube recording
          Stable matchings: Gale-Shapley Theorem
	  Galvin's Theorem: wrap-up
     Fractional chromatic number
	  (A book: Fractional Graph Theory by Scheinerman and Ullman)
	  Fractional chromatic number χf
          odd cycles
	  lower bounds
          b-cliques and fractional clique number ωf
Lecture 29, Th 10.02.2022
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
Lecture 30, Fr 11.02.2022
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       
Lecture 31, Th 17.02.2022
Youtube recording
        The Berge conjectures
        Chordal graphs
           clique separators - simplicial vertices -    
           tree representation - perfect elimination ordering
        The perfect graph theorem
	   ω-perfectness - α-perfectness - product perfectness
	   minimally imperfect graphs
Lecture 32, Fr 18.02.2022
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.