Inhaltsverzeichnis / Content

Graphentheorie

Wintersemester 2023/24
Stefan Felsner

Lecture 1, Mo. 16.10.2023

    3 trigger problems     
    Basics
          what is a graph?
          examples of graphs
          iso- and other morphisms
          how many graphs?
      Solution of problem I
      

       Why graph theory ?
       Handshaking 
    Solution of problem II
       Geometric graphs without disjoint edges
       Topological graphs, Thrackles
       Problems from discrete geometry:
          diameters, unit distances

    Solution of problem III
       Rigid grids: paralell classes of edges - connectivity of auxiliary graph
       Graph rigidity in the plane - Laman density condition    
    Degree sequences
       Charakterization of Havel and Hakimi
       The flip-graph of 2-switches
       Thm. of Erdös-Gallai
    Paths and cycles
       Distances

     Defense of Felix Schröder: 14:00 sharp in Villa BEL third floor.

       Connectivity
         vertex- and edge-connectivity 
         Κ(G) vs Κ'(G)
         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
          2 algorithmic proofs for their existence
          a glimpse on matroids
 

          a glimpse on search trees [DFS/BFS]
        BridgeIt
           The game
           A winning strategy based on spanning trees
        Cayley' Theorem on the number of trees
           Proof 1. Prüfer; a bijection between trees and Prüfer codes
           Proof 2. Clarke; refined counting and recursion

           Proof 3. Pitman; twofold counting of chains of rooted forests
	   Proof 4. Joyal; A bijection involving the cycle-forests of maps [n] to [n]
	F2 vector spaces of graphs
	   F2 orthogonality
	   vertex and edge space
	   cut and cycle space
           fundamental bases of cut and cycle space

         Turán's Theorem
            Proof 1: optimization - shifting weights
            Proof 2: short induction
            Proof 3: the 3 vertex property
            - characterizing maximizing examples
         Extremal functions ex(n,H)

         Functions from Adjacency matrices
         Graph Limits
         Triangle Removal Lemma

         Triangles in dense graphs
         Furedi stability theorem
         Theorems of Erdös-Stone and Erdös-Simonovits
      An inequality for the independence number α (Wei Inequality)
         proof: analyzing Algo MIN

        More about the Wei inequality:
         2. proof: analyzing Algo MAX
         3. proof: random permutations
         Turán as a consequence of Wei  
   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
    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)

      Matrix-Tree Theorem
           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 and de Bruijn graphs

        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 closure
       Hamiltonian cycles in squares of trees

    Gray-codes for combinatorial structures
       The classical Gray-code for 01-vectors
         ranking and unranking
         additional requirements
       Zig-zag permutation languages
         Algorithm J
         Instances of Alg J: 01-vectors, Catalan

   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
        Coloring planar graphs with 6 colors
        Coloring planar graphs with 5 colors
            Kempe chains

        The "Art Gallery Problem"
           Kempe's "proof" of the 4-color theorem
        Ideas for the proof of the 4-color theorem
           Unavoidable sets - discharging
           Reducible configurations - recoloring

      Theorems of Kuratowski and Wagner
            Proof of the Kuratowski Theorem
               Contractible edges in 3-connected graphs
               Subdivision lemma

     Whitney's Theorem (unique embedding)
     Hanani-Tutte Theorem (independent odd crossings)
         Transforming drawings
	 The z-vector of a drawing
	 The affine space of drawings 
	 The affine spaces of subdivisions of K5 and K3,3

     Crossing numbers
        topological and straight
        conjectures for cr(Kn) and cr(Kn,m) 
        bounds
        The Crossing Lemma

         Unit distances - an application of the crossing lemma
         Moon's probabilistic proof for drawings of Kn with few crossings
     Charakterizations of planar graphs
     Dimension of Graphs
     Schnyder's dimension theorem

       Schnyder Woods
        The three trees Ti
        Regions
        Inclusion order of regions
        a 3-realizer

       Straight line drawings 
          reinserting vertices of degree at most 5
          resolution and grid drawings
          nested triangles
          counting faces in regions of Schnyder woods
             the triangle of an edge
     Perfect graphs
          ω-perfectness and α-perfectness
          odd cycles and holes
          classes of perfect graphs
          interval graphs

       Maximum Weight Independent Set on Trees
       Maximum Weight Matching on Trees
       Dynamic Programming
       Pathwidth of a graph

       Maximum Independent Set on graphs with bounded pathwidth
       Treewidth of a graph
       Cops and Robber with helicopters

      Greedy colorings
      Bounding  χ by Δ and by degeneracy
      Bounding  χ by pathlength in orientations (Gallai-Roy)
      Brook's Theorem
         Case 1: a vertex of small degree

       Brook's Theorem
         Case 2:  Δ regular graphs
       Edge-Colorings
       Vizing's Theorem

    List coloring
       List chromatic number of bipartite graphs  
       Planar graphs (Thomassen's theorem)

    Fractional chromatic number
       χ as an integer program
       relaxation and integral gap
       f-chromatic number and b-chromatic number
       Kneser graphs
       f-chromatic number of Kneser graphs
       chromatic number of Kneser graphs (topol. argument)