Table of Content

Graphen, Ordnungen und Geometrie (Diskrete Strukturen III)

Sommersemester 2024
Stefan Felsner

1. Vorlesung, 16.04.2024

       Intersection graphs
         interval graphs
            α=Θ (greedy left to right independent set)
            χ=ω (greedy left to right coloring)
         unit squares Θ≤2α and χ≤2ω
         squares -- intersection graph is 4(ω-1) degenerate
            Θ≤4α and χ≤4ω-3

         rectangle intersection graphs
            the Asplund-Grünbaum bound: χ≤4ω²-3ω
         intersection graphs of pseudodiscs
            the union complexity 
            the coloring bound: χ≤19ω

         triangle-free graphs with large chromatic number
            classical constructions
            bounds on χ in terms of number of vertices
            segment intersection graphs 
              the construction of Pawlik et al.
       χ-boundedness
            examples and questions  
            circle graphs

     Coloring circle graphs
        Basics: circle and overlap graphs
           permutation graphs
        James Davies: Improved bounds for colouring circle graphs
           arxiv.org/pdf/2107.03585.pdf  
           coloring on the basis of pillars

          adding pillars to an arc
             binary tree order
          subdivided arc and color intervals - a poset
     Approximation algorithms for α
        segments stabbed by a line 

           a sqrt(α) approximation by dynamic progr.
        general segments
           divide and conquer with the median line
           levels in the recursion tree
        rectangles
           the crossing graph G

           computing a max indep set S in G
           computing a 2-maximal indep set I in S
           comparing |I| with a maximum indep set J 
      Geometric representations of planar graphs
         Drawings
           Force directed embeddings
              the energy of an embedding
              energy is strongly convex

             energy minimization as a linear system
               digression: discrete analytic functions
             each vertex in strict convex hull of neighbours
             anglesums allow no surplus
             the embedding is planar 

         Circle packing (kissing coins representation)
            radii imply angles
            iteration with increasing radii
            non-divergence
            the embedding
            primal-dual circle packings     

         Planar separator theorem (application of circle packing)
            lifting circles to the sphere
            centerpoints
            areas of cups and belts
            a random plane through 0 is expected to hit few circles
         Max weighted matchings via separators
            augmenting paths
            a divide and conquer algorithm

         Triangle contact representations
            Schnyder woods
            A simple layout algorithm
            Homothetic triangles
               the problem with separating triangles
               stacked triangulations
            Bijection Schnyder woods - 3-orientations   

           The lattice of α-orientations
              Existence of α-orientations and Hall condition
              Rigid edges
              flips-flops and facial cycles
              potentials

              Bijection between α-potentials and α-orientations
              The lattice of α-potentials
           Linear equations for homothetic triangles
              The matrix A and a bipartite graph
              det(A) as a sum over perfect matchings
              Kasteleyn theorem and non-degeneracy

             negative values and their directed cycles
             flipping and iterating
          Linear equations for squarings
             rectangulations and separating decompositions

             the matrix, the graph, det and perfect matchings
             a single flip suffices for a non-negative solution
          Kasteleyn signatures exist for planar bipartite graphs

          Cartograms
             [recommended visit: WorldMapper] 
             Three equivalence relations for rectangulations
             Weak equivalence class is area universal
                uniqueness of an area representation

                existence via inverse mapping
             Applications:
                Mapping segments of a rectangulation to points
                Rectilinear cartograms of triangulations via Schnyder woods
                [example: polution Europe]

        Order Theory
           Linear extensions and dimension
               linear extensions exist
               realizer and dimension
               dimension and embeddings - Ore definition
               dimension of Boolean lattice
                  standard examples

           2-dimensional orders
               conjugate order
               non-separating linear extension
           critical pairs and alternating cycles
           dimension and hypergraph coloring

        Dimension of incidence orders and dimension of graphs
           incidence relations and their graphs
           comparing the two dimension concepts for graphs
           dimension of the complete graph
           dimension of polytopes, lower bound [pdf]

        Dimension of planar maps
           splits and their dimension
           grid intersection graphs (GIG) and their dimension
           the angle graph of a map
           setting things together (2-connected maps)

     Greene-Kleitman Theory
        notation and the 5 theorems
        sketch of the proof via min-cost-flow
        k-antichains and antichains in P x [k]

         Viennot's approach to Greene-Kleitman theory for 2 dimensional orders
           Young Tableaux
           Robinson-Schensted correspondence
           jump lines and skeleton points
           proof of the properties of Young tableaux

           computing maximum l-antichain of X
               using maximum l-antichain of S(X)
           computing maximum k-chain of X
               using maximum (k-1)-chain of S(X)

        Two Poset Polytopes
           the order polytope
              vertices
              simplicial partition 
              volume
           the chain polytope
              vertices
           a map between the polytopes
              Stanley's Theorem

           convex corners and antiblockers
           the antiblocker of the chain polytope 
               is the antichain polytope
           liner extensions of 2-dim posets, an ineqiality
           Siderenko's inequality
               proof via network an flow
        Counting linear extensions
           hardness and easy cases