Extremal Combinatorics: Problems and Algorithmic Aspects

Princeton University, Princeton NJ

Investigators

Abstract

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 value of an invariant of a combinatorial structure that satisfies certain requirements as well as with the investigation of inequalities between combinatorial invariants, and questions dealing with relations among them. The Principal Investigator intends to investigate several questions in the area, including ones that are motivated by algorithmic applications. The specific topics to be studied include old and new problems in Graph Theory and Combinatorics, as well as the algorithmic aspects of questions about fair representations of necklaces and graphs. The non-constructive solutions of some of these questions combine algebraic and topological tools, leaving the fascinating problem of finding algorithmic solutions open. The proposal addresses several fundamental old and new combinatorial problems. Besides their intrinsic interest, many of these problems are motivated by related questions in other areas. In particular, the study of splitting random necklaces has a surprising connection to questions about random walks in Euclidean spaces and about matchings in nearly regular uniform hypergraphs. The algorithmic aspects of the necklace theorem are intriguing in view of the recent results about the hardness of the problem. The related study of the algorithmic aspects of some of the other fair partitioning problems described in the project is also challenging. The investigation of Graph Codes, which is interesting in its own right, is also motivated by questions about Ramsey type results in Additive Combinatorics. The methods the Principal Investigator intends to apply combine combinatorial, probabilistic, algebraic and geometric tools with ideas from Coding Theory. It is expected that progress on the problems mentioned here will be interesting and significant, will hopefully lead to the development of novel fruitful techniques, and will yield interesting applications and insights in related areas. 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.