Problems in Probabilistic Combinatorics

Princeton University, Princeton NJ

Investigators

Abstract

1. The proposed project covers several topics in Probabilistic Combinatorics. The first group of questions is about graph colorings. It mainly deals with the study of chromatic and choice numbers of graphs satisfying certain local conditions. One of the open problem which investigators will study is bounding the chromatic number of a graph G with maximum degree d, which contains no copy of a fixed graph H. A variant of this problem was posed already twenty years ago by Komlos and Szemeredi and so far it was solved only for some special cases. Investigator also plans to work on a few related questions about vertex list coloring and acyclic edge coloring of graphs. Another set of questions is about asymptotic properties of random graphs and random regular 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. He also plans to study the properties of pseudo-random graphs and their applications. 2. 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.