University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Algebraic Graph Theory Seminar- Chris GodsilExport this event to calendar

Thursday, October 18, 2018 — 1:30 PM EDT

Title: Graphs of Homomorphisms

Speaker: Chris Godsil
Affiliation: University of Waterloo
Room: MC 6486

Abstract: If X and Y are graphs and f is a function on V (X) taking values in V (Y ), then the graph of
f is the subset formed by the pairs (x; f(x)) for x in V (X). (This is a graph as in Calculus. I
am not responsible for the notational clash.)
I will discuss a product of the graphs X and Y (with vertex set V (X)V (Y )) with the property
that there is a homomorphism from X to Y if and only if the graph of the homomorphism is
a coclique in the product. I will show how standard eigenvalue bounds can then be used to
derive constraints on the existence of homomorphisms, and on the maximum size of induced
k-colourable subgraphs. Some of this theory extends to quantum homomorphisms of graphs,
but I will not say much about this.

Location 
MC - Mathematics & Computer Building
6486
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
  1. 2021 (37)
    1. April (6)
    2. March (13)
    3. February (8)
    4. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)