Extremal problems on hereditary properties and partitions of combinatorial structures

Iowa State University, Ames IA

Investigators

Abstract

ABSTRACT Principal Investigator: Axenovich, Maria Co-Principal Investigator: Martin, Ryan Proposal Number: DMS - 0901008 Institution: Iowa State University Title: Extremal problems on hereditary properties and partitions of combinatorial structures This 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.