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

图和超图的极值问题自然出现在不同的科学领域，如信息论、电子工程、统计物理和分子生物学。这是一个快速发展的大领域，有着深刻的思想和强大的工具。该领域也与数学、计算机科学和运筹学的其他部分密切相关。我们考虑了图和超图上的两类基本极值问题：给定类型的路径和环的存在性问题和（超）图的顶点集或边集的特殊划分问题（主要涉及其环结构）。由于循环和路径是图和超图非常自然的子结构，理解它们存在的问题将有助于解决其他极端问题。PI计划让伊利诺伊大学的几名研究生和刚毕业的学生参与到研究项目中来。对他们的研究指导有助于他们的专业发展和声誉。本课题的目标是研究一系列与图和超图中的路径和循环以及着色有关的极值问题，特别是当答案依赖于循环结构时。事实上，在大多数着色问题中，循环结构是重要的。在许多问题中，我们将考虑对度结构有限制的（超）图。例子有：有界最大度图，有界最大平均度图，给定简并度图，k规则图，高最小度图。其中重要的主题是图和有序图的环和路径上的turan型问题，超图中不同类型的环和路径上的问题，不同类型染色上的极值问题，环和路径上的ramsey型问题，dp染色，列表染色，不正当染色，已知子图的顶点数小于n-1时的图重构问题，超图的饱和问题。这些方向的工作将利用并有望发展该领域的最新进展，包括PI及其合著者的结果和想法，特别是与他一起工作的研究生。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.