Existence of Specific Paths, Cycles, and Colorings in Graphs and Hypergraphs

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Extremal problems on graphs and hypergraphs naturally arise in different areas of science, such as information theory, electrical engineering, statistical physics, and molecular biology. This is a large fast developing area with deep ideas and powerful tools. The area also is closely related to other parts of mathematics, computer science and operation research. We consider two types of basic extremal problems on graphs and hypergraphs: on the existence of paths and cycles of a given kind and on special partitions of the set of vertices or edges of a (hyper)graph (mainly involving its cycle structure). Since cycles and paths are very natural substructures of graphs and hypergraphs, understanding problems on their existence will help in resolving other extremal problems. The PI plans to involve into work on the problems of the grant several graduate students and very recent graduates of the University of Illinois. The research guidance for them contributes to their professional development and reputation. The goal of this project is to study a series of extremal problems related to paths and cycles in graphs and hypergraphs and to colorings, especially when the answers depend on the cycle structure. In fact, in most coloring problems the cycle structure is important. In a number of problems we will consider (hyper)graphs with restrictions on degree structure. Examples are: (hyper)graphs with bounded maximum degree, or with bounded maximum average degree, or with given degeneracy, or k-regular, or with high minimum degree. Among important topics are Turan-type problems on cycles and paths in graphs and ordered graphs, problems on different kinds of cycles and paths in hypergraphs, extremal problems on different types of coloring, Ramsey-type problems for cycles and paths, DP-colorings, list coloring, improper colorings, graph reconstruction problems when the known subgraphs have less than n-1 vertices, saturation problems for hypergraphs. Work in these directions will exploit and hopefully develop recent advances in the field including the results and ideas of the PI and his co-authors, in particular, graduate students working with him. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.