Abstracts of lectures
on Combinatorial Counting
Back
to course homepage.
11.3. 2001
Motivating examples, I
Combinatorial counting,
the permanent and the determinant,
graph polynomials,
generating functions of graph properties.
18.3. 2001
Models of Computation, I
The class #P (Turing machines),
The (non-uniform) classes VP and VNP over fields F
(Algebraic circuits)
Register machines over a field or a ring
(Blum-Shub-Smale computing)
25.3. 2001
Complete problems for #P
The hamiltonian and the permanent
Counting solutions of 3COL and 3SAT
1.4. 2001
Complete problems for VNP
PESACH
15.4. 2001
The Tutte polynomial, I
Basic properties
Special instances
22.4. 2001
The Tutte polynomial, II
Tutte-Grothedieck invariants of graphs
Colored Tutte polynomials
Rank generating polynomials
29.4. 2001
The Tutte polynomial, III
Complexity of graph polynomials
The Tutte polynomial is almost always hard to evaluate
6.5. 2001
An excursion into knot theory
Basic knot theory
Combinatorial knot invariants
Jones polynomial and Kauffman brackets
13.5. 2001
Graphs of bounded tree width
Basic on tree width
Dynamic programming on graphs of bounded tree width
Combinatorial counting on graphs of bounded tree width
20.5. 2001
Splitting formulas for graph polynomials
Shavuoth
3.6. 2001
More on the permanent, I
10.6. 2001
More on the permanent, II
17.6. 2001
Approximation algorithms: Tutte polynomial
24.6. 2001
Approximation algorithms: Permanent