Graphs and 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.