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

极值和概率图论：谱、子图计数和图序列

• 批准号: 0906634
• 负责人: Bela Bollobas
• 金额: $ 49.55万
• 依托单位: University of Memphis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-06-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0906634&HistoricalAwards=false
• 关键词: Extremal; Probabilistic; Graph; Theory; Spectra

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.

摘要 首席研究员：Bollobas, Bela 联合首席研究员：Vladimir Nikiforov 提案编号：DMS - 0906634 机构：孟菲斯大学 标题：极值和概率图论：谱、子图计数和图序列 该奖项由 2009 年美国复苏和再投资法案资助（公法 111-5）。在过去十年的“全球”问题中，有关图的类和序列的问题在图论中脱颖而出。 Alon、Chung、Borgs、Chayes、Lovasz、Balogh、Morris 研究了图的遗传特性、稠密图和稀疏图序列、非齐次随机图类、图代数、过饱和图族和图族谱。博洛巴斯、拉兹博罗夫、尼基福罗夫和赖尔丹等等。目前研究人员的主要目标是开发光谱、分析和随机技术来解决这些领域中的一些主要开放问题。特别是，研究人员将重点关注稀疏图的收敛序列、子图计数以及谱与图结构及其经典不变量的关系等问题。图论是数学最年轻的分支之一，仍远未成熟。尽管几十年来它一直在获取工具，但其大部分进展仍然必须依赖巧妙的临时方法。任何使成熟的数学分支方法与图论的主要问题相关的举措都必须受到欢迎。通过展示经典分析和概率论工具如何应用于图论问题，研究人员将尝试将现代图论的重要领域纳入传统数学的范畴。其中大多数领域也受到计算机科学家的深入研究，并应用于网络以及高效算法的设计和分析。