Thresholds and asymptotics

阈值和渐近

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

This project focuses on two of the PI's current interests, thresholds for random structures and asymptotic enumeration, with somewhat more emphasis on the former. Roughly speaking, a threshold is the point at which some event of interest in a random system becomes likely as some intensity parameter increases. Understanding when this happens has long been a central concern of probabilistic combinatorics and related areas, particularly theoretical computer science and statistical physics. For example, thresholds have been a main focus of the theory of random graphs since its initiation by Erdos and Renyi fifty years ago. They are closely tied to the theory of percolation, a basic model of statistical mechanics dating to work of Broadbent and Hammersley in 1957. (It was, however, some decades before the connections between these disciplines began to be appreciated). Asymptotic enumeration of the type considered in this project is concerned with estimating rates of growth of various combinatorially interesting families (e.g. graphs without triangles or functions representable by k-SAT formulae) in situations where traditional generating functions techniques seem to be of little use.Several of the problems considered in the proposal have roots in related disciplines (one general theme underlying much of the material is that complicated structures can often be usefully approximated by simpler ones), though the focus is primarily on what appears to be mathematically fundamental. These problems are simple and seemingly basic questions that have long resisted solution. Attacking such questions requires one to go beyond existing methods, and to find and exploit connections with other parts of mathematics. Despite the probable difficulty of the main questions considered, recent progress by the PI and coauthors gives hope of further developments and even full resolutions of some of them. There are also many interesting lesser (sub- or related) problems that may prove more tractable.

这个项目的重点是两个PI的当前利益，阈值随机结构和渐近枚举，有点更强调前者。 粗略地说，阈值是随机系统中某些感兴趣的事件随着某些强度参数的增加而变得可能的点。 理解这种情况何时发生一直是概率组合学和相关领域的核心问题，特别是理论计算机科学和统计物理。 例如，自Erdos和Renyi在50年前提出随机图理论以来，阈值一直是随机图理论的主要焦点。 它们与逾渗理论密切相关，逾渗理论是统计力学的基本模型，可追溯到1957年布罗德本特和哈默斯利的工作。 (It然而，在这些学科之间的联系开始受到重视之前的几十年）。 在这个项目中考虑的渐近枚举类型是关于估计各种组合有趣的家庭的增长率（例如，没有三角形的图或可由k-SAT公式表示的函数），在传统的生成函数技术似乎没有什么用处的情况下。（大部分材料背后的一个总的主题是，复杂的结构往往可以有效地近似于较简单的结构），尽管重点主要是在什么似乎是数学基础。这些问题都是简单的，似乎是长期以来一直无法解决的基本问题。 解决这些问题需要超越现有的方法，并找到和利用与数学其他部分的联系。 尽管所考虑的主要问题可能存在困难，但PI和合著者最近的进展给了进一步发展甚至完全解决其中一些问题的希望。 也有许多有趣的较小（子或相关）的问题，可能证明更容易处理。