Department of
Applied
Mathematics

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

A student project 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 project can vary from understanding some research level project to becoming an expert in some particular area of research. Some projects can be finished by implementing some research ideas into concrete software. (Disclaimer: Hands-on implementation work under my guidance is recommended only for bachelor projects. Even these will require you to read and understand theoretical results!)

Independent of the scale and final outcome of a project that we may mutually agree upon, it is expected that at the end of the project 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 projects.

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.