CAREER: Problems in Extremal and Probabilistic Combinatorics

职业：极值和概率组合问题

• 批准号: 2146406
• 负责人: Asaf Ferber
• 金额: $ 43.5万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2027-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2146406&HistoricalAwards=false
• 关键词: CAREER; Problems; Extremal; Probabilistic; Combinatorics

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). In this project the PI will study various topics in extremal and probabilistic combinatorics, two areas which have grown significantly in both depth and breadth in the 21st century, resulting in methods that apply well beyond their original settings. These include applications, and many significant breakthroughs, in number theory, group theory, probability theory, information theory, and theoretical computer science. The approaches and techniques resulting from this project will have a significant impact on the development of these areas and will also be applicable in other branches of mathematics and theoretical computer science. This project is also designed for training undergraduate and graduate students.The problems the PI intends to study are fundamental and belong to some of the most actively studied topics of current research in extremal and probabilistic combinatorics. The first set of questions is coming from the sub-area of Ramsey theory and includes several classical questions on Ramsey numbers, spectral Ramsey theory, the clique number of Cayley graphs, Ramsey properties of random graphs, and more. The second set of questions is related to perfect matchings in (hyper)graphs. In particular, the PI will study fundamental problems such as: finding the Dirac threshold for the existence of a perfect matching, finding/counting 1-factorizations in (pseudo)random hypergraphs, decomposing the edges of d-regular (pseudo)random d-regular hypergraphs into perfect matchings, etc. Furthermore, the PI intends to study other interesting problems such as: finding the smallest number of (linear) bases over a finite field whose union forms an additive base, extremal problems in k-majority tournaments, counting Hadamard matrices, and more. Common themes run through these areas, and the methods developed in one area are likely to have implications for the others.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.

该奖项的全部或部分资金来自《2021年美国救援计划法案》(公法117-2)。在这个项目中，PI将研究极值和概率组合数学中的各种主题，这两个领域在21世纪的深度和广度都有了显著的增长，导致方法的应用远远超出了最初的设置。这些包括在数论、群论、概率论、信息论和理论计算机科学方面的应用和许多重大突破。该项目产生的方法和技术将对这些领域的发展产生重大影响，也将适用于数学和理论计算机科学的其他分支。这个项目也是为培养本科生和研究生而设计的。PI打算研究的问题是基础性的，属于当前极值和概率组合学研究中最活跃的一些研究课题。第一组问题来自Ramsey理论的子领域，包括关于Ramsey数、谱Ramsey理论、Cayley图的团数、随机图的Ramsey性质等几个经典问题。第二组问题与(超)图中的完美匹配有关。特别是，PI将研究基本问题，如：寻找完美匹配存在的Dirac阈值，在(伪)随机超图中寻找/计数1-因子分解，将d-正则(伪)随机d-正则超图的边分解为完美匹配等。此外，PI还将研究其他有趣的问题，如：在其并构成可加基的有限域上寻找(线性)基的最小数目，k-多数竞赛中的极值问题，计算Hadamard矩阵，等等。这些领域贯穿着共同的主题，在一个领域开发的方法可能会对另一个领域产生影响。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。