Problems and Methods in Extremal Combinatorics

Princeton University, Princeton NJ

Investigators

Abstract

Extremal Combinatorics investigates the maximum or minimum possible sizes of combinatorial objects satisfying prescribed sets of required properties. Questions of this type are often motivated by applications in other areas including theoretical computer science, geometry and information theory. This is one of the most active areas in modern Combinatorics and has developed spectacularly over the last decades. In this project the PI intends to investigate several fundamental problems in the area, including ones that are motivated by algorithmic applications. A representative example is the problem of finding the smallest possible size of a graph that contains every member of a given family as an induced subgraph. This is closely related to the ability to store members of the family in an economical way in distributed systems. It is expected that work on the problems addressed in the proposal will lead to new methods and new applications. It is also expected that the project will contribute to advancing mathematics through education by mentoring graduate students working on these topics and by giving lectures on these and related subjects to experts and to graduate and undergraduate students. The aim of the project is to study several important problems in Extremal Combinatorics, including ones motivated by algorithmic applications. The first topic addressed deals with universal graphs which are graphs that contain every member of a given family as an induced subgraph. The investigation of the smallest possible number of vertices of universal graphs for prescribed interesting families is motivated by the study of adjacency labeling schemes and received a considerable amount of attention. Within this area, the main goals are to obtain tight estimates for the smallest possible sizes of universal graphs or hypergraphs for the family of all graphs or hypergraphs with a given number of vertices, the family of all Cayley graphs of a given group, and several families of intersection graphs of simple geometric objects. The second topic proposed concerns traces of hypergraphs and the related notions of their VC-dimension and Littlestone dimension. The PI hopes to prove new bounds for the general extremal problem of estimating the maximum number of projections on a set of vertices of a given size that can be guaranteed in any hpergraph with a given number of vertices and edges. In the study of these problems and related ones the PI plans to apply and develop a range of methods combining combinatorial, probabilistic, algebraic and geometric tools with ideas from Coding Theory. 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.