Graph Polynomials - Part II
Org: Danielle Cox
(Mount Saint Vincent Universityx) and Christopher Duffy
- DANIELLE COX, Mount Saint Vincent University
Optimal Graphs for Domination Polynomials [PDF]
Let $G$ be a graph on $n$ vertices and $m$ edges and $D(G,x)$ the domination polynomial of $G$. In this talk we will completely characterize the values of $n$ and $m$ for which optimal graphs exists for domination polynomials. Applications to network reliability will be highlighted. This is joint work with Iain Beaton (Dalhousie University) and Jason Brown (Dalhousie University).
- CHRISTOPHER DUFFY, University of Saskatchewan
The Oriented Chromatic Polynomial [PDF]
One can define a $k$-colouring of an oriented graph to be a homomorphism to a tournament on $k$ vertices. This definition implies a definition of the oriented chromatic polynomial. In this talk we examine the behaviour of oriented chromatic polynomial. We classify chromatically equivalent pairs of graphs and oriented graphs. This leads to a new question of of chromatic equivalence — can one find a graph $\Gamma$ and an oriented graph $G$ so that $G$ is not an orientation of $\Gamma$, yet they have the same chromatic polynomial?
Joint work with Danielle Cox (MSVU)
- NICHOLAS HARVEY, University of British Columbia
Computing the Independence Polynomial in Shearer's Region for the Lovasz Local Lemma [PDF]
The independence polynomial has been widely studied in algebraic graph theory, in statistical physics, and in algorithms for counting and sampling problems. We consider the problem of computing the independence polynomial with a negative (or even complex) argument, whose magnitude is less than the smallest magnitude of any root of the polynomial. We show that there is a fully-polynomial-time approximation scheme (FPTAS) for such an argument. Our proof uses a novel multivariate form of the correlation decay technique. This FPTAS can be used to give a constructive algorithm for the Lovasz Local Lemma in probabilistic combinatorics.
- DAVID WAGNER, University of Waterloo
Ursell inequalities for random spanning trees [PDF]
The spanning tree enumerator of a graph is a multivariate polynomial which governs the behavior of several quasi-physical processes on the graph: random spanning trees, electrical networks, and random walks, among others. I will sketch how to combine these ideas in order to derive some new higher-order correlation inequalities for the random spanning tree model.