The Sunflower Conjecture, Disjunctive Normal Forms, and Beyond

点击翻译按钮获取中文摘要

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.