Extremal Problems in Combinatorics and Their Applications

主要研究者：Shapira，Asaf 提案编号：DMS -0901355机构：GA Tech Research Corporation - GA Institute of Technology题目：Extremal Problems in Combinatorics and Their Applications该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。拟议的研究旨在研究极值组合学中的几个基本问题，其中许多问题的动机是理论计算机科学中的问题。调查的一个领域是图的局部和全局性质之间的关系，PI在过去几年中对几个主要的开放问题进行了系统的研究，并且与其他几项研究合作解决了几个开放问题。我们描述了几个开放的问题，这种味道相关的密集和稀疏的图形，一个领域有许多有趣的开放的问题，如最小的非平面子图的大小在一个图，是远离平面。第二个研究领域是准随机图理论，PI最近与R. Yuster（海法大学），几个开放的问题。我们打算研究一些中心问题，这些问题也可能有一些算法应用。第三个领域是研究Szemeredi的正则性引理的图和超图，PI希望证明超图中最小正则分区的大小的严格界限。另一个研究领域是加法数论，其中PI最近解决了一个与线性方程组的移除特性相关的开放问题，并且PI打算研究这样的问题，例如描述具有前n个整数的近似线性大小的子集的线性方程，没有解决方案。最后，最近研究的另一个主题是纯算法问题，如理解有向图和无向图中计算最短路径的真正区别。本项目建议书中提出的问题与离散数学的几个领域（如图论、极值组合学、加法数论和理论计算机科学）的许多研究目前正在研究的问题有关。因此，PI预计，作为该项目的结果，将开发的结果和技术将在几个数学领域的应用。此外，正如本提案的主体部分所解释的那样，许多建议的问题都是由计算机科学中的问题所激发的，并且有许多有趣的应用。PI近年来取得的一些成果出现在主要的计算机科学会议上，PI打算介绍将通过该项目取得的成果，以便广泛传播。我们还计划开发研究生和本科生课程，这些课程将展示离散数学和计算机科学之间的联系，这些联系将从本提案所涵盖的结果中产生

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