Graphs and Polynomials

图和多项式

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

许多现实世界的数学应用都是图，它是由对象（顶点）和指示对象之间关系的有序或无序对（边）组成的模型。计算机和社会网络、存储设施和调度都产生了图形，其中的突出问题（无论它们是由连通性还是资源分配组成）可以用数学术语重新表述为底层图形的属性。