Global and Local Properties of Discrete Structures

离散结构的全局和局部属性

基本信息

批准号：
1764123
负责人：
Jozsef Balog
金额：
$ 42.5万
依托单位：
University of Illinois at Urbana-Champaign
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-06-15 至 2024-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1764123&HistoricalAwards=false
关键词：
Global Local Properties Discrete Structures

项目摘要

The theory of combinatorial structures is closely related to several areas of mathematics, including algebra, logic, number theory, and probability, as well as to other fields such as information theory, coding theory, theoretical computer science, and statistical physics. Investigating random and pseudo-random structures has become an important research topic, particularly because the results and the techniques developed proved to be useful in the study of large networks in important applications. A recently-discovered connection between sparse combinatorial structures and enumeration problems yielded several deep results that call for further study. This research project focuses on understanding the robustness of important properties of dense structures and testing whether they are inherited by random sparse substructures, with the goal of developing a unified theory. The project will involve training of graduate students through involvement in the research, and it is anticipated that some of the results will be integrated into courses for graduate student training.A central focus of combinatorics over the past twenty years has been the introduction and proof of various random analogues of well-known theorems in extremal graph theory, Ramsey theory, and additive combinatorics. Recently, the so-called container method was developed, which proved to be useful to attack these questions and many others. One direction of research in this project will focus on applications of the method, and it is expected that this exploration will lead to new exciting questions and directions. In particular, the following related areas are to be investigated: (1) extremal questions in sparse structures; (2) embedding in subgraphs of sparse random and pseudo-random graphs; (3) applications of flag algebras; and (4) problems in bootstrap percolation.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.

组合结构理论与代数、逻辑、数论和概率等数学领域以及信息论、编码理论、理论计算机科学和统计物理学等其他领域密切相关。研究随机和伪随机结构已成为一个重要的研究课题，特别是因为所开发的结果和技术被证明可用于研究重要应用中的大型网络。最近发现的稀疏组合结构和枚举问题之间的联系产生了一些需要进一步研究的深刻结果。该研究项目的重点是了解致密结构重要属性的鲁棒性，并测试它们是否被随机稀疏子结构继承，目标是发展统一的理论。该项目将通过参与研究来培训研究生，预计部分成果将被纳入研究生培训课程中。过去二十年组合数学的一个中心焦点是引入和证明极值图论、拉姆齐理论和加性组合学中著名定理的各种随机类似物。最近，开发了所谓的容器方法，事实证明该方法对于解决这些问题和许多其他问题很有用。该项目的一个研究方向将集中于该方法的应用，预计这一探索将带来新的令人兴奋的问题和方向。具体而言，需要研究以下相关领域：（1）稀疏结构中的极值问题； (2)嵌入稀疏随机图和伪随机图的子图中； (3) 标志代数的应用； (4) 引导渗透问题。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。