CAREER: Graph Structural Theorems, Asymptotic Dimension, and Beyond

职业：图结构定理、渐近维数及其他

• 批准号: 2144042
• 负责人: Chun-Hung Liu
• 金额: $ 40万
• 依托单位: Texas A&M University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2027-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2144042&HistoricalAwards=false
• 关键词: CAREER; Graph; Structural; Theorems; Asymptotic

This project aims to develop structural theorems for graphs and apply them to questions in mathematics and computer science inspired by notions related to geometry. Graphs are combinatorial objects that have been extensively studied in mathematics and used for modeling systems in engineering, statistics, biology, economics, and many other disciplines. Graphs can be used to represent spaces or networks and to encode distance between points in spaces or machines in networks. Asymptotic dimension is a notion that concerns large-scale behaviors of such spaces or networks studied in metric geometry, geometric group theory, and distributed computing. The PI and his collaborators recently used tools from structural graph theory, a central research area in combinatorics, to establish results about asymptotic dimension, showing possibilities for attacking open questions in different areas in mathematics. This project aims to further explore this direction by developing novel structural theorems about graphs motivated by their potential applications to computer science and metric geometry, including but not limited to questions about asymptotic dimension. This project contains an education component, including student mentoring, research opportunities for graduate students and advanced undergraduate students, and course development, with outreach activities designed for K-12 students and the public.The main objective of this project is to develop novel graph structural theorems and apply them to solve open questions in combinatorics, theoretical computer science, and other areas in mathematics. The first direction is to study metric spaces supported by minor-closed families of graphs. Embedding problems and related applications in computer science for such metrics have attracted wide attention. One goal of this project is to develop new structural theorems for minor-closed families to attack those problems. The second direction is to study graph classes with polynomial expansion. Such graph classes have been extensively studied in computer science and geometric graph theory due to its tight connection to separator theory. A goal of this project is to develop decomposition theorems for such classes without involving separator theory to pave a novel way for studying those classes. A potential application is to determine the sparsity hierarchy for graph classes with finite asymptotic dimension. The third direction addresses the emerging induced graph minor theory, which combines graph minor theory and induced subgraph theory, two major directions in structural graph theory. An objective of this project is to study this area by extending the existing graph minor theory for sparse graphs to theory for dense graphs via notions inspired from asymptotic dimension and metric geometry.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.

这个项目的目的是开发图形的结构定理，并将它们应用于数学和计算机科学中的问题，这些问题的灵感来自与几何相关的概念。图是一种组合对象，在数学中得到了广泛的研究，并在工程、统计学、生物学、经济学等许多学科中用于系统建模。图可以用来表示空间或网络，并编码空间中的点或网络中的机器之间的距离。渐近维是度量几何、几何群论和分布式计算中研究的此类空间或网络的大规模行为的概念。PI和他的合作者最近使用了结构图论的工具，这是组合学的一个核心研究领域，建立了关于渐近维度的结果，显示了在数学的不同领域攻击开放问题的可能性。该项目旨在通过开发关于图的新的结构定理来进一步探索这一方向，其动机是图在计算机科学和度量几何中的潜在应用，包括但不限于关于渐近维度的问题。这个项目包含一个教育部分，包括学生指导，为研究生和高级本科生提供的研究机会，以及课程开发，以及为K-12学生和公众设计的外展活动。这个项目的主要目标是开发新的图结构定理，并将它们应用于解决组合学、理论计算机科学和其他数学领域的开放问题。第一个方向是研究次闭图族所支持的度量空间。这种度量的嵌入问题及其在计算机科学中的相关应用引起了广泛的关注。这个项目的一个目标是为未成年人封闭家庭开发新的结构定理来解决这些问题。第二个方向是研究具有多项式展开的图类。由于其与分离子理论的紧密联系，这类图类在计算机科学和几何图论中得到了广泛的研究。这个项目的一个目标是在不涉及分离子理论的情况下发展这类类的分解定理，为研究这类类铺平一条新的途径。一个潜在的应用是确定有限渐近维图类的稀疏层次。第三个方向是新兴的诱导图子图理论，它结合了结构图论中的两个主要方向--图子理论和图子理论。这个项目的一个目标是通过将现有的稀疏图的图次理论扩展到稠密图的理论来研究这一领域，这个奖项受到渐近维度和度量几何的启发。这个奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为是值得支持的。

项目成果

Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth

正确的无冲突列表着色、奇数次要、细分和分层树宽

• DOI: 10.1016/j.disc.2023.113668
• 发表时间: 2024
• 期刊: Discrete Mathematics
• 影响因子: 0.8
• 作者: Liu, Chun-Hung

Phase transition of degeneracy in minor-closed families

• DOI: 10.1016/j.aam.2023.102489
• 发表时间: 2019-12
• 期刊: Adv. Appl. Math.
• 作者: Chun-Hung Liu;F. Wei

Defective Coloring is Perfect for Minors

有缺陷的色彩非常适合未成年人

• DOI: 10.1007/s00493-024-00081-8
• 发表时间: 2024
• 期刊: Combinatorica
• 影响因子: 1.1
• 作者: Liu, Chun-Hung

Clustered coloring of graphs with bounded layered treewidth and bounded degree

具有有界分层树宽和有界度的图的聚类着色

• DOI: 10.1016/j.ejc.2023.103730
• 发表时间: 2023
• 期刊: European Journal of Combinatorics
• 影响因子: 1
• 作者: Liu, Chun-Hung;Wood, David R.
• 通讯作者: Wood, David R.