Extremal Problems in Combinatorics and Their Applications

点击翻译按钮获取中文摘要

Principal Investigator: Shapira, Asaf Proposal Number: DMS - 0901355Institution: GA Tech Research Corporation - GA Institute of TechnologyTitle: Extremal Problems in Combinatorics and Their ApplicationsThis award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).The proposed research aims to study several fundamental problems in extremal combinatorics, many of them motivated by problems in theoretical computer science. One area of investigations is the relation between local and global properties of graphs, an area in which the PI has been conducting a systematic study of several major open problems in the past few years, and where several open problems have been resolved in collaboration with several other researches. We describe several open problem of this flavor related both to dense and sparse graphs, an area with many intriguing open problems, like the size of the smallest non-planar subgraph in a graph that is far from being planar. A second area of research is the theory of quasi-random graphs, where the PI has recently resolved, jointly with R. Yuster (Haifa U.), several open problems. We intend to work on some central problems that may also have some algorithmic applications. A third area is the study of Szemeredi's regularity lemma of graph and hypergraphs where the PI hopes to prove tight bounds on the size of the smallest regular partition in hypergraphs. Another area of research is additive number theory, where the PI has recently resolved an open problem related to the removal properties of sets of linear equations, and where the PI intends to work on problems like characterizing the linear equations that have nearly linear sized subset of the first n integers with no solution. Finally, another topic of recent investigation is purely algorithmic problems like understanding the true difference between computing shortest paths in directed and undirected graphs.The problems suggested in this project proposal are related to problems that are currently being investigated by many researches in several areas of discrete mathematics like graph theory, extremal combinatorics, additive number theory and theoretical computer science. Therefore, the PI expects that the results and techniques that will be developed as a result of this project will have applications in several mathematical areas. Furthermore, as is explained in the main body of this proposal, many of the suggested problems are motivated by questions in computer science and have many interesting applications. Several of the results of the PI, which were obtained in recent years, appeared in leading computer science conferences and the PI intends to present the results which will be obtained as a result of this project so that they will be broadly disseminated. We also plan on developing graduate and undergraduate courses that will present the links between discrete mathematics and computer science that will emerge from the results covered by this proposal