Substructures of Large Objects - Extremality, Typicality, and Complexity

大物体的子结构——极值性、典型性和复杂性

• 批准号: 428212407
• 负责人: Professor Dr. Felix Joos
• 金额: --
• 依托单位: Arbeitsgruppe Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Independent Junior Research Groups
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/428212407?language=en
• 关键词: Substructures; Large; Objects; Extremality; Typicality

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.

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