The Sunflower Conjecture, Disjunctive Normal Forms, and Beyond

计算机科学和数学之间有着丰富的共生历史。该奖项旨在进一步加强这种联系，特别是理论计算机科学和组合学领域之间的联系。这个项目围绕着组合学中一个基本的公开问题展开，这个问题叫做向日葵猜想。这个问题起源于1960年，尽管在数学和计算机科学中有许多应用，但至今仍未得到回答。国际和平研究所最近的工作在解决这一猜想方面取得了重大进展，本项目的重点是继续这项工作。该项目为研究生提供了研究培训的机会。具体地说，该项目探索了集合系统(也称为超图)和析取范式之间的对应关系。在PI最近工作的基础上，该项目展示了用于研究DNF的工具如何在研究集合系统中起到作用，并提出了一个统一和通用的框架，以在数学和理论计算机科学中关于集合系统和DNF的结构的几个充分研究的猜想上取得进展。除了向日葵猜想和组合学中的相关问题外，这些问题还包括与DNF压缩和DNF的傅立叶结构有关的问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

There is a rich history of symbiosis between computer science and mathematics. This award is aimed at further strengthening this connection, and in particular between the fields of theoretical computer science and combinatorics. This project centers around a fundamental open problem in combinatorics, called the sunflower conjecture. This problem originated in 1960 and is still unanswered, despite having numerous applications in mathematics and in computer science. Recent work by the PI has made significant progress towards resolving the conjecture, and this project is focused on continuing this work. The project provides research training opportunities for graduate students.Concretely, the project explores a correspondence between set systems (also known as hypergraphs) and DNFs (Disjunctive Normal Forms). Building upon recent work by the PI, the project demonstrates how tools used to study DNFs can be instrumental in studying set systems, and proposes a unified and versatile framework to make progress on several well-studied conjectures in mathematics and theoretical computer science about the structure of set systems and DNFs. These also include, beyond the sunflower conjecture and related problems in combinatorics, problems related to DNF compression and the Fourier structure of DNFs.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.