Lehre

Given a graph, we can consider the set of all of its spanning trees. A listing with an interesting property is one in which any two consecutive spanning trees differ only a little bit, for example, in exchanging a single edge, i.e., one edge is removed and another edge is inserted to obtain the next tree. Such a listing of combinatorial objects subject to some minimum-change condition is often referred to as a Gray code.

The goal of this thesis is to pursue questions such as: Are there similar listings for the spanning trees of other graphs? Can we impose even stronger restrictions on the allowed edge exchanges, for example, by exchanging only edges that share a common end vertex? If so, how can such listings be computed efficiently?

For a detailed description, see the following PDF.

The cup-stacking game is a one-person game played on a finite graph G. Initially, a single cup is placed at every vertex of G. Each move consists in removing all cups placed at a single vertex, and if there are k of them, to stack them onto another vertex in distance exactly k, provided that the other vertex already has at least one cup on it. The goal is to move all cups onto a single target vertex t, and the game is a win if this is achieved. If this is possible for every choice of target vertex t in G, then G is called cup-stackable.

The goal of this thesis is to pursue questions such as: For which graphs and target vertices can this game be won? Can we derive necessary and/or sufficient conditions for a graph to be cup-stackable? How do solutions look like that minimize the total number of cups moved during the game? What about vari- ations of the game where the rules of moving cups are slightly changed?

For a detailed description, see the following PDF.

An n-Venn diagram is a diagram in the plane consisting of n simple closed curves, such that every possible intersection pattern between the curves is represented by exactly one region in the plane. The most familiar diagram is the one usually drawn in school for n = 3 curves, but interestingly these diagrams exist also for all larger values of n. A diagram is called simple, if no three curves intersect in any point.

The goal of this thesis is to pursue questions such as: Can we count the number of distinct (simple and non-simple) Venn diagrams for n = 5, 6, 7 curves, possibly with computer help? Can we derive general lower and upper bounds for the number of distinct diagrams as a function of n? Given a simple n-Venn diagram, is it possible to add another curve to turn the diagram into a simple (n + 1)-Venn diagram?

For a detailed description, see the following PDF.

An isomorphism between two graphs G and H is a bijective mapping of the vertices of G to those of H that preserve edges and non-edges. In this project, we fix a graph G, and we ask ourselves if every isomorphism between certain subgraphs (so called induced subgraphs) can be extended to an automorphism of G. In general, there are very few graphs with this property, and they are called ultrahomogeneous.

A relaxation of this concept is the following: we would like to to embed G into a (possibly larger) graph H such that every isomorphism between induced subgraphs of G extends to an automorphism of H. Such a graph H is then called an EPPA witness for G.

Interestingly, this problem has many connections to algebra, in particular, to group theory. The aim of this project is to further explore the existence and structure of EPPA-witnesses. For a detailed description, see the following PDF.

Consider the following problem: n cars want to park, one at a time, on a one way street with n available parking spots. Each car has a preference, i.e. a favourite spot, that it checks first. If that spot is still free, then the car parks there. Otherwise, the car then proceeds forward, parking in the first available spot it finds. If there are no such spots, the car is not able to park.

Lists of preferences such that all cars are able to park are called parking functions, and have been extensively studied in their standard form. However, there are many variations on this simple setup that can be considered.

Depending on the considered variation, many questions can be asked, e.g., how many are the sequences such that all cars are able to park, can you characterize such sequences, and can you list them efficiently? For a detailed description, see the following PDF.

Graph coloring plays a central role in discrete mathematics, and especially in combinatorics. Many everyday problems, such as finding the smallest number of time slots needed for tests, can be modeled as graph coloring problems. Other applications can be found in wireless communication and robot navigation. Here, the colors correspond to a unique assignment of transmission frequencies; especially in the latter case, it is often mandatory that a robot can always assign a transmitter with a unique frequency. This condition is referred to as a conflict-free coloring.

The goal of this thesis is relatively open and can be adapted to the tastes and ideas of the student. For a detailed description, see the following PDF.