Substructures of Large Objects - Extremality, Typicality, and Complexity

在数学的许多领域中，一个基本的主题来自以下类型的问题：给定一个“大”对象，它是否包含特定的“小”或“基本”子结构？此外，如果是这样，它包含多少给定的子结构，以及“大”对象可以分解成哪些“基本”对象？仅列出几个突出的例子，这包括素数分解的数字，球包装在d维空间，矩阵分解成特定类型的矩阵，勒贝格的分解定理的措施，和Levy-Ito分解的Levy过程。这个项目的目的是调查这些问题在不同方面的组合学和几何包括以下主题：1.子图包含：给定一个目标图H，我们要求保证H作为宿主图G中的子图包含的充分条件。这可以说是图论中最基本的问题之一。2.分解：给定目标图H1，...，Hr和宿主图G，研究了G的边集能否分解为H1，.，Hr的边不相交副本.超图匹配：超图中最基本和研究最多的子结构之一是匹配。在图中，我们从结构和算法的角度都很好地理解了匹配。超图匹配显示了一个相当复杂的结构，并且明显不太好理解。考虑到组合学中各种著名的开放问题（包括分解问题）可以被重新表述为超图（完美）匹配问题，这并不奇怪。球形填料：求d维空间中非重叠单位球面的密排可能是数学中最古老和最著名的问题之一。在他著名的清单23个问题发表于1900年，希尔伯特要求在他的第18个问题的denominator球包装在三维空间。球体堆积密度仅针对维度1、2、3、8和24确定，并且基本上对于任何其他维度保持难以捉摸。

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.