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 - David RobersonExport this event to calendar

Monday, August 10, 2020 — 11:30 AM EDT

Title: What do graph planarity and homomorphism counts have to do with quantum mechanics?

Speaker: David Roberson
Affiliation: Technical University of Denmark
Zoom: Contact Soffia Arnadottir

Abstract:

I will introduce the notion of quantum isomorphisms of graphs. These are defined in terms of a game in which two cooperating players attempt to convince a referee that two given graphs are isomorphic. Classically, the players can achieve this with probability 1 if and only if the graphs are indeed isomorphic. However, if the players are allowed to perform local quantum measurements on a shared entangled state, then for some pairs of non-isomorphic graphs they are still able to convince the referee with probability 1. We say that such graphs are quantum isomorphic. After introducing this notion I will discuss the recent result of myself and Mancinska where we show that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any *planar* graph. This can be seen as a quantum analog of Lovasz' result from 1967 saying that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph.

S M T W T F S
27
28
29
30
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
31
  1. 2020 (105)
    1. November (3)
    2. October (12)
    3. September (12)
    4. August (11)
    5. July (17)
    6. June (11)
    7. May (6)
    8. March (11)
    9. February (11)
    10. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (136)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)