Algebraic and probabilistic methods in discrete mathematics

Summer 2022
Stefan Felsner

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 ,

Lecture 1, Tuesday 19.04.2022

Counting Polynomials
   chromatic polynomial
      definition and examples
      first explicit representation
      delete-contract formula
      Whitney representation
Lecture 2, Thursday 21.04.2022
      Stanley reciprocity - evaluation at -1
   flow polynomial
      examples and easy observations
      delete-contract formula
      duality between flows and colorings
      the Tutte conjectures
Lecture 3, Tuesday 26.04.2022
      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
Lecture 4, Thursday 28.04.2022
      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
Lecture 5, Tuesday 03.05.2022
      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 
Lecture 6, Thursday 05.05.2022
      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
Lecture 7, Thursday 12.05.2022
        planar bipartite graphs are 3-choosable
     a second version of CNSS
        application: p-regular subgraphs
	application: F-factors 
Lecture 8, Tuesday 17.05.2022
        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
Lecture 9, Thursday 19.05.2022
        the number of matchings of 3-regular bipartite graphs
     using determinants to evaluate permanents
        Kasteleyn signatures
	planar bipartite graphs admit Kasteleyn signatures
Lecture 10, Tuesday 24.05.2022
     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)
Lecture 11, Tuesday 31.05.2022
     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
Lecture 12, Thursday 02.06.2022
         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])
Lecture 13, Tuesday 07.06.2022
    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
Lecture 14, Tuesday 14.06.2022
       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.  
Lecture 15, Thursday 16.06.2022
    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
Lecture 16, Tuesday 21.06.2022
  Discrete Probability
    Basic Examples
       a p-coin : the geometric distribution
       Coupon Collector's Problem
       cycles and left-right maxima of permutations
         2 proofs for the expectation
Lecture 17, Thursday 23.06.2022
    Tail estimates for left-right maxima
       Markov inequality
       Chebyshev inequality
       higher moments
    Randomized quick-sort
       random tree-sort
Lecture 18, Tuesday 28.06.2022
    Randomized linear programming
         divide & conquer for 2-dimensional convex hull
         the bridge problem
         bridge is a LP in 2 variables
       LP via random sampling  
Lecture 19, Thursday 30.06.2022
        the sampling lemma revisited
      random incremaental LP
      LP via randomized reweighting
      LP via prune & search
Lecture 20, Tuesday 05.07.2022
    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
Lecture 21, Thursday 07.07.2022
    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
Lecture 22, Tuesday 12.07.2022
    Random spanning trees
      Markov chain tree theorem
        reversible chains
	first entrance trees
     spanning trees via cycle erasure
        Wilson's algorithm
Lecture 23, Thursday 14.07.2022
        the cycle popping variant of Wilson's
	the distribution on the output trees
	the expected number of random edges
Lecture 24, Tuesday 19.07.2022
     Markov chains
        ergodic chains
	total variational distance
	rapid mixing
	techniques to bound mixing time
	  eigenvalues; conductance; congestion
Lecture 25, Thursday 21.07.2022
	  the coupling lemma
	the Bubley-Dyer chain for linear extensions  

Zurück zur Vorlesungsseite.