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

图和超图上的极值问题自然出现在不同的科学领域，如信息论、电子工程、统计物理和分子生物学。这是一个巨大的快速发展领域，拥有深厚的理念和强大的工具。该领域还与数学、计算机科学和运筹学的其他部分密切相关。我们考虑了图和超图上的两类基本极值问题：一类是给定类型的路和圈的存在性问题，另一类是(超)图的顶点或边集的特殊划分问题(主要涉及其圈结构)。由于圈和路是图和超图的非常自然的子结构，了解它们的存在问题将有助于解决其他极值问题。PI计划让几名伊利诺伊大学的研究生和新近毕业的学生参与到补助金问题的工作中来。本项目的目标是研究图和超图中与路和圈有关的一系列极值问题，特别是当答案取决于圈的结构时。事实上，在大多数着色问题中，圈结构是重要的。在一些问题中，我们将考虑对度结构有限制的(超)图。例如：具有有界最大度、有界最大平均度、具有给定退化度、或具有k-正则、或具有高最小度的(超)图。图和有序图中关于圈和路的Turan型问题，超图中不同类型的圈和路的Turan型问题，不同类型着色的极值问题，圈和路的Ramsey型问题，DP-着色，列表着色，不适当的着色，当已知子图的顶点少于n-1时的图重构问题，超图的饱和问题。这些方向的工作将开发并有望发展该领域的最新进展，包括PI和他的合著者，特别是与他一起工作的研究生的结果和想法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.