Questions and Methods in Probabilistic Combinatorics

概率组合学中的问题和方法

• 批准号: 1953990
• 负责人: Jacob Fox
• 金额: $ 17.92万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-06-01 至 2023-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1953990&HistoricalAwards=false
• 关键词: Questions; Methods; Probabilistic; Combinatorics

The probabilistic method is a powerful technique for using probability theory to prove seemingly non-probabilistic facts in combinatorics. Together with the probabilistic method, a second line of study that has grown rapidly is the study of random structures, most famously random graphs. These two lines of research are collectively known as probabilistic combinatorics. This project aims to develop new ideas and techniques in probabilistic combinatorics by studying concrete questions in the field. In addition to fundamental advances in probability and combinatorics, previous work on probabilistic combinatorics has led to development of tools that have had enormous impacts in computer science, where they are used to design and study randomized algorithms and to understand performance on random inputs and in noisy environments.The investigator plans to focus on several topics. One topic concerns Ramsey graphs, which are an important class of graphs that are “approximately extremal” for Ramsey’s theorem. The investigator plans to build on some previous work regarding edge statistics in Ramsey graphs, which also naturally leads to the study of the so-called quadratic Littlewood-Offord problem. Another topic is the subject of extremal theorems “relative to a random set.” For example, given a typical outcome of a random hypergraph, what conditions on a spanning subgraph ensure that it has a perfect matching? To approach questions of this type, the investigator plans to apply some new insights for applying the so-called absorption method non-constructively.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.

概率方法是一种强大的技术，用于使用概率理论来证明组合学中看似非概率的事实。与概率方法一起，迅速发展的第二个研究领域是随机结构的研究，最著名的是随机图。这两条研究路线统称为概率组合学。本计画旨在透过研究机率组合学的具体问题，发展机率组合学的新观念与新技术。除了在概率和组合学的基本进展，以前的工作概率组合学已经导致了在计算机科学中产生巨大影响的工具的发展，在那里他们被用来设计和研究随机算法，并了解随机输入和噪声环境中的性能。其中一个主题涉及拉姆齐图，这是一类重要的图，是拉姆齐定理的“近似极值”。研究人员计划建立在一些以前的工作，边缘统计拉姆齐图，这也自然导致了所谓的二次Littlewood-Offord问题的研究。另一个主题是“相对于随机集”的极值定理。例如，给定一个随机超图的典型结果，在生成子图上什么条件确保它具有完美匹配？为了解决这类问题，研究人员计划应用一些新的见解，用于非建设性地应用所谓的吸收方法。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Extension complexity of low-dimensional polytopes

低维多胞形的可拓复杂度

• DOI: 10.1090/tran/8614
• 发表时间: 2022
• 期刊: Transactions of the American Mathematical Society
• 影响因子: 1.3
• 作者: Kwan, Matthew;Sauermann, Lisa;Zhao, Yufei
• 通讯作者: Zhao, Yufei

Clique minors in graphs with a forbidden subgraph

带有禁止子图的图中的小集团未成年人

• DOI: 10.1002/rsa.21038
• 发表时间: 2021
• 期刊: Random Structures & Algorithms
• 影响因子: 1
• 作者: Bucić, Matija;Fox, Jacob;Sudakov, Benny
• 通讯作者: Sudakov, Benny

Threshold Ramsey multiplicity for odd cycles

奇数循环的阈值 Ramsey 重数

• DOI: 10.33044/revuma.2874
• 发表时间: 2022
• 期刊: Revista de la Unión Matemática Argentina
• 作者: Conlon, David;Fox, Jacob;Sudakov, Benny;Wei, Fan
• 通讯作者: Wei, Fan

Removal lemmas and approximate homomorphisms

移除引理和近似同态

• DOI: 10.1017/s0963548321000572
• 发表时间: 2022
• 期刊: Probability and Computing
• 作者: Fox, Jacob;Zhao, Yufei
• 通讯作者: Zhao, Yufei

Lower bounds for superpatterns and universal sequences

超级模式和通用序列的下界

• DOI: 10.1016/j.jcta.2021.105467
• 发表时间: 2021
• 期刊: Series A
• 作者: Chroman, Zachary;Kwan, Matthew;Singhal, Mihir
• 通讯作者: Singhal, Mihir