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 , one may wonder whether the edge set of 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 vertices can be decomposed into (edge-disjoint) copies of any given -regular graph on vertices. This has been solved if fulfills further properties and for all large by Glock, Joos, Kim, Kühn and Osthus (see here).
- Tree packing conjecture: Can we decompose the complete graph on vertices into any given list of trees where is a tree on vertices?
- Ringel's tree packing conjecture: Given any tree on vertices, does the complete graph on vertices contain edge-disjoint copies of ? This has been solved by Montgomery, Pokrovskiy and Sudakov for all large (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 if every edge is incident to (at least) one vertex in .
A fairly simple theorem we learn in Discrete Structures I says that in a bipartite graph the size of the largest matching equals the size of the smallest vertex cover . Observe that this is optimal because the edges in are disjoint and hence each edge of needs to intersect .
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 has the Erdös-Pósa property if there exists a function such that for every integer and every graph , the graph either contains vertex-disjoint copies from members in or a set of vertices such that contains no member of . For example, if is contains only the complete graph on two vertices, then has the property with ; in fact, any finite class 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 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 dimensions? If , the answer is very easy, it is 2. For it is also easy, it is . 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 . So one might wonder whether there is some space for another sphere.
What happens actually when tends to infinity? It is not hard to observe that the optimal solution is an exponential function in . However, the base is not determined. Jenssen, Joos, and Perkins improved the lower bound by a factor of after Shannon, Wiener, and Chabauty independently determined in the 1950s a lower bound which every greedy algorithm achieves.