Extremal problems on hereditary properties and partitions of combinatorial structures

首席研究员：阿克森诺维奇，玛丽亚联合首席研究员：马丁，瑞安建议编号：DMS-0901008机构：爱荷华州立大学标题：遗传属性和组合结构划分的极值问题该奖项由2009年美国复苏和再投资法案(公共法律111-5)资助。该建议的总体主题是研究组合对象中的局部子结构，主要是网络。一个给定的子结构在多大程度上是不可避免的？拉姆齐理论指出，在足够大的系统中，某些子结构总是不可避免的。其他的可以通过局部修改来避免，例如，在图中，边删除和添加。该建议部分涉及图形的有效修改，称为图形编辑。求出从图到遗传属性的编辑距离可以深入了解这些属性的一般结构，并有许多应用，如属性测试。提出的解决这个问题的技术包括伪随机图、正则划分、有色同态和优化--所有这些技术都有望在图论的其他方面有用。在研究不可避免的组合结构时，这个建议解决了一个广义Ramsey问题，在这个问题中，子结构不是显式给出的，而是由一组参数决定的。例如，这样的参数可以是出现在边色图的给定子图上的颜色的数量。PI的研究属于图论学科，是研究网络及其性质的学科，它在包括计算机科学、生物信息学、运筹学和经济学在内的许多其他学科中都有应用。研究生和合作是PIS研究的组成部分。该提案的主要目标是解决两个基本问题：“在大型系统中，例如网络，哪些结构是不可避免的？”以及“如何才能有效地修改(编辑)网络，以满足所需的特性？”对这些问题的回答将带来对网络的更好理解，特别是那些产生于科学应用的网络。

ABSTRACTPrincipal Investigator: Axenovich, Maria Co-Principal Investigator: Martin, RyanProposal Number: DMS - 0901008Institution: Iowa State UniversityTitle: Extremal problems on hereditary properties and partitions of combinatorial structuresThis award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).The overarching theme of this proposal is the study of local substructures in combinatorial objects, primarily networks. To what degree is a given substructure unavoidable? Ramsey theory states that certain substructures are always unavoidable in large enough systems. Others could be avoided by local modifications such as, in graphs, edge deletion and addition. This proposal deals, in part, with the efficient modification of graphs, referred to as graph editing. Finding the edit distance from a graph to a hereditary property provides insight into the general structure of such properties and has many applications, such as property testing. The techniques proposed to address this problem include pseudorandom graphs, regular partitions, colored homomorphisms and optimization -- all of which promise to be useful in other facets of graph theory. In the study of unavoidable combinatorial structures, this proposal addresses a generalized Ramsey problem in which the substructures are not given explicitly but rather are determined by a set of parameters. For example, such a parameter can be the number of colors that are present on a given subgraph of an edge-colored graph. This explores, in particular, the balance between classical Ramsey and anti-Ramsey problems.The PIs' research belongs to the discipline of graph theory, which is the study of networks and their properties and which has applications in a wide variety of other disciplines, including computer science, bioinformatics, operations research and economics. Graduate students and collaboration are integral parts of the PIs' research. The main objective of this proposal is to address two fundamental questions: "Which structures are unavoidable in large systems, such as networks?" and "How can one modify (edit) a network efficiently in order to satisfy desired properties?" Answers to these questions will bring a better understanding of networks, specifically those arising from scientific applications.