The proposed project covers several important topics in Extremal Combinatorics. The first group of questions concerns Ramsey Theory. One goal here to understand the asymptotic behavior of diagonal Ramsey numbers of 3-uniform hypergraphs. There is a gap of one exponential between the current upper and lower bounds for these numbers and closing this gap is one of the most challenging questions in the area. The author also plans to study the Ramsey numbers of sparse graphs, i.e., graph in which every subgraph has bounded average degree. It was conjectured 35 years ago by Burr and Erdos that Ramsey numbers of these graphs grow linearly in the number of their vertices. This is one of the central problems in Graph Ramsey Theory which attracted a lot of attention. Another set of questions in this proposal deals with Turan-type problems. In particular PI plans to continue his work on the 40 year old conjecture of Erdos on the Turan numbers of bipartite graphs, in which every subgraph has vertex of degree at most r. He also plans to study the beautiful conjecture of Erdos-Simonovits and Sidorenko which states that the number of copies of bipartite graph H in a n-vertex graph is at least as large as in the random n-vertex graph with the same edge density. This important conjecture has connection to matrix theory, Markov chains, graph limits and quasirandomness.
Combinatorics is a branch of mathematics focusing on the study of discrete objects and their properties. Although Combinatorics is probably as old as the human ability to count, the field experienced tremendous growth during the last fifty years and is one of the most modern in today's Mathematics, with numerous connections to different disciplines and various practical applications, ranging from designing VLSI chips to modeling complex social networks. Is it true that in any company of six people there are three who all know each other, or alternatively are all unfamiliar with each other? Can the countries of any planar map be colored with at most four colors so that no two countries that share a common boundary have the same color? If each link of a complex telephone network fails with probability p, what is the probability that Alice will not be to have a phone conversation with her friend Bob? Questions of this type are in the heart of modern Combinatorics and illustrate various research topics which PI plans to consider.
Combinatorics is a branch of mathematics focusing on the study of discrete objects and their properties. Although Combinatorics is probably as old as the human ability to count, the field experienced tremendous growth during the last fifty years and is one of the most modern in today's Mathematics, with numerous connections to different disciplines and various practical applications, ranging from designing VLSI chips to modeling complex social networks. Is it true that in any company of six people there are three who all know each other, or alternatively are all unfamiliar with each other? Can the countries of any planar map be colored with at most four colors so that no two countries that share a common boundary have the same color? If each link of a complex telephone network fails with probability p, what is the probability that Alice will not be to have a phone conversation with her friend Bob? Questions of this type are in the heart of modern Combinatorics and illustrate various research topics which PI studies. This project covered several important topics in Extremal Combinatorics focusing on questions from Ramsey theory and Turant-type problems. The PI manage to solve several important problems in these areas and published more than 30 paper during three years of this grant. He also gave more than 40 lectures on various interntaional forums, publicising the obtained results
