Inhaltsverzeichnis

Algebraic and probabilistic methods in discrete mathematics

Summer 2022
Stefan Felsner

Lecture 1, Tuesday 19.04.2022

Counting Polynomials
   chromatic polynomial
      definition and examples
      first explicit representation
      delete-contract formula
      Whitney representation

      Stanley reciprocity - evaluation at -1
   flow polynomial
      examples and easy observations
      delete-contract formula
      duality between flows and colorings
      the Tutte conjectures

      two theorems of Jaeger about nowhere zero flows
   The Tutte polynomial
      recursive definition
      the rank polynomial
       TG(x,y) = RG(x-1,y-1)
      some evaluations
      the receipt theorem

      proof of the receipt theorem
      the chromatic polynomial in terms of the Tutte polynomial
      internal and external activity
      a partition of the Boolean lattice
      The Tutte polynomial in terms of activities

      proof of the partition lemma
Kombinatorischer Nullstellensatz
   colorings, orientations, and polynomials
      the graph polynomial fG
      fG as sum of weights of digraphs
      the role of out-degree sequences 

      bijection between eulerian subgraphs of D and
         orientations with the same out-degree sequence as D
      the Alon Tarsi Theorem
         main lemma: combinatorial Nullstellensatz (CNSS)
         first applications of Alon Tarsi

        planar bipartite graphs are 3-choosable
     a second version of CNSS
        application: p-regular subgraphs
	application: F-factors 

        the permanent lemma
	Erdös-Ginzburg-Ziv theorem
  Permanents, determinants and matchings
        determinants, permanents and derangements
     evaluating permanents in O(poly(n)*2^n) time
     important results about permanents

        the number of matchings of 3-regular bipartite graphs
     using determinants to evaluate permanents
        Kasteleyn signatures
	planar bipartite graphs admit Kasteleyn signatures

     Domino tilings and rhombic tilings of some shapes
     domino tilings of the Aztec Diamond
        a recursion formula based on superposition of matchings
	K-subgraphs and their cycles (K stands for Kuo)

     Frieze patterns of integers
         the diamond rule
	 frieze patterns from triangulations of the n-gon
	 a formula for products of matchings in planar bipartite graphs
	   a proof using K-graphs

         frieze patterns from determinants and
	 Dogson's condensation formula
     A q-analog of McMahon's formula
       plane partitions and rhombic tilings
       superposition of matchings in the hexagonal lattice
       (Graphical Condensation and Plane Partitions - Eric Kuo 2004 [slides])

    Rhombic tilings of a 2n-gon and arrangements
       tilings induce arrangements
       sweeping arrangements and implications
          left-to-right is acyclic
       stretchability and Pappus
       stretchability and counting
          THM Oleinik-Pertovskii | Milnor-Thom | Warren

       review on rhombic tilings and arrangements
       triangle orientations encode arrangements
          local sequences encode arrangements
	  local binary sequences encode arrangements
       an upper bound on Bn = # arr of n pseudolines
       a lower bound on Bn
       improved lower bound via McMahon formula
       an upper bound on  # arr of n lines via Warren's Thm.  

    Triangles in arrangements
       Levi's Thm. triangles in projective arrangements
       Shannon's Thm. triangles in line arrangements
         the n-2 bound in the pseudo-setting
	 Belov's proof using determinants and moving lines

  Discrete Probability
    Basic Examples
       a p-coin : the geometric distribution
       Zauberzeile
       Coupon Collector's Problem
       cycles and left-right maxima of permutations
         2 proofs for the expectation

    Tail estimates for left-right maxima
       Markov inequality
       Chebyshev inequality
       higher moments
    Randomized quick-sort
       random tree-sort

    Randomized linear programming
       motivation 
         divide & conquer for 2-dimensional convex hull
         the bridge problem
         bridge is a LP in 2 variables
       LP via random sampling  

        the sampling lemma revisited
      random incremaental LP
      LP via randomized reweighting
      LP via prune & search

 
    Lovasz Local Lemma
      random assignments for k-SAT formulas
      bounded dependency and LLL
      Mosers entropy compression argument
         the recursive algorithm 
	 the data in the LOG
	 retreiving random bits from the LOG

 
    Random spanning trees I
       uniform spanning tree via matrix tree theorem
    Random walks on graphs
       stationary distribution
       hitting times
       path, clique and lollipop
       cover times

 
    Random spanning trees
      Markov chain tree theorem
        last-exit-tree
        reversible chains
	first entrance trees
     spanning trees via cycle erasure
        Wilson's algorithm

 
        the cycle popping variant of Wilson's
	the distribution on the output trees
	the expected number of random edges

 
     Markov chains
        ergodic chains
	total variational distance
	rapid mixing
	techniques to bound mixing time
	  eigenvalues; conductance; congestion

 
        couplings
	  the coupling lemma
	the Bubley-Dyer chain for linear extensions