 english accueil réunion accueil canadam

Graph Polynomials - Part I
Org: Danielle Cox (Mount Saint Vincent University) et Christopher Duffy (University of Saskatchewan)
[PDF]

IAIN BEATON, Dalhousie University
Independence Equivalence Class of Paths and Cycles  [PDF]

The independence polynomial of $G$, denoted by $i(G,x)$ is defined by $i(G,x)=\sum_{k=0}^{\alpha}i_kx^k$ where $i_k$ is the number of independent sets of size $k$ in $G$ and $\alpha$ is the independence number. Two graphs $G$ and $H$ are considered independence equivalent if $i(G,x)=i(H,x)$. The independence equivalence class of $G$ is the set of all graphs independence equivalent to $G$. In this talk we will discuss the independence equivalence class of $P_n$ and $C_n$. This is joint work with Jason Brown and Ben Cameron.

BEN CAMERON, Dalhousie University
The Maximum Modulus of an Independence Root  [PDF]

The independence polynomial of a graph is the generating polynomial for the number of independent sets of each size. Its roots are called independence roots. In this talk we will bound $\operatorname{maxmod}(n)$, the maximum modulus of an independence root over all graphs on $n$ vertices, and $\operatorname{maxmod}_T(n)$, the maximum modulus of an independence root over all trees on $n$ vertices. We will show that both values are exponential in $n$. More precisely, we show $$\frac{\log_3(\operatorname{maxmod}(n))}{n}=\frac{1}{3}+o(1)~~~~~~\text{ and }~~~~~~\frac{\log_2(\operatorname{maxmod}_T(n))}{n}=\frac{1}{2}+o(1).$$

This is a joint work with Jason Brown.

LUCAS MOL, University of Winnipeg
The Subtree Polynomial  [PDF]

The subtree polynomial of a tree $T$ is the generating polynomial for the number of subtrees of $T$. The subtree polynomial encodes a variety of interesting parameters of the tree including the total number of subtrees, the mean subtree order, and the independence number. We present a sharp constant bound on the roots of the subtree polynomial of a tree. We then discuss root-free and root-dense intervals of the real line. Finally, we give a short proof of the fact that the path (star, respectively) has coefficient-wise least (greatest, respectively) subtree polynomial. This is joint work with Jason Brown.

LISE TURNER, University of Waterloo
Convergence of Coefficients of the Rank Polynomial in Benjamini-Schramm Convergent Sequences of Graphs  [PDF]

Benjamini-Schramm convergence is a notion of convergence that is based on local behaviour and useful for sparse graphs. We show that it implies a convergence result on the coefficients of the rank polynomial. This is joint work with Dmitry Jakobson, Calum MacRury and Sergey Norin.

MACKENZIE WHEELER, University of Victorica
Chromatic Uniqueness of Mixed Graphs  [PDF]

For simple graphs $G$ and $H$ with chromatic polynomials $P(G,\lambda)$ and $P(H,\lambda)$, $G$ and $H$ are said to be chromatically equivalent if $P(G,\lambda)=P(H,\lambda)$ for all values of $\lambda$. If the only graphs which are chromatically equivalent to $G$ are also isomorphic to $G$, then $G$ is said to be chromatically unique. In this talk we will consider the problem of chromatic uniqueness for mixed graphs and directed graphs. In particular we will present several classes of directed graphs which are chromatically unique, as well as classify mixed graphs which are chromatically equivalent to their underlying graph.