Lehre

In der Vorlesung werden grundlegende Fragestellungen der diskreten Mathematik behandelt. Themen sind u.a. das Abzählen diskreter Mengen und Strukturen mittels verschiedener Techniken, das Auflösen von Rekursionen, asymptotische Abschätzungen, Kombinatorik, sowie eine Einführung in die Graphentheorie.

Die Vorlesung ist für Bachelor- und Lehramtstudenten als Vertiefung im Bereich diskrete Mathematik bzw. angewandte Mathematik geeignet. Voraussetzung ist Vertrautheit mit grundlegenden mathematischen Konzepten.

Link zur Moodle-Seite

Aufbauend auf den Inhalten der Veranstaltung Elementare Lineare Algebra werden weiterführende Konzepte der linearen Algebra wie beispielsweise Eigenwerte und Eigenvektoren, Diagonalisierung von Matrizen, und Bilinearformen behandelt.

Link zur Moodle-Seite

This seminar covers various topics in discrete mathematics such as graph theory, discrete geometry, and related topics. We will provide scientific articles from which the students should choose one, read and understand it, and then present the content in a seminar talk. You also attend the seminar talks of the other participants.

The talks should be given in English (if this is a problem, we can discuss individual exceptions). You also have to submit a report on your topic, which will then be graded.

Link to the associated moodle page

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 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 numbered 1, . . . , n. Each car has a preference, i.e., a favourite spot, that it checks first. If that spot is not occupied by any of the earlier cars, then the car parks there. Otherwise, the car proceeds forward (to spots with larger numbers), parking in the first available spot that 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 of this simple setup that we aim to consider in this project.

Depending on the considered variation, we ask the following: How many sequences of length n are there such that all cars are able to park? Can we characterize such sequences? Can we list them efficiently? Does the order of the cars matter? Does the chosen variation share some properties with some other combinatorial objects?

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 communicate to one of its neighbors on a unique frequency. This condition is referred to as a conflict-free coloring.

In the context of robot navigation, it may be necessary to change the frequencies over time. For this purpose, exactly one node can change its color in each step. At the same time, however, it must be ensured that a valid conflict-free coloring is maintained throughout.

The goal of this thesis is relatively open and can be adapted to the tastes and ideas of the student. However, among other things, there is the question of providing bounds for the required number of colors so that arbitrary reconfiguration is possible.

For a detailed description, see the following PDF.