Graphs and Hypergraphs

图和超图

• 批准号: 170450-2013
• 负责人: Brown, Jason
• 金额: $ 1.38万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=635567
• 关键词: Graphs; Hypergraphs

The first part of the project concentrates on answering a variety of graph theoretical questions via connections to other branches of mathematics. First, using analytic, algebraic and combinatorial techniques, I will investigate problems related to the roots of such polynomials in terms of the the largest modulus, real and imaginary parts among graphs of order n. As well, new generalizations of colouring polynomials have arisen that take into account forbidden sets of colours at the vertex sets, and some difficult extremal problems require more attention. Connections have suggested that a deeper exploration of the algebras over finite fields as a way to further bound the polynomials and locate their roots. Also, I plan to investigate whether a famous open problem on the colouring number of a certain product of two graphs might yield to a matrix-theoretic approach.In network reliability, I plan to continue to explore analytic properties of these polynomials, ranging from location of the roots and fixed points to new notions of optimality of reliability polynomials, using integrals. Also, I plan to complete development for the theory of a new local (rather then global) measure of robustness, that may be more useful for social networks. I propose to investigate an abstract notion of convexity both graph theoretically and analytically via associated polynomials. I also plan to explore a matrix-theoretic approach to Tutte's 5-flow problem, utilizing counting principles, to bound the number of 5-flows of a graph in terms of the dimensions of certain subspaces. Certain vector spaces associated with hypergraphs have only recently been explored, and there is much work to be done yet on connecting up structural properties of the hypergraphs with the vector space dimension (and bases) of the associated spaces. Results are likely to help provide new insights into the building blocks of families of hypergraphs.

该项目的第一部分集中于通过与其他数学分支的连接来回答各种图论问题。首先，使用分析、代数和组合技术，我将研究与n阶图中最大模、真实的和虚部等多项式的根相关的问题。此外，新的广义的着色多项式已经出现，考虑到禁止集的颜色在顶点集，一些困难的极值问题需要更多的关注。联系表明，更深入地探索有限域上的代数作为进一步约束多项式和定位其根的一种方式。此外，我计划调查是否一个著名的公开问题的着色数的某个产品的两个图形可能产生的矩阵理论approaches.In网络的可靠性，我计划继续探索这些多项式的分析性质，从位置的根和不动点的可靠性多项式的最优性的新概念，使用积分。此外，我计划完成一个新的本地（而不是全局）鲁棒性度量理论的开发，这可能对社交网络更有用。我建议调查一个抽象的概念，凸性的图形理论和分析通过相关的多项式。我还计划探索一个矩阵理论的方法Tutte的5流问题，利用计数原则，绑定的数量5流的图形在某些子空间的尺寸。某些与超图相关的向量空间直到最近才被探索，在将超图的结构性质与相关空间的向量空间维数（和基）联系起来方面还有很多工作要做。结果可能有助于提供新的见解的超图族的积木。