On structures of large graphs

关于大图的结构

• 批准号: 1500699
• 负责人: Guoli Ding
• 金额: $ 20万
• 依托单位: Louisiana State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-01 至 2019-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1500699&HistoricalAwards=false
• 关键词: structures; large; graphs

In recent years, large-scale networks become more and more important in many fields of science. Examples of such networks include not only traditional networks like transportation networks and computer networks, but also social networks (like Facebook) and biological neural networks (like human brains). Since graphs are mathematical models of these networks, the study of these large-scale networks demands a better understanding of the behavior of large graphs. The topics under study in this research project are concerned with fundamental properties of large graphs. Results on these questions will have strong impact on many areas of graph theory. In particular, structure results coming out of this project could lead to more efficient algorithms for related problems on large graphs. These algorithms would in turn impact the study of large-scale networks from the real world.To be precise, the PI will study the following three fundamental problems: (1) He will characterize graphs that do not contain a large K_{3,n}-minor. (This graph is special because researchers in this area believe that it is the main reason for a high genus of a graph. The PI proposes to show that a 6-connected K_{3,n}-free graph must have a small genus or small tree-width.) (2) He will establish a splitter theorem for large 4-connectd graph. (These types of results are very fundamental and, as useful tools, they will have a very wide range of applications.) (3) He will characterize Petersen-free graphs that can be drawn on the projective plane. (There are reasons to believe that this class of graphs provide important building blocks for general Petersen-free graphs. A positive result here could shed new light on the general problem of characterizing Petersen-free graphs.)

近年来，大规模网络在许多科学领域变得越来越重要。这样的网络的例子不仅包括传统的网络，如交通网络和计算机网络，还包括社交网络（如Facebook）和生物神经网络（如人脑）。由于图是这些网络的数学模型，因此研究这些大规模网络需要更好地理解大型图的行为。在这个研究项目中正在研究的主题是关于大型图的基本性质。这些问题的结果将对图论的许多领域产生重大影响。特别是，这个项目的结构结果可能会导致更有效的算法在大型图上的相关问题。这些算法将反过来影响从真实的世界中研究大规模网络，具体来说，PI将研究以下三个基本问题：（1）刻画不包含大K_{3，n}-子式的图。(This图是特殊的，因为这方面的研究者认为这是图的高亏格的主要原因。PI提出证明一个6-连通无K_{3，n}图必须有一个小亏格或小树宽。(2)他将建立一个大的4-连通图的分裂定理。（这些类型的结果是非常基本的，作为有用的工具，它们将有非常广泛的应用。(3)他将描述彼得森自由图，可以画在投影平面上。（有理由相信这类图为一般的Petersen自由图提供了重要的构建块。这里的一个肯定结果可以为刻画Petersen-free图的一般问题提供新的线索。