Spectral and Extremal Graph Theory with Applications

谱与极值图论及其应用

• 批准号: 9801446
• 负责人: Fan Chung Graham
• 金额: --
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-07-01 至 1999-06-22
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9801446&HistoricalAwards=false
• 关键词: Spectral; Extremal; Graph; Theory; Applications

Graham 9801446 This project involves several interrelated areas in spectral graph theory, extremal graph theory, and quasi-random graphs. The goal is to deduce the fundamental properties and structures of a graph from its graph spectrum or from a short list of easily computable invariants. One approach is to examine the relationship of various graph properties and to identify large equivalence classes of graph properties. Geometric methods are used to derive spectral bounds and to improve the rate of convergence for random walk problems. Part of the research is closely coupled with the study of very large graphs in connection with many combinatorial problems arising in massive data sets. This research is in the area of combinatorics. One of the goals of combinatorics is to find efficient methods for manipulating and enumerating discrete collections of objects. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.

格雷厄姆9801446 这个项目涉及到谱图理论、极值图理论和拟随机图中几个相互关联的领域。 其目标是从图的谱或从一个简单的可计算的不变量列表中推导出图的基本性质和结构。一种方法是检查各种图形属性之间的关系，并确定图形属性的大等价类。几何方法被用来推导谱界和提高随机游动问题的收敛速度。部分研究是紧密结合在一起的研究非常大的图与许多组合问题中出现的海量数据集。 这项研究属于组合学领域。组合数学的目标之一是找到有效的方法来操作和枚举离散的对象集合。离散系统的行为对现代通信极为重要。例如，大型网络的设计，如电话系统中的网络设计，以及计算机科学中的算法设计，都要处理离散的对象集，这就需要使用组合研究。