Extremal and Probabilistic Graph Theory: Spectra, Subgraph Counts, and Graph Sequences

主要研究人员：Bollobas，Bela共同首席研究人员：Vladimir NikiforovProposal编号：DMS-0906634机构：孟菲斯大学标题：极值和概率图论：谱、子图计数和图序列该奖项由2009年美国复苏和再投资法案(公共法律111-5)资助。在过去十年中，关于图形的类别和序列的问题在图论中脱颖而出。Alon，Chung，Borgs，Chayes，Lovasz，Balogh，Morris，Bollobas，Razborov，Nikiforov和Riordan等人研究了图的遗传性质，稠密和稀疏图的序列，非齐次随机图的类，图代数，过饱和图族和图族的谱。目前研究人员的主要目标是开发光谱、分析和随机技术来解决这些领域中的一些主要公开问题。特别是，研究人员将集中于稀疏图的收敛序列、子图计数、谱与图的结构及其经典不变量的关系等问题。图论是数学中最年轻的分支之一，还远未成熟。尽管几十年来它一直在获取工具，但在其大部分进展中，它仍然不得不依靠巧妙的特别方法。任何使久负盛名的数学分支的方法与图论的主要问题相关的举措都必须受到欢迎。通过展示如何将经典分析和概率论的工具应用于图论问题，研究人员将试图将现代图论的大量领域纳入传统数学的范畴。这些领域中的大多数也得到了计算机科学家的大量研究，并应用于网络和高效算法的设计和分析。

ABSTRACTPrincipal Investigator: Bollobas, Bela Co-Principal Investigator: Vladimir NikiforovProposal Number: DMS - 0906634Institution: University of MemphisTitle: Extremal and Probabilistic Graph Theory: Spectra, Subgraph Counts, and Graph SequencesThis award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).In the past decade `global' questions, questions concerning classes and sequences of graphs have come to the fore in graph theory. Hereditary properties of graphs, sequences of dense and sparse graphs, classes of inhomogeneous random graphs, graph algebras, families of supersaturated graphs, and spectra of families of graphs have been studied by Alon, Chung, Borgs, Chayes, Lovasz, Balogh, Morris, Bollobas, Razborov, Nikiforov, and Riordan, among many others. The main goal of the present investigators is to develop spectral, analytical and random techniques to attack some of the major open problems in these fields. In particular, the investigators will focus on problems of convergent sequences of sparse graphs, subgraph counts, and relations of spectra to the structure of graphs and their classical invariants.Graph theory is one of the youngest branches of mathematics and is still far from maturity. Although it has been acquiring tools for decades, for much of its progress it still has to rely on ingenious ad hoc methods. Any move that makes the methods of well-established branches of mathematics relevant to major problems of graph theory must be welcome. By showing how tools of classical analysis and probability theory can be brought to bear on problems of graph theory, the investigators will attempt to bring substantial areas of modern graph theory into the fold of traditional mathematics. Most of these areas are much studied by computer scientists as well, and have applications to networking and the design and analysis of efficient algorithms.