Temata diplomovych praci

Martin Loebl

1. Optimization in Sociology: Median of partitions. The aim is to study the problem to find a median of given set-partitions, with respect to a given distance. Such problems appear in Sociology and Biology, but it turns out that some natural graph theoretic and matroidal questions can be formulated in this language (1 student).

2. Discrete Applied Mathematics: Theory of Kasteleyn orientations. This theory started in the 1960's by a seminal result of Kasteleyn about enumeration of perfect matchings of planar graphs. At present, this theory is applied in many diverse areas, e.g., statistical physics, graph colorings, algorithms and complexity, knot theory and spin networks, quantum computing (2 students).

2. Bioinformatics: The role of repeats in DNA. DNA contains families of repeats, whose function is unclear. The aim is to study repeats with methods of graph theory, and also to do computer experiments towards understanding the repeats (1 student).

2. Discrete Optimisation: generation of random objects The topic aims to include some global conditions in optimisation by combining optimisation and random generation methods, for practical problems.

2. Graph Theory: Directed Cycle Double Covers The aim is to study a well-known conjecture, if any 2-connected graph has a directed cycle double cover. (2 students).