Extremal problems on hereditary properties and partitions of combinatorial structures

主要研究者：Axenovich，Maria 共同主要研究者：Martin，Ryan提案编号：DMS -0901008机构：爱荷华州州立大学题目：组合结构的遗传性质和划分的极值问题该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。该提案的首要主题是研究组合对象中的局部子结构，主要是网络。给定的子结构在多大程度上是不可避免的？拉姆齐理论指出，在足够大的系统中，某些子结构总是不可避免的。其他可以通过局部修改来避免，例如，在图中，边删除和添加。该提案部分涉及图形的有效修改，称为图形编辑。寻找从图到遗传属性的编辑距离提供了对此类属性的一般结构的洞察，并且具有许多应用，例如属性测试。为解决这个问题而提出的技术包括伪随机图、规则划分、着色同态和优化--所有这些都有望在图论的其他方面发挥作用。在不可避免的组合结构的研究中，这个建议解决了一个广义的拉姆齐问题，其中的子结构没有明确给出，而是由一组参数确定。 例如，这样的参数可以是边着色图的给定子图上存在的颜色的数量。 该研究主要探讨了经典拉姆齐问题和反拉姆齐问题之间的平衡。PI的研究属于图论学科，这是对网络及其属性的研究，并在各种其他学科中有应用，包括计算机科学，生物信息学，运筹学和经济学。 研究生和合作是PI研究的组成部分。 这个建议的主要目标是解决两个基本问题：“在大型系统中，如网络，哪些结构是不可避免的？如何有效地修改（编辑）网络以满足所需的属性？“这些问题的答案将使人们更好地理解网络，特别是那些来自科学应用的网络。

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.