Graphs and Polynomials

图和多项式

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

Underlying many real-world applications of mathematics are graphs, which are models that consists of objects (vertices), and ordered or unordered pairs (edges) that indicate relationships between the objects. Computer and social networks, storage facilities, and scheduling all yield graphs for which the salient problems (whether they consist of connectivity or resource allocation) can be reformulated in mathematical terms, as properties of the underlying graphs.******For a number of these problems, the models include associated functions, which turn out to be of the simplest kind, namely polynomials. Network reliability measures the robustness of a network, under the assumption that vertices are always working but the edges operate independently with a fixed probability. Chromatic polynomials count the number of ways to properly colour the vertices of a graph so that vertices joined by an edge (indicating some form of incompatibility) are coloured differently. Moreover, sometimes the best way to study sequences of numbers that relate to a property of graphs (such as being independent or being a clique) is to form what is called a generating polynomial and to study mathematical properties of the latter. ******In my research program, the algebraic and analytic properties of all such graph polynomials will be investigated, in order to get a deeper understanding of both the important applications at hand, and the theoretical underpinnings of the graph properties in question. Methods and tools will be developed from a variety of areas of mathematics (such as real and complex analysis, algebra and probability) that can also be applied in other settings where combinatorial structures form the basis. Zeros of polynomials will play a prominent role, as their location can produce much useful information about approximations of the functions and the shape of their coefficients (such as whether the sequence is unimodal). Classical results and new techniques (both for univariate and multivariate polynomials, such as those of Gauss, Schur, Hermite, Beraha, Kahane, Weiss, Chudnovsky and Seymour, Borcea and Branden) will play an important role in the research. It is anticipated that novel methods for bounding and approximating the graph polynomials will arise, stronger than previously known approaches, from the interplay between the interdisciplinary mathematical methodology and computational theory. As well, homology of neighbourhood complexes will inform us on the difficult problem of 3-colourability of graphs.******The research will be useful not only to theoreticians who work on outstanding graph problems and physicists who are interested in the interplay between local interactions and global behavior in Potts models, but also to those in applied settings (scheduling and transportation networks) who are implementing algorithms for graph colourings and are designing optimal (or near optimal) networks.

数学在现实世界中的许多应用都是图，图是由对象（顶点）和指示对象之间关系的有序或无序对（边）组成的模型。计算机和社交网络、存储设施和调度都产生了图，其中的突出问题（无论它们是由连通性还是资源分配组成）都可以用数学术语重新表述为底层图的属性。对于这些问题中的一些，模型包括相关的函数，这些函数是最简单的类型，即多项式。网络可靠性衡量网络的鲁棒性，假设顶点总是工作，但边以固定的概率独立运行。色多项式计算了正确着色图的顶点的方法的数量，使得由边连接的顶点（指示某种形式的不兼容性）被不同地着色。此外，有时研究与图的性质（例如独立或团）有关的数列的最佳方法是形成所谓的生成多项式并研究后者的数学性质。** 在我的研究计划中，所有这些图多项式的代数和分析性质将被研究，以便更深入地了解手头的重要应用以及所讨论的图性质的理论基础。方法和工具将从各种数学领域（如真实的和复杂的分析，代数和概率），也可以应用于其他设置组合结构形成的基础。多项式的零点将发挥重要作用，因为它们的位置可以产生关于函数近似及其系数形状的许多有用信息（例如序列是否是单峰的）。经典的结果和新的技术（无论是对一元和多元多项式，如高斯，舒尔，埃尔米特，Beraha，Kahane，韦斯，Chudnovsky和西摩，Borcea和布兰登）将发挥重要作用的研究。可以预见，新的方法将出现边界和近似的图形多项式，强于以前已知的方法，从跨学科的数学方法和计算理论之间的相互作用。同样，邻域复形的同调将告诉我们关于图的3-可着色性的难题。这项研究将是有用的，不仅是谁的理论家工作在突出的图形问题和物理学家谁感兴趣的局部相互作用和全局行为之间的相互作用在波茨模型，但也对那些在应用设置（调度和运输网络）谁是实施算法的图形着色和设计最优（或接近最优）的网络。