Substructures of Large Objects - Extremality, Typicality, and Complexity

点击翻译按钮获取中文摘要

A fundamental theme in many areas of mathematics arises from the following type of question: Given a ‘large’ object, does it contain particular ‘small’ or ’elementary’ substructures? In addition, if so, how many given substructures does it contain and into which ‘elementary’ objects can the ‘large’ object be decomposed? To list only a few prominent examples, this includes the prime factorization of numbers, sphere packings in the d-dimensional space, matrix factorizations into particular types of matrices, Lebesgue's decomposition theorem for measures, and the Levy-Ito decomposition of Levy processes.The aim of this project is to investigate such questions in different aspects of combinatorics and geometry including the following themes:1. Subgraph containment: Given a target graph H, we ask for sufficient conditions that guarantee the containment of H as a subgraph in a host graph G. This is arguably among the most fundamental questions in graph theory.2. Decompositions: Given a list of target graphs H1,...,Hr and a host graph G, we investigate whether the edge set of G can be decomposed into edge-disjoint copies of H1,…,Hr.3. Hypergraph matchings: One of the most elementary and most investigated substructures in hypergraphs are matchings. In graphs, we understand matchings well both in a structural and algorithmic point of view. Hypergraph matchings display a considerably more complex structure and are significantly less well understood. This is not very surprising when considering that various famous open problems in combinatorics (including decomposition problems) can be rephrased as a hypergraph (perfect) matching problem.4. Sphere packings: Asking for the densest packings of non-overlapping unit spheres in the d-dimensional space is possibly one of the oldest and most well-known problems in mathematics. In his famous list of 23 problems published 1900, Hilbert asked in his 18th problem for the densest sphere packing in three dimensions. The sphere packing density has been determined only for dimension 1, 2, 3, 8, and 24 and stays elusive for essentially any other dimension.