Graphs and digraphs

The first part of the proposed research centers on combinatorial polynomials, from graph colourings to network reliability and independence polynomials. Algebraic and analytic techniques will be used to not only bound network reliability, both in the undirected and directed cases, but also to examine the underlying combinatorial structures. Locating the roots of the polynomials will shed more light on the outstanding unimodality problems of the underlying coefficients, as well as provide more insight into a newly defined class of fractals associated with independence in both graphs and simplicial complexes. I plan to continue to investigate strongly connected reliability, a useful measure of the robustness of a directed graph. In particular, there is an associated new simplicial complex that has not been previously studied, and its properties may help to efficiently bound this reliability measure. A new approach will involve compressing the directed and undirected graphs first with appropriate wavelets. Associated with every abstract simplicial complex are homology groups, and algebraic and topological properties of these combinatorial structures sometimes have import on unsolved discrete problems. The project will look at developing more of the broad connections between these, with applications to network reliability and graph colourings. I also plan to investigate applications of mathematics to music. Independence polynomials of highly structured graphs are related to counting consonant chords in equally tempered scales with n tones, and there are still open problems concerning this enumeration problem. A characterization of tilings of finite cyclic groups will be useful in generating rhythmic canons. More importantly, I plan to construct markov-like models for both melodic and harmonic aspects of songs. The models will take into account not only song structure but key modulation as well. The models will be of use not only for algorithmic composition, but also for authorship identification.