THIS SITE

Information for

Tutte Colloquium - Krystal GuoExport this event to calendar

Friday, April 20, 2018 — 3:30 PM EDT

Title: Transversals in covers of graphs

Speaker: Krystal Guo
Affiliation: Université Libre de Bruxelles
Room: MC 5501

Abstract:

We study a polynomial with connections to correspondence colouring (also known as DP-colouring) and the Unique Games Conjecture. Given a graph G and an assignment of elements of the symmetric group Sr to the edge of G, we define a cover graph: there are sets of r vertices corresponding each vertex of G, called fibres, and for each edge uv, we add a perfect matching between the fibres corresponding to u and v. A transversal subgraph of the cover is an induced subgraph which has exactly one vertex in each fibre. In this setting, we can associate correspondence colourings with transversal cocliques and unique label covers with transversal copies of G.

We define a polynomial which enumerates the transversal subgraphs of G with k edges. We show that this polynomial satisfies a contraction deletion formula and use this to study the evaluation of this polynomial at -r-1. This is joint work with Chris Godsil and Gordon Royle. 

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West
Waterloo, ON N2L 3G1
Canada

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