Statistical Physics Methods in Combinatorics, Algorithms, and Geometry

点击翻译按钮获取中文摘要

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.