Problems in Extremal and Probabilistic Combinatorics

Princeton University, Princeton NJ

Investigators

Abstract

The proposed project covers several important topics in Extremal and Probabilistic Combinatorics. The first group of questions concerns the Ramsey and Turan numbers of sparse graphs. More precisely, the author wants to study degenerate graphs, i.e., graphs in which every subgraph has bounded average degree. Here one goal is to show that such graphs have Ramsey numbers which grow linearly in the size of the graph. An additional goal is to obtain tight estimates for the Turan numbers of degenerate bipartite graphs. Both problems were posed many years ago by Erdos, and despite all efforts are still open. Another set of questions deals mainly with the study of the chromatic and choice numbers of graphs. The author plans to study two conjectures about graphs whose choice number is equal to their chromatic number. Since usually there is a huge gap between these two parameters, cases in which equality holds are extremely interesting. Another set of questions is about asymptotic properties of random graphs. Here investigators goal is to understand the distribution of independent sets of nearly optimal size in sparse random graphs, and use this to determine the asymptotic behavior of its choice number. It is sometimes the case that an existence proof, supplied by the probabilistic method, is not sufficient and it is better to have an explicit construction. One of the major open problems in this field is to construct exponentially large graphs, without a clique or an independent set of size k. In this project investigator intends to consider this problem together with its bipartite version. Leave nothing to chance. This cliche embodies the common belief that randomness has no place in carefully planned methodologies. In modern Combinatorics at least, nothing can be further from the truth. Here the Probabilistic Method has been developed intensively and become one of the most powerful and widely used tools. Use of probability proved to be helpful in tackling many long standing open problems. Another major reason for the development of this method is the important role of randomness in Theoretical Computer Science. Here algorithm which make random choices during its execution proved to be simplest and fastest for many applications. The PI plans to develop new probabilistic tools and techniques and apply them to various combinatorial problems. Some of these problems and conjectures have been open for few decades.