Spectral bounds in extremal discrete geometry

极值离散几何中的谱界

• 批准号: 414898050
• 负责人: Professor Dr. Frank Vallentin
• 金额: --
• 依托单位: Abteilung Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/414898050?language=en
• 关键词: Spectral; bounds; extremal; discrete; geometry

Extremal / optimal structures in discrete geometry are fundamental to many areas in mathematics, physics, (quantum) information theory, and materials science. Famous examples are densest packings of spheres, densest packings of tetrahedra, and the chromatic number of the Euclidean plane. The problem of optimal packings of tetrahedra goes back to the ancient Greeks, the sphere packing problem was first mentioned by Kepler, and determining the chromatic number of the plane is known as the Hadwiger-Nelson problem. Despite the long history of these problems, there are only few mathematical tools available to tackle them.Studying extremal structures in discrete geometry, we are facing twobasic tasks:Constructions: How to construct structures which are conjecturally optimal?Obstructions: How to prove that a given structure is indeed optimal?For the constructions researchers in mathematics and engineering found many heuristics which often work well in practice. The main objective of this proposal is the development and the validation of (computational) tools for the obstructions. For the special case ofsphere packings the PI developed a blend of tools coming from infinite-dimensional semidefinite optimization and harmonic analysis,together with computational techniques coming from real algebraic geometry and polynomial optimization. The results obtained arefrequently the best-known, for example for the sphere packing problem, the kissing number problem or the measurable chromatic number of Euclidean space.The aim of this proposal is to go beyond sphere packings to packings of more complex geometric shapes (like tetrahedra) and to go beyond measurable colorings of Euclidean spaces to measurable colorings of more complex geometries (like Riemannian symmetric spaces).To achieve this one has to improve current computational techniques. In particular, the goal is to 1. extend the current methods so that they can deal with more complex geometries,2. build on stronger, computationally more expensive, tools from combinatorial optimization.This will allow to apply mathematical optimization to a much wider range of challenging optimization problems in discrete geometry.

离散几何中的极值/最优结构是数学、物理、（量子）信息论和材料科学许多领域的基础。著名的例子是球体的最密堆积、四面体的最密堆积以及欧几里德平面的色数。四面体的最佳堆积问题可以追溯到古希腊人，球堆积问题由开普勒首先提出，确定平面的色数被称为哈德维格-纳尔逊问题。尽管这些问题由来已久，但可用于解决它们的数学工具却很少。研究离散几何中的极值结构，我们面临着两个基本任务：构造：如何构造推测最优的结构？障碍：如何证明给定的结构确实是最优的？对于构造，数学和工程领域的研究人员发现了许多在实践中经常发挥作用的启发式方法。该提案的主要目标是开发和验证障碍物的（计算）工具。对于球体堆积的特殊情况，PI 开发了一系列来自无限维半定优化和调和分析的工具，以及来自实代数几何和多项式优化的计算技术。获得的结果通常是最著名的，例如球体堆积问题、接吻数问题或欧几里德空间的可测量色数。该提案的目的是超越球体堆积到更复杂几何形状（如四面体）的堆积，并超越欧几里得空间的可测量着色到更复杂几何形状（如黎曼几何）的可测量着色 对称空间）。要实现这一目标，必须改进当前的计算技术。具体来说，目标是 1. 扩展当前方法，以便它们能够处理更复杂的几何形状，2.建立在更强大、计算成本更高的组合优化工具的基础上。这将允许将数学优化应用于离散几何中更广泛的具有挑战性的优化问题。