Rigorous results on Spin Glasses

这一提议中的主要问题来自于大约40年前物理学家引入的模型，目的是了解某些金属合金的不寻常的磁性行为，即自旋玻璃。对这些模型的研究产生了许多新的想法，这些想法发现了超出最初动机的意想不到的应用。 最有趣的应用之一是在优化问题领域。举一个例子，让我们考虑一大群人，其中任何两个人要么是朋友，要么是敌人，让我们把他们分成两组，试图保持朋友在一起，而将敌人分开。这不可能总是完美的，因为如果你的两个朋友是敌人，那么你要么失去一个朋友，要么他们在你的团队中仍然是敌人；这被称为受挫三人组。众所周知，以最优方式划分组的问题通常很难解决(想象一下有许多受挫的三元组的情况)，但对于典型情况下会发生什么，人们可以提出许多有趣的问题。例如，人们可以问最优解决方案通常是什么样子的，或者其他几乎最优的解决方案与最优解决方案是如何关联的。 物理学家们非常成功地将自旋眼镜研究中发展出来的思想应用于数学(旅行推销员问题、图划分)、计算机科学(布尔公式的随机可满足性)和生物学(模拟大脑活动)中的各种优化问题，他们的主要贡献大致可分为两类。一方面，他们对这些优化问题中的典型情况(通过随机选择问题的参数来模拟典型情况)有了深刻而复杂的理论理解。另一方面，考虑到这一点，他们可以提出有效的算法来解决实践中的一些问题。 这项提案的主要重点是第一类，即一个模型家族中的理论图景--所谓的稀释自旋玻璃模型，其中包括对上述问题的修改，即在每个人只与少数其他人互动的情况下将一组人分成两组。该提议的主要目标是为物理学家在这些模型中提出的图景找到严格的数学解释。特别是，该提案试图证明著名的自由能的Mézard-Parisi公式，以及描述这些模型中Gibbs度量的结构(其中主要的公开问题称为再生性假设)。就像物理学家的工作是基于在自旋玻璃模型的背景下发展出来的想法一样，这个提议建立在近年来在原始自旋玻璃模型背后的严格数学理论方面取得的重大进展的基础上。

The main questions in this proposal originate from the models that were introduced by the physicists about forty years ago with the goal of understanding the unusual magnetic behaviour of certain metal alloys, called spin glasses. The study of these models produced many new ideas that found unexpected applications beyond their original motivation. One of the most interesting applications was to the area of optimization problems. To give one example, let us consider a large group of people where any two are either friends or enemies, and let us divide them into two groups attempting to keep friends together and separate the enemies. This can not always be done perfectly, because if two of your friends are enemies then either you lose one of your friends or they will stay enemies inside your group; these are called frustrated triples. This problem of dividing the group in an optimal way is known to be very difficult to solve in general (imagine a situation with numerous frustrated triples), but there are many interesting questions one can ask about what happens in a typical situation. For example, one can ask how optimal solutions typically look like, or how other almost optimal solutions are related to the optimal ones. The physicists were very successful in applying the ideas developed in the study of spin glasses to various optimization problems arising in mathematics (traveling salesman problem, graph partitioning), computer science (random satisfiability of Boolean formulas) and biology (modelling brain activity), and their main contributions can be roughly divided into two categories. On the one hand, they have developed a deep and sophisticated theoretical understanding of what happens in a typical situation in these optimization problems (where a typical situation is modelled by choosing the parameters of the problem randomly). On the other hand, having this picture in mind allowed them to come up with efficient algorithms for solving some of these problems in practice. The main focus of this proposal is on the first category, namely, theoretical picture in one family of models -- the so called diluted spin glass models, which includes a modification of the above problem of splitting a group of people into two groups in the case when each person interacts with only a small number of other people. The main goal of the proposal is to find a rigorous mathematical explanation for the picture proposed by the physicists in these models. In particular, the proposal attempts to prove the famous Mézard--Parisi formula for the free energy, as well as describe the structure of the Gibbs measure in these models (where the main open problem is called reproducibility hypothesis). Just like the work of the physicists was based on the ideas developed in the context of the models of spin glasses, this proposal builds upon a significant progress achieved in recent years in the rigorous mathematical theory behind the original spin glass models.