Extremal Problems in Combinatorics and Their Applications

主要研究者：Shapira， Asaf提案编号：DMS - 0901355机构：GA技术研究公司- GA技术研究所标题：组合学中的极端问题及其应用该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。提出的研究旨在研究极值组合学中的几个基本问题，其中许多问题是由理论计算机科学的问题引起的。研究的一个领域是图的局部和全局性质之间的关系，PI在过去几年中对几个主要的开放问题进行了系统的研究，其中一些开放问题已经与其他几个研究合作解决了。我们描述了几个与密集图和稀疏图相关的开放问题，这是一个有许多有趣的开放问题的领域，比如图中最小的非平面子图的大小，而图远非平面。第二个研究领域是准随机图理论，PI最近与R. Yuster （Haifa U.）共同解决了几个开放问题。我们打算研究一些核心问题，这些问题也可能有一些算法应用。第三个领域是图和超图的Szemeredi正则引理的研究，PI希望证明超图中最小正则分区大小的紧界。另一个研究领域是加性数论，PI最近解决了一个与线性方程集的去除性质有关的开放问题，PI打算研究诸如描述线性方程的问题，这些方程具有近线性大小的前n个整数子集，没有解。最后，最近研究的另一个主题是纯粹的算法问题，比如理解有向图和无向图中计算最短路径的真正区别。本项目提案中提出的问题与离散数学中图论、极值组合、加性数论和理论计算机科学等多个领域的许多研究人员目前正在研究的问题有关。因此，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