Probabilistic and Extremal Combinatorics

概率和极值组合学

• 批准号: 2246907
• 负责人: Tom Bohman
• 金额: $ 24万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-08-01 至 2026-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2246907&HistoricalAwards=false
• 关键词: Probabilistic; Extremal; Combinatorics; Probabilistic; Extremal; Combinatorics

This research project is an investigation of discrete mathematical objects like networks and codes. Extremal combinatorics is focused on developing a better understanding of discrete mathematical objects that optimize interesting or desirable properties, while probabilistic combinatorics studies discrete mathematical objects that are generated by a series of random choices. These two research directions are intimately related as randomized algorithms are a remarkably powerful tool for the construction of interesting discrete mathematical objects. Furthermore, randomness is a major theme of the work on extremal problems for discrete structures as a deep understanding of the ways in which deterministic objects mimic their randomized counterparts often leads to major progress. This research has the potential to benefit society through the development of new algorithms for computational problems on large networks, new methods for analyzing existing network algorithms, and new codes and communication protocols. The project also provides training opportunities at both the undergraduate and graduate level.This research is in the broad areas of probabilistic and extremal combinatorics. The work in probabilistic combinatorics is focused on very sharp concentration of global parameters of the binomial random graph and problems regarding the decomposition of the edge set of the uniform random graph into cliques or bicliques. The work on sharp concentration in the binomial random graph is motivated by a recent result of the investigator and a doctoral student that establishes 2-point concentration of the independence number of the binomial random graph over a broad range of the probability parameter. The comprehensive understanding of the extent of concentration of the independence number of the binomial random graph is one of the goals of this part of the research program. This project also includes further study of the fascinating lonely runner conjecture and some problems on Ramsey numbers for hypergraphs and posets. While the structures that we consider in these two contexts are not necessarily random, we expect the interplay of structure and randomness (i.e. pseudorandom properties of discrete structures) to play a major role. The ultimate goal of this research is to find new methods that are broadly applicable in discrete mathematics.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该研究项目是对网络和代码等离散数学对象的研究。极端组合物的重点是对优化有趣或理想的属性的离散数学对象进行更好的理解，而概率组合学研究由一系列随机选择产生的离散数学对象。这两个研究方向是密切相关的，因为随机算法是构建有趣的离散数学对象的非常强大的工具。此外，随机性是关于离散结构的极端问题的主要主题，这是对确定性对象模仿其随机对应物的方式的深刻理解。这项研究有可能通过开发大型网络上的计算问题，分析现有网络算法的新方法以及新的代码和通信协议来使社会受益。该项目还在本科和研究生层面提供培训机会。这项研究在概率和极端组合学的广泛领域。概率组合学中的工作集中在二项式随机图的全局参数的非常清晰的浓度上，以及有关均匀随机图的边缘集合中的分解成簇或双质量的问题。二项式随机图中急剧浓度的工作是由研究者和博士生的最新结果激励的，该研究人员在广泛的概率参数上建立了二项式随机图的独立性数的2分浓度。对二项式随机图的独立性浓度程度的全面理解是研究计划的这一部分的目标之一。该项目还包括进一步研究迷人的孤独跑步者的猜想，以及有关超图和Posets的Ramsey数字的一些问题。尽管我们在这两种情况下考虑的结构不一定是随机的，但我们期望结构和随机性的相互作用（即离散结构的伪内属性）起着主要作用。这项研究的最终目的是找到广泛适用于离散数学的新方法。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响评估标准通过评估来获得支持的。