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 ,

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 polynomialTsome evaluations the receipt theorem_{G}(x,y) = R_{G}(x-1,y-1)

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 polynomialf_{G}fas sum of weights of digraphs the role of out-degree sequences_{G}

bijection between eulerian subgraphs ofDand orientations with the same out-degree sequence asDthe 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 inO(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 onB= # arr of_{n}npseudolines a lower bound onBimproved lower bound via McMahon formula an upper bound on # arr of_{n}nlines 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

Zurück zur Vorlesungsseite.