# 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
```
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
Zauberzeile
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
motivation
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
last-exit-tree
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
```
couplings
the coupling lemma
the Bubley-Dyer chain for linear extensions
```

Zurück zur Vorlesungsseite.