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将研究基本问题，如：找到完美匹配存在的狄拉克阈值，在（伪）随机超图中找到/计数1-因子分解，将d-正则（伪）随机d-正则超图的边分解为完美匹配等。寻找有限域上的最小数量的（线性）基，其联合形成一个加法基，k-多数竞赛中的极值问题，计数Hadamard矩阵等等。共同的主题贯穿于这些领域，在一个领域开发的方法可能会对其他领域产生影响。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。