Research topics

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).

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)

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.