Theoretical Computer Science & Discrete Mathematics

Research topics

In our research group we investigate a variety of topics. Most topics involve some kind of discrete object, which may be a graph or hypergraph, a permutation, a Latin square or geometric objects. We investigate these discrete objects in several aspects; this may involve algorithmic or structural considerations. Frequently, we explore how a typical random object from a certain class of objects looks like.

Graph and hypergraph decompositions

Given a (finite) graph GG, one may wonder whether the edge set of GG can be decomposed into (the edge sets of) predetermined graphs. There are a few instances of this question which become famous conjectures in the field some of which are solved by now.

  • Oberwolfach problem: Ringel asked in the 1960s whether the complete graph on 2n+12n+1 vertices can be decomposed into nn (edge-disjoint) copies of any given 22-regular graph FF on 2n+12n+1 vertices. This has been solved if FF fulfills further properties and for all large nn by Glock, Joos, Kim, Kühn and Osthus (see here).
  • Tree packing conjecture: Can we decompose the complete graph on nn vertices into any given list of trees T1,,TnT_1,\ldots,T_n where TiT_i is a tree on ii vertices?
  • Ringel's tree packing conjecture: Given any tree TT on n+1n+1 vertices, does the complete graph on 2n+12n+1 vertices contain 2n+12n+1 edge-disjoint copies of TT? This has been solved by Montgomery, Pokrovskiy and Sudakov for all large nn (see here).
  • Jackson conjectured in the 1980s that any regular bipartite tournament can be decomposed into Hamilton cycles. Granet proved this conjecture in 2022 (see here).

Weak dualities for graph packing and covering problems

A matching in a graph is a set of disjoint edges and a bipartite graph is a graph whose vertex set can be split into two classes such that there are no edges inside the two classes. A set is a vertex cover CC if every edge is incident to (at least) one vertex in CC.

A fairly simple theorem we learn in Discrete Structures I says that in a bipartite graph the size of the largest matching MM equals the size of the smallest vertex cover CC. Observe that this is optimal because the edges in MM are disjoint and hence each edge of MM needs to intersect CC.

Finding a largest matching and finding a smallest vertex cover in a graph are classical optimisation problems. Observe that one is a maximisation problem and one is a minimisation problem. In fact, they are dual to each other. For linear programs we know that duality plays a crucial role whereas for integer linear programs, as in our case, we may not have perfect duality anymore. Already when we consider the matching/vertex cover problem in general graphs, a smallest vertex cover may be essentially double as large as a matching; for example, in the complete graph.

The Erdös-Pósa property deals with graphs classes where at least a weak duality is maintained. We say a family of graphs FF has the Erdös-Pósa property if there exists a function f ⁣:NNf\colon \mathbb{N}\to \mathbb{N} such that for every integer kk and every graph GG, the graph GG either contains kk vertex-disjoint copies from members in FF or a set XX of f(k)f(k) vertices such that GXG-X contains no member of FF. For example, if FF is contains only the complete graph on two vertices, then FF has the property with f(k)=2kf(k)=2k; in fact, any finite class FF has the property. Strikingly, the class of all cycles has the property, as Erdös and Pósa proved in the 1960s.

There are many open problems regarding the Erdös-Pósa property and it is still unclear whether one can identify a somewhat universal criterion that determines whether a family FF has the Erdös-Pósa property. Another interesting problem arises if in the definition every occurrence of "vertex" gets replaced "edge". This variant seems even more mysterious (see for example here)

Kissing numbers

How many unit sphere can touch a specific unit sphere in dd dimensions? If d=1d=1, the answer is very easy, it is 2. For d=2d=2 it is also easy, it is 33. However, in three dimensions the problem is already complicated and already Newton has thought about this problem in the 17th century. The solution is 12, but there is in fact a configuration with twelve spheres such that all spheres have some space to move a bit, which is not the case for d{1,2}d\in \{1,2\}. So one might wonder whether there is some space for another sphere.

What happens actually when dd tends to infinity? It is not hard to observe that the optimal solution is an exponential function in dd. However, the base is not determined. Jenssen, Joos, and Perkins improved the lower bound by a factor of dd after Shannon, Wiener, and Chabauty independently determined in the 1950s a lower bound which every greedy algorithm achieves.

Last update on Apr 4, 2023 at 09:01 UTC
color-mode icon
home icon