Inhaltsverzeichnis

Graphentheorie

Wintersemester 2021/22
Stefan Felsner

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
      

       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

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

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

          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
 

        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

           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

           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
	      arborescences
	      reduction to digraphs with outdeg(v) = 1 for all v

     Eulerian paths and cycles
        Memory Wheels 
           The deBruijn Graph Bn(m)
        BEST Theorem 
           Counting eulerian cycles in directed graphs

        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

       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

      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

     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

   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 of R(k,k) via induced colorings
       Existence of R(k,k) by induction, binomial coefficients
       Probabilistic lower bound

     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

         K5 and K3,3 are non-planar
         Dual Graphs
         Proofs of Euler's formula
	    dual trees
	    induktion 
	    angle sums 

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

           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

      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

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

         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

     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

        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)

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

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

          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

          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
  

          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
  

        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
  

        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       

        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

  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