COSAM »
Events »
2018 »
February »
DMS Colloquium: Dr. Brendan Rooney
DMS Colloquium: Dr. Brendan Rooney

Time:
Feb 05, 2018 (04:00 PM)

Location:
Parker Hall 250

Details:
Speaker: Dr. Brendan Rooney, Korea Advanced Institute of Science and Technology
Title: Vector Colourings and Graph Homomorphisms
Abstract: A vector colouring of a graph $X$ is a map from $V(X)$ to vectors on the unit sphere in $\mathbb{R}^m$. The goal is to map adjacent vertices to vectors that are far apart. The vector chromatic number of $X$ is the smallest $t\geq 1$ so that there is a vector colouring $\phi$ for which the inner product of $\phi(u)$ and $\phi(v)$ is at most $1/(t1)$, whenever $u$ and $v$ are adjacent.
We look at vector colourings given by representations of a graph on its least eigenspace, and identify a class of graphs for which these colourings are optimal. This leads to a novel approach to proving that a graph is a core, and for proving the nonexistence of homomorphisms between pairs of graphs. As an application we give a new proof that the Kneser graphs $K_{n:r}$ for $n\geq 2r+1$ and $q$Kneser graphs $qK_{n:r}$ for $n\geq 2r+1$ are cores; in particular, a proof that does not require application of the Erd{\H o}sKoRado Theorem.

Last updated:
01/19/2018