Thursday, September 27, 2018 — 3:30 PM EDT

Title: A characterization of (p,q)-mixing when p/q < 4

Speaker: Ben Moore
Affiliation: University of Waterloo
Room: MC 5417

Abstract: Let Hom(G,H) be the graph whose vertex set is the set of H-colourings of G, and two H-colourings f and g are adjacent if f differs from g in at most one vertex. The H-mixing problem is to determine if Hom(G,H) is connected when given just H and G. In particular, when H is a circular clique on integers p and q, then this is called the (p,q)-mixing problem. I'll show that when 2< p/q < 4,  G is (p,q)-mixing if and only if for every (p,q)-colouring f, and every cycle C, the winding number of C under f is 0. When H is an odd cycle, this simplifies to G is (2k+1,k)-mixing if and only if G does not fold to C_6, where a fold is a restricted graph homomorphism. If time persists, I'll sketch a polynomial time algorithm for this problem when G is planar. 

Location 
MC - Mathematics & Computer Building

200 University Avenue West

Waterloo, ON N2L 3G1
Canada

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