Extremal Combinatorics: Challenges, Methods and Applications

Extremal Combinatorics is one of the most active areas in modern Combinatorics and has developed spectacularly over the last decades. It deals with the problem of determining or estimating the maximum or minimum possible values of invariants of combinatorial structures that satisfy certain requirements, as well as with the investigation of inequalities between such invariants, and questions dealing with relations among them. The problems in the area are often related to other topics including Coding Theory, Additive Number Theory, Geometry and Computer Science. In this project the PI intends to investigate several questions in the area, including ones that are motivated by applications in Coding Theory and Geometry among others. Besides the study of these problems the aim is to develop new relevant methods. The specific topics to be studied in this project include old and new problems in Combinatorics and Discrete Geometry, questions about erasure codes and their connection to hypercube extremal problems, and problems about geometric and combinatorial designs. One of the subjects to be studied is graph codes, a natural variant of the classical topic of error-correcting codes motivated by questions in additive number theory and extremal finite set theory, and related to problems in Ramsey Theory. Another topic is the sign-rank of matrices, which appears naturally in communication complexity, and can also be interpreted as a representation of matrices by points and hyperplanes in the Euclidean space. This is a natural geometric problem, and it is also motivated by one of the earliest problems studied in computational learning. The planned methods combine combinatorial, probabilistic, algebraic and geometric tools with ideas from Coding Theory. It is expected that progress on the problems considered will be interesting and significant, will lead to the development of novel fruitful techniques, and will yield interesting applications in related areas. Students will be involved in the research. 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. NSF Award ID: 2553988 | Program: 01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Noga Alon | Institution: Princeton University, PRINCETON, NJ | Award Amount: $180,000 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2553988 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2553988.html