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} minor的图形。 （这张图很特别，因为该领域的研究人员认为这是图形高属的主要原因。PI提议表明6个连接的K_ {3，N} - Free Graph必须具有一个小的属或小的树宽。）（2）他将建立一个大型4-Connectd图的Splitter。 （这些类型的结果非常基本，作为有用的工具，它们将具有非常广泛的应用程序。）（3）他将表征可以在投射平面上绘制的无彼得森图。 （有理由相信这类图为一般无Petersen图表提供了重要的基础。在这里，积极的结果可能会为表征无Petersen的图表的一般问题提供新的启示。）