Discrete Problems

离散问题

• 批准号: 0200856
• 负责人: Jeffry Kahn
• 金额: $ 36.69万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-06-01 至 2008-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0200856&HistoricalAwards=false
• 关键词: Discrete; Problems

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.

该项目解决的问题涵盖了相当广泛的离散数学（DM），一些来自相关领域，如统计力学（SM），概率和理论计算机科学（TCS）。 这些问题中的一个共同点是：人们在一些大的离散空间（例如图中的独立集或适当的着色）上给出了概率分布，并且想要知道系统的一部分的行为是否会显著影响其他遥远部分的行为。 "长程效应”（LRE's）这个术语用于描述这种相互作用。强和弱LRE's都很有趣：对于SM来说，通常需要的是强LRE，通常称为"相变”（PT）。在最近的工作中，研究人员和他的学生DavidGalvin主要使用组合思想来解决这个领域中一个研究较多的问题（关于PT的“硬核晶格气模型”），目前特别希望的是，从这项工作的想法，更一般地说，研究人员的组合的角度来看，将导致各种或多或少相关问题的进展。从DM和TCS的角度来看，另一方面，弱LRE通常是可取的，例如，因为它们与马尔可夫链的快速混合有关（一个主题的主要兴趣在TCS），因为在组合应用的概率，具有弱LRE的系统有时可以替代基于纯粹独立选择的概率空间。 (This再次涉及核心模型，它出现在令人惊讶的多样化的数学背景下。）一般来说，该项目的主要部分旨在理解各种大型随机系统的有序或无序程度，例如，通过了解相邻粒子之间的相互作用，可以在多大程度上预测物理系统的全局结构。近年来，与用于模拟物理现实的随机系统类似的随机系统在TCS和DM中发挥着越来越重要的作用，部分是因为它们可以帮助分析（算法和/或理论），甚至在这些领域的非随机问题;并且已经越来越多地认识到，这三个学科中出现的问题是相关的。 本项目的一个主要主题是一个interestin应用思想和方法跨越数学边界：特别是在使用的想法从调查员的核心领域（DM）攻击SM和TCS的问题，而且在带来了越来越熟悉的技术从后者领域tobear在DM的长期利益的几个问题。