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.