Table of Content

Topics in Discrete Mathematics (Diskrete Strukturen III)

Sommersemester 2026
Stefan Felsner

1. Vorlesung, 14.04.2025

        Order Theory
           Basics of order theory
               graphs related to a poset
               chains and antichains   
           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
           Transitive orientation of graphs
               forcing relation
           Incidence orders of graphs and dimension
               characterizing dimension 2

        Dimension of incidence orders and dimension of graphs
           critical pairs - comparing the two dimension concepts for graphs
           dimension of the complete graph
              HM-antichains in the Boolean lattice
        Dimension of planar graphs
           dim(G) at most 3 implies planarity

           Schnyder's dimension Theorem
              Schnyder woods - definition and existence
              paths and regions of a vertex
              containment orders of i-regions
              the 3-realizer

   
        Dimension of polytopes
           3-polytopes   
           the lower bound
           cyclic polytopes
        Grid drawings of planar graphs
           counting faces in regions
           the empty triangle of a face

        Orthogonal surfaces
           the OS obtained from face counting 
           OS and the Schnyder dimension theorem   
        Schnyder woods of 3-connected planar graphs
           primal-dual Schnyder woods

       Intersection and contact representations of graphs
         Examples: segment intersection graphs, triangle contact graphs
           Circle contact representations (Koebe's Thm.)
         Triangle contact representations from Schnyder woods
         Homothetic triangle contact representations
           Existence and 'monster packing'
           Connection with orthogonal surfaces
           Algorithm using Schnyder woods, linear equations and flips

       The dimension of planar maps
          History of the Brightwell Trotter Theorem
          The split of a poset and the in-place split
          Dimension of grid intersection graphs (GIGs)
          Bipartite planar graphs admit segment contact representations 

          The angle graph of a map
          Putting things together (2-connected maps)
          Dealing with cut vertices and loops
       Squaring a rectangle contact representation 
          Modeling the task with linear equations
          The system is square and non-singular
             Leibniz formula and perfect matchings
          How to deal with negative values in the solution 

      k-sets and k-edges
         alternation lemma + Lovasz Lemma
         the squareroot bound
         crossing lemma 

         Welzel's formula
            convex position
            mutations
            upper bound on  ≤k-sets
               duality - allowable sequences + pseudolines

       The crossing number of the complete graph
          Hill conjecture and Hill optimal drawings
          The Moon construction - randomized drawings on the sphere
          The rectilinear crossing number of Kn 
              (an application of k-set bounds)               

        Maximal plane subdrawings of simple drawings of Kn
            Number of edges
        ES-type questions for simple drawings of Kn
            Empty triangles 

    Tilings
       Domino tilings - rectangles and almost rectangles
       Tilings with Vs (L-Trominos)
    Necessary conditions
        Crit 1: divisibility
        Crit 2: coloring conditions
             tilings with Ts, 4-sticks, and Ls
        Crit 3: homology criterion

             free abelian groups and reductions
             tilings with dominoes
         Tiling Aztec diamonds with Z's
         Crit 4: homotopy criterion
             boundary words and the free group generated by x,y
             a first example