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 $G$, one may wonder whether the edge set of $G$ 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+1$ vertices can be decomposed into $n$ (edge-disjoint) copies of any given $2$-regular graph $F$ on $2n+1$ vertices. This has been solved if $F$ fulfills further properties and for all large $n$ by Glock, Joos, Kim, Kühn and Osthus (see here).
• Tree packing conjecture: Can we decompose the complete graph on $n$ vertices into any given list of trees $T_1,\ldots,T_n$ where $T_i$ is a tree on $i$ vertices?
• Ringel's tree packing conjecture: Given any tree $T$ on $n+1$ vertices, does the complete graph on $2n+1$ vertices contain $2n+1$ edge-disjoint copies of $T$? This has been solved by Montgomery, Pokrovskiy and Sudakov for all large $n$ (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 $C$ if every edge is incident to (at least) one vertex in $C$.

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

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 $F$ has the Erdös-Pósa property if there exists a function $f\colon \mathbb{N}\to \mathbb{N}$ such that for every integer $k$ and every graph $G$, the graph $G$ either contains $k$ vertex-disjoint copies from members in $F$ or a set $X$ of $f(k)$ vertices such that $G-X$ contains no member of $F$. For example, if $F$ is contains only the complete graph on two vertices, then $F$ has the property with $f(k)=2k$; in fact, any finite class $F$ 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 $F$ 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 $d$ dimensions? If $d=1$, the answer is very easy, it is 2. For $d=2$ it is also easy, it is $3$. 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\in \{1,2\}$. So one might wonder whether there is some space for another sphere.

What happens actually when $d$ tends to infinity? It is not hard to observe that the optimal solution is an exponential function in $d$. However, the base is not determined. Jenssen, Joos, and Perkins improved the lower bound by a factor of $d$ 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