Discrete Problems

该项目涉及相当广泛的离散数学(DM)领域的问题，其中一些问题来自统计力学(SM)、概率和理论计算机科学(TCS)等相关领域。在许多这样的问题中，一个共同的线索是：给一个人在某个大的离散空间上的概率分布(例如，图中的独立集合或适当的着色)，并想知道系统的一个部分的行为是否会显著影响其他遥远部分的行为。在最近的工作中，研究人员和他的学生DavidGalvin主要使用组合思想来解决这一领域中的一个已研究过的问题(关于硬核晶格气体模型中的PT)，目前的一个特别的希望是，来自这项工作的想法，以及更一般地，研究者的组合观点，另一方面，从DM和TCS的角度来看，弱LRE通常是可取的，例如，因为它们与马尔可夫链的快速混合(TCS的一个主要感兴趣的主题)有关，并且因为在概率的组合应用中，具有足够弱LRE的系统有时可以替代基于纯独立选择的概率空间。(这又涉及到核心模型，它出现在令人惊讶的不同数学背景中。)非常笼统地说，该项目的(主要部分)旨在了解各种大型随机系统中的有序或无序程度，例如，从关于相邻粒子之间相互作用的知识可以预测物理系统的全局结构的程度。近年来，与用于模拟物理现实的随机系统类似的随机系统在TCS和DM中发挥着越来越重要的作用，部分原因是它们可以帮助分析(算法和/或理论上)这些领域的非随机问题；并且人们越来越多地认识到这三个学科中出现的问题的关联程度。本项目的一个主要主题是对跨越数学界限应用想法和方法的兴趣：特别是使用研究人员核心区(DM)的想法来解决SM和TCS中的问题，而且还使人们越来越熟悉后一个领域的技术，以解决DM长期感兴趣的几个问题。

The project addresses problems covering a rather broadspectrum of discrete mathematics (DM), some drawn from relatedareas such as statistical mechanics (SM), probability, andtheoretical computer science (TCS). A common thread in many of these problems is:one is given a probability distribution on some large discrete space (e.g. independent sets in, or proper colorings of, a graph), and wants to know whether behavior in one part of the system can significantly affect behavior in other, distant parts. The loose term``long range effects" (LRE's) is used for such interactions.Both strong and weak LRE's are of interest:For SM what's wanted is, more often than not,strong LRE's, usually under the name ``phase transition" (PT).In very recent work, the investigator and his student DavidGalvin used mainly combinatorial ideas to settle onemuch-studied question in this area (concerning PT's in the``hard-core lattice gas model"), and a particular hope atpresent is that ideas from this work, and, more generally,the investigator's combinatorial perspective, will lead toprogress on various more or less related questions.From the perspectives of DM and TCS, on the other hand,weak LRE's are often desirable, e.g. because of theirconnections with rapid mixing of Markov chains (a topicof major interest in TCS), and because in combinatorialapplications of probability, systems with sufficientlyweak LRE's can sometimes substitute for probability spacesbased on purely independent choices. (This again involvesthe hard-core model, which arises in surprisingly diversemathematical contexts.)Speaking very generally, the (main part of the) project aimsat understanding the degree of order or disorder in variouslarge random systems, for instance the extent to which theglobal structure of a physical system can be predicted fromknowledge about interactions between neighboring particles.In recent years, random systems similar to those used to modelphysical reality have played increasingly important rolesin TCS and DM, partly because they can be helpful in analyzing(algorithmically and/or theoretically) even non-random problemsin these areas; and there has been an increasing realization ofthe degree to which the issues arising in these three disciplinesare related. One major theme of the present project is an interestin applying ideas and methods across mathematical boundaries:especially in using ideas from the investigator's core area (DM)to attack problems in SM and TCS, but also in bringing an increasing familiarity with techniques from the latter areas tobear on several problems of longstanding interest in DM.