This proposal outlines a challenging career developments plan focusing on several fascinating problems in Discrete Mathematics. Specific areas in which PI plans to work include Ramsey Theory, Graph colorings, Extremal Combinatorics and Random and pseudo-random graphs. Furthermore the author plan to study application of all these areas to Theoretical Computer Science. The main tools which are going to be used in this investigation combine combinatorial techniques, probabilistic methods, tools from Linear Algebra and spectral techniques amongst the others. First group of questions in this proposal deals with Ramsey numbers. The author wants to bound these numbers for sparse graphs, i.e., graphs in which every subgraph has bounded average degree. Here the goal is to show that such graphs have Ramsey numbers which grow linearly in the size of the graph. An additional topic is to study various extremal problems. In particular to obtain extensions of classical Turan's theorem and prove better bounds on the Max Cut in the graphs with forbidden subgraphs. Some of these 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. Usually there is a huge gap between these two parameters, so one of the goals in this proposal is to understand the graphs for which chromatic and choice numbers are equal. Finally the PI also intends to study the asymptotic properties of random and pseudo-random graphs which is one of the central topics in Probabilistic Combinatorics.
Concepts and questions of Combinatorics appear naturally in many branches of mathematics, and have also found applications in other disciplines. These include applications in Information Theory and Electrical Engineering, in Statistical Physics and Molecular Biology, and most notably in Computer Science. The PI is convinced that progress in the problems he discusses will be interesting and significant, and will lead to new developments in Discrete Mathematics. He believes that the new approaches and techniques resulting from this project will be applicable and useful in other fields as well. The author also proposes a wide range of educational measures closely related to his project. He plans to develop a series of courses for senior undergraduate and starting graduate students, which will serve as a gentle introduction to the variety of powerful methods in modern Combinatorics. Part of these courses will be closely related to the research problems in this proposal. Along the course, the author plans to integrate research activities into the teaching by introducing open questions that will motivate the students to undertake research on these fascinating topics, which can lead to a B.A. thesis or Ph.D. dissertation.
