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