IOWA STATE UNIVERSITY
Grant: $174,993 - National Science Foundation - Aug. 2, 2009
No votes have been cast for this award yet
Join the conversation: Post a comment about this award
Award Description: INTELLECTUAL MERIT Rapidly growing volumes of information arising from, for example, biological data, present modern science with the challenge of processing and analyzing this information efficiently. Recent advances in discrete mathematics have proven that our understanding of extremal and structural graph properties provided qualitatively new approaches in fundamental research. These approaches have lead to new knowledge about complex networks with applications in biology and computer science. The overall objective of this application is to narrow the gaps in the knowledge about large discrete structures by pursuing the following specific aims: the investigation of hereditary graph properties from the point of view of editing; and studying unavoidable substructures in partitions of combinatorial objects, or Ramsey-type problems. The innovative aspect of the proposed research is developing a relatively new edit direction in combinatorics, and applying new extremal graph theory techniques such as colored homomorphisms and weighted densities to a wide class of network problems. The edit direction proposed is particularly significant for applications in biology and computer science, where networks evolve and change via adding or destroying connections between nodes. Specifically, in measuring the degree of similarity of consensus structures or in hereditary property testing, the techniques developed in graph editing already have proven to be vital. The significance of Ramsey theory is in the deep connections with many areas of pure mathematics and applications: from constructions in additive number theory, the geometry of fractals, harmonic analysis, ergodic theory and topological dynamics, to computational geometry with applications in VSLI designs, dual source codes, and the time complexity of parallel computation. Part of an active and diverse discrete mathematics group at Iowa State University, the PIs have developed a research program focusing on editing and Ramsey-type problems in extremal combinatorics by applying various methods from extremal graph theory, probability, algebra, finite geometry and additive number theory. The expected outcomes of the proposed research include developing an edit distance direction, relating it to a fundamental study of hereditary properties and of graph-defined metric spaces, as well as investigating the properties of unavoidable configurations in partitions of various combinatorial structures under local constraints. BROADER IMPACT Integration of this research project with education will be accomplished through the motivation and teaching of undergraduate and graduate students as well as educating specialists from other disciplines. This research is expected to benefit society as a whole, primarily through developing methods for manipulating large amounts of information represented by complex networks. Implementation of these particular methods will address pressing challenges in the areas of computer science and bioinformatics. Results of the proposed research will be disseminated widely by publishing in peer-reviewed journals, presenting at professional meetings and conferences and posting on the World-Wide Web. The research will have an impact on underrepresented groups, specifically by giving research opportunities to and mentoring women pursuing careers in the mathematical sciences.
Project Description: INTELLECTUAL MERIT Rapidly growing volumes of information arising from, for example, biological data, present modern science with the challenge of processing and analyzing this information efficiently. Recent advances in discrete mathematics have proven that our understanding of extremal and structural graph properties provided qualitatively new approaches in fundamental research. These approaches have lead to new knowledge about complex networks with applications in biology and computer science. The overall objective of this application is to narrow the gaps in the knowledge about large discrete structures by pursuing the following specific aims: the investigation of hereditary graph properties from the point of view of editing; and studying unavoidable substructures in partitions of combinatorial objects, or Ramsey-type problems. The innovative aspect of the proposed research is developing a relatively new edit direction in combinatorics, and applying new extremal graph theory techniques such as colored homomorphisms and weighted densities to a wide class of network problems. The edit direction proposed is particularly significant for applications in biology and computer science, where networks evolve and change via adding or destroying connections between nodes. Specifically, in measuring the degree of similarity of consensus structures or in hereditary property testing, the techniques developed in graph editing already have proven to be vital. The significance of Ramsey theory is in the deep connections with many areas of pure mathematics and applications: from constructions in additive number theory, the geometry of fractals, harmonic analysis, ergodic theory and topological dynamics, to computational geometry with applications in VSLI designs, dual source codes, and the time complexity of parallel computation. Part of an active and diverse discrete mathematics group at Iowa State University, the PIs have developed a research program focu
Jobs Summary: No job information available at this time. (Total jobs reported: 0)
Project Status: Less Than 50% Completed
This award's data was last updated on Aug. 2, 2009. Help expand these official descriptions using the wiki below.
No comments have been added for this project.