On structures of large graphs

近年来，大规模网络在许多科学领域中变得越来越重要。这类网络的例子不仅包括交通网络和计算机网络等传统网络，还包括社交网络(如Facebook)和生物神经网络(如人脑)。由于图是这些网络的数学模型，对这些大规模网络的研究需要更好地理解大型图的行为。本研究项目所研究的主题是关于大型图的基本性质。这些问题的研究结果将对图论的许多领域产生重大影响。特别是，该项目的结构结果可以为大型图上的相关问题带来更有效的算法。准确地说，PI将研究以下三个基本问题：(1)他将刻画不包含大K_(3，n)-子式的图。(这个图之所以特殊，是因为这一领域的研究人员认为它是图的高亏格的主要原因。PI建议证明一个6-连通K_(3，n)-Free图一定有一个小亏格或小树宽。)(2)他将为大的4-连通图建立一个分裂定理。(这些类型的结果是非常基本的，作为有用的工具，它们将有非常广泛的应用。)(3)他将刻画可以在射影平面上绘制的无彼得森图。(有理由相信这类图为一般的无Petersen图提供了重要的构建块。一个肯定的结果可以为刻画无Petersen图的一般问题提供新的线索。)

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.)