-
Tue 10.04.2012: Examples; graph properties and invariants;
strongly regular graphs; Laplacian drawings
lecture slides
-
Thu 12.04.2012: Graph isomorphism as a computational problem;
coding issues; reduction from labeled graph isomorphism to plain graph
isomorphism; reduction of the construction problem to the decision problem
-
Tue 17.04.2012: Reduction to connected graphs; complete
invariants and canonisation; colour refinement: definitions and examples
-
Thu 19.04.2012: Stable equivalence relations; the bijective
pebble game; colour refinement identifies trees and forests
-
Tue 24.04.2012: Colour refinement in time O((n+m)log n)
-
Thu 26.04.2012: Random graphs; colour refinement distinguishes almost
all graphs
-
Tue 8.5.2012: A linear program for graph isomorphism and
fractional isomorphism;
equivalence between fractional isomorphism and colour refinement; proof of easy direction
-
Thu 10.5.2012: Background from linear algebra: components of a
matrix; eigenvectors of doubly stochastic matrices
-
Tue 22.5.2012: Proof that the existence of a solution to the LP
implies indistinguishability by colour refinement
-
Thu 24.5.2012: The basic individualisation-refinment algorithm
-
Tue 29.5.2012: Pruning the search tree using automorphisms
-
Thu 31.5.2012: tree decompositions; 3-connected components of a graph
-
Tue 5.6.2012: lifting canonisations from the 3-connected
components to the whole graph; plane and planar graphs
-
Thu 7.6.2012: rotation systems; strong canonisation of
3-connected planar graphs; other classes with a polynomial time isomorphism test
- Tue 12.6.2012: isomorphism complete classes; partial
isomorphisms and atomic types; the Weisfeiler Lehman algorithm
- Thu 14.6.2012: basic facts about the Weisfeiler Lehman
algorithm
- Tue 19.6.2012: the bijective k-pebble game
- Thu 21.6.2012: the logik Ck; the power of the
Weisfeiler-Lehman algorithm
- Tue 3.7.2012: background from group theory
Last modified: Fri Mar 30 00:23:35 CEST 2012
