Statistical Physics Methods in Combinatorics, Algorithms, and Geometry

组合学、算法和几何中的统计物理方法

• 批准号: MR/W007320/2
• 负责人: Matthew Jenssen
• 金额: $ 105.55万
• 依托单位: King's College London
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=MR%2FW007320%2F2
• 关键词: Statistical; Physics; Methods; Combinatorics; Algorithms

The remarkable idea that matter is made up of discrete units, indiscernible to the eye, can be traced back at least as far as ancient Greece. In the centuries since philosophers and scientists have grappled with the myriad questions this atomic theory of matter raises. This research project is guided by one such question:How does matter, consisting of a multitude of interacting particles, exhibit such a rich array of patterns and structures?Over the course of the past century, the field of statistical physics has emerged to deal with precisely this question. The essence of the problem, to understand the relationship between order and disorder, is so fundamental that it is central to a number of scientific fields. The overarching goal of this project is to show how the tools and intuitions from statistical physics provide a unified framework for solving problems in combinatorics, computer science, and geometry. These investigations will also have the reciprocal benefit of shedding new light on old problems in statistical physics itself.The starting point for this research project is one of the oldest mathematical models of a gas or liquid known as the hard sphere model: simply throw identical non-overlapping spheres into a fixed box at random. As the number of spheres increases, one might expect the spheres to begin to follow a crystalline pattern so that they can all fit inside the box. This shift from randomness to structure is known as a phase transition in physics and it suggests a remarkable fact about matter: the freezing of a gas to a solid occurs for purely geometric reasons. However, mathematically proving that a phase transition in the hard sphere model actually occurs is a major unsolved problem. This problem is intimately related to a problem in geometry that dates back to Kepler in 1611:If you want to fit as many identical spheres into a box as possible, what is the best way to arrange them?This puzzle, known as the sphere packing problem, remained unsolved for almost 400 years. This project proposes the hard sphere model as a key to a deeper understanding of the sphere packing problem. One aim of this project is to prove the existence of particularly dense sphere packings in high-dimensional space.The second part of this research project concerns the study of phase transitions in computer science. Simulating the hard sphere model is one of the oldest challenges in computer science. Indeed the Metropolis Algorithm, one of the most influential algorithms of the 20th century, was developed for precisely this purpose. There is a fascinating connection between the computational complexity of simulating the hard sphere model and the physical phase (gaseous or solid) of the system. Algorithms, such as the Metropolis Algorithm, tend to do well in the gaseous regime, but begin to fail when the system begins to freeze. One theme of this project will be to show that phase transitions need not be an obstacle for the design of successful algorithms. In fact, we will show that the very mechanisms that drive phase transitions can be exploited to design efficient algorithms that work in the ordered, 'frozen' regime.The third part of this project aims to bridge the fields of statistical physics and the mathematical field of combinatorics. A central object of study in combinatorics is known as a graph: a collection of nodes and edges between them. Graphs can be used to encode a vast array of information e.g. people in a social network, neurons communicating in a brain, or a system of interacting particles. A major theme in both statistical physics and combinatorics is to understand the relationship between structure and randomness and both fields have independently developed intricate tools to study the very same phenomena. I plan to combine two powerful methods, one from statistical physics and one from combinatorics, in order to make progress on classical problems in both fields.

物质是由肉眼难以分辨的离散单元组成的，这一非凡的观点至少可以追溯到古希腊。几个世纪以来，哲学家和科学家一直在努力解决这个物质的原子理论所提出的无数问题。这个研究项目是由这样一个问题指导的：物质，由大量相互作用的粒子组成，如何表现出如此丰富的模式和结构？在过去的世纪中，统计物理学领域的出现正是为了解决这个问题。这个问题的本质是理解有序与无序之间的关系，它是如此的根本，以至于它是许多科学领域的核心。该项目的总体目标是展示统计物理学的工具和直觉如何为解决组合学，计算机科学和几何学问题提供统一的框架。这些研究也将为统计物理学本身的老问题带来新的启发。这个研究项目的出发点是气体或液体的最古老的数学模型之一，称为硬球模型：简单地将相同的不重叠的球体随机扔到一个固定的盒子里。随着球体数量的增加，人们可能会期望球体开始遵循一种水晶图案，以便它们都能装进盒子里。这种从随机性到结构的转变在物理学中被称为相变，它表明了一个关于物质的显着事实：气体冻结成固体纯粹是出于几何原因。然而，在数学上证明硬球模型中的相变实际上发生是一个主要的未解决的问题。这个问题与1611年开普勒提出的一个几何问题密切相关：如果你想把尽可能多的相同球体放入一个盒子里，那么排列它们的最佳方法是什么？这个被称为球体填充问题的难题，在近400年的时间里一直没有得到解决。这个项目提出了硬球模型作为一个关键，以更深入地了解球包装问题。本项目的目的之一是证明在高维空间中存在特别稠密的球填充。本研究项目的第二部分涉及计算机科学中的相变研究。模拟硬球模型是计算机科学中最古老的挑战之一。事实上，大都会算法，其中一个最有影响力的算法的20世纪，正是为了这个目的。在模拟硬球模型的计算复杂性和系统的物理相（气态或固态）之间存在着迷人的联系。算法，如大都会算法，往往在气体状态下表现良好，但当系统开始冻结时，开始失败。这个项目的一个主题将是表明，相变不一定是一个成功的算法设计的障碍。事实上，我们将证明，驱动相变的机制可以用来设计有效的算法，工作在有序的，“冻结”regime.The第三部分的项目旨在弥合统计物理领域和组合数学领域。组合学中的一个中心研究对象被称为图：节点和它们之间的边的集合。图可以用来编码大量的信息，例如社交网络中的人，大脑中的神经元通信，或相互作用的粒子系统。统计物理学和组合学的一个主要主题是理解结构和随机性之间的关系，这两个领域都独立开发了复杂的工具来研究相同的现象。我计划将两种强大的方法联合收割机结合起来，一种来自统计物理学，另一种来自组合学，以便在这两个领域的经典问题上取得进展。

项目成果

The least singular value of a random symmetric matrix

随机对称矩阵的最小奇异值

• DOI: 10.1017/fmp.2023.29
• 发表时间: 2024
• 期刊: Forum of Mathematics, Pi
• 作者: Campos M

The singularity probability of a random symmetric matrix is exponentially small

随机对称矩阵的奇点概率呈指数小

• DOI: 10.1090/jams/1042
• 发表时间: 2024
• 期刊: Journal of the American Mathematical Society
• 影响因子: 3.9
• 作者: Campos M

Quasipolynomial-time algorithms for Gibbs point processes

吉布斯点过程的拟多项式时间算法

• DOI: 10.1017/s0963548323000251
• 发表时间: 2023
• 期刊: Probability and Computing
• 作者: Jenssen, Matthew;Michelen, Marcus;Ravichandran, Mohan
• 通讯作者: Ravichandran, Mohan