权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

The Interplay between Spectral and Combinatorial Properties of Graphs and Association Schemes

图的谱属性和组合属性与关联方案之间的相互作用

基本信息

批准号：
1600768
负责人：
Sebastian Cioaba
金额：
$ 13万
依托单位：
University of Delaware
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-08-01 至 2020-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1600768&HistoricalAwards=false
关键词：
Interplay between Spectral Combinatorial Properties

项目摘要

Graph theory is essential for analyzing the structure and function of networks. Often the sizes of such networks are so large that analyzing their structures by brute force is not feasible. The challenge is to use parameters that can efficiently capture the shapes of networks. Spectral graph theory provides important tools for studying structural properties of graphs and has close connections to computer science and network design. Although the eigenvalues do not determine a graph in general, they contain important structural information that in some situations, could not be obtained by any other means. Association schemes are combinatorial and algebraic structures with high degree of regularity that sit at the core of algebraic combinatorics and have important applications in coding theory, geometry and quantum computing. In this project, the close connections between the spectral and combinatorial properties of graphs and association schemes will be investigated. This project will involve graduate and undergraduate students at University of Delaware. This project encompasses recent progress in spectral graph theory on combinatorial and spectral problems and conjectures involving simplicial rook graphs, Wenger graphs and friendship graphs as well as in the theory of association schemes by answering questions of Brouwer regarding the connectivity of strongly regular and distance-regular graphs and their subconstituents. The project will investigate conjectures of Haemers that almost all graphs are determined by their spectrum, of Godsil and Brouwer regarding the edge- and vertex-connectivity of graphs in association schemes as well as related problems such as understanding the spectral and isoperimetric properties of graphs defined by systems of equations over finite fields or graphs arising in other combinatorial problems.

图论对于分析网络的结构和功能是必不可少的。通常，这样的网络的规模是如此之大，以至于通过蛮力分析它们的结构是不可行的。挑战在于使用可以有效捕获网络形状的参数。谱图理论是研究图的结构性质的重要工具，与计算机科学和网络设计有着密切的联系。虽然特征值一般不决定图，但它们包含重要的结构信息，在某些情况下，这些信息无法通过任何其他手段获得。结合方案是具有高度正则性的组合代数结构，是代数组合学的核心，在编码理论、几何学和量子计算中有重要的应用。在这个项目中，将研究图的谱和组合性质与结合方案之间的密切联系。该项目将涉及特拉华州大学的研究生和本科生。该项目包括最近的进展，在谱图理论的组合和谱问题和acetrutures涉及单纯车图，温格图和友谊图，以及在理论上的关联方案，回答问题的布劳威尔关于连接的强正规和距离正规图及其子成分。该项目将研究Haemers的progratures，几乎所有的图都是由它们的谱决定的，Godsil和Brouwer关于关联方案中图的边和顶点连通性以及相关问题，例如理解有限域上的方程组或其他组合问题中产生的图所定义的图的谱和等周性质。