Statistical Physics Methods in Combinatorics, Algorithms, and Geometry

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

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.