Department of
Applied
Mathematics

Before listing some concrete problems -- that I think can be a nice bachelor/master thesis -- I would like to comment on our mutual expectations out of a thesis.

A student thesis depends not only on my own areas of interest, but also on the background and interests of the student. So in principle we can find a common problem of interest to work on that is quite different from what is listed here. Depending on your level the outcome of a thesis can vary from understanding some research level project (bachelor thesis) to becoming an expert in some particular area of research (PhD thesis). Some theses can be finished by implementing some research ideas into concrete software.

Independent of the scale and final outcome of a thesis that we may mutually agree upon, it is expected that at the end you have learnt about methods and objects that are of theoretical as well as practical importance. In general, they will relate to geometry and polyhedra.

Here are some concrete problems for bachelor/master thesis.

Uniform Polytopes and their extension complexity

Uniform polytopes generalize the notion of regular polygons on the plane. A way to construct a large class of them is known (Wythoff construction). Construct small extended formulations of uniform polytopes or at least the ones obtainable from Wythoff construction.

Indpendent set polytopes in Perfect Graphs

The goal of the project would be to study the perfect graph theorem and try to work out an extended formulation for the convex hull of all independent sets. For general graphs no small extension exists. Does one exist for perfect graphs?

Library of extended formulations

Write a software library that can be used to efficiently do computations over polytopes by exploiting extended formulations. Ideally your library would extend the functionalities of some other popular tool for polehdral computations such as lrs, cdd, polymake, etc.