Graphs and Polynomials

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

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.