Download como arquivo ICAL
Seminário de TCCO
Sexta-feira 19 Julho 2019, 14:00 - 15:30
Contato: Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.
Colouring and Homomorphisms
Palestrante: Chris Godsil (Combinatorics & Optimization, University of Waterloo)

Abstract: A textsl{graph homomorphism} from graph $X$ to a graph $Y$ is a map $phi$ from $V(X)$ to $V(Y)$, such that if $a$ and $b$ are adjacent vertices in $X$, their images $phi(a)$ and $phi(b)$ are adjacent in $Y$. The most well known and important case is when $Y$ is the complete graph on $c$ vertices, in which case $phi$ would usually be referred to as a $c$-colouring. However there are other interesting and important cases, for example, we might take $Omega(d)$ to be the graph with the unit vectors in $mathbb{R}^d$ as vertices, where two unit vectors are adjacent if they are orthogonal. Then a homomorphism $XtoOmega(d)$ corresponds to a so-called orthogonal representation of a graph. Recent work in quantum information theory has lead to the concept of /textsl{quantum colourings}. These can be defined in terms of homomorphisms into graphs with the unitary group of $dtimes d$ matrices as vertices---no physics is needed.
Local : IME-USP - Bloco B - Auditório Jacy Monteiro