Spring 2019 - Period 3

Combinatorial Structures (in Graph Theory)

Tero Harju


There are various methods to decompose coloured graphs. Decompositions of combinatorial and algebraic structures are special cases of the divide-and-conquer method, where a large problem is partitioned into smaller ones, and a method is given to link solutions of the subproblems to a solution of the original one. The clan decomposition (modular or substitution decomposition), is a structural result on general graphs related to the decomposition by quotients in algebra. The lectures are divided into a `static' and 'dynamic' parts. The static part is concerned with the decomposability and primitivity. The key notion is that of a clan - a subset of vertices that cannot be distinguished from each other by the outsiders. The `dynamic' part studies the local transformation of switching. The set of labels of the edges is given a group structure. In this way one obtains switching classes of graphs.

Lectures

Exercises


LECTURES

Tuesday 10-12 Room M1
Wednesday 14-16 Room M3

EXERCISE CLASSES

Thursday 12-14 Room M1

FIRST EXAM: Thursday 21st, February, 12-14 Room M1


Lecture Notes:

Combinatorial Structures in Graph theory



See also my links for graph theory

Slides:

Introduction
Small primitive subgraphs
Hereditary primitivity
Beginnings of Switching
Groups Z_4 and S_3
Quotients of Switching classes
Automorphisms
Eulerian graphs
Hamiltonian graphs
Trees and acyclic graphs

Exercises

Problem Set 1 (Solutions)
Problem Set 2 (Solutions)
Problem Set 3 (Solutions)
Problem Set 4 (Solutions)
Problem Set 5 (Solutions)


Department of Mathematics and Statistics