Graph theory seminar - David RobersonExport this event to calendar

Thursday, June 12, 2014 — 1:00 PM EDT

Unique Vector Colorings: Core Concepts

Speaker: David Roberson
Affiliation: Nanyang Technological University
Room: Mathematics and Computer Building (MC) 6486

Abstract: 

A vector $k$-coloring of a graph G is an assignment of real unit vectors to the vertices of $G$ such that vectors assigned to adjacent vertices have inner product at most $-1/(k-1)$. The smallest $k$ for which a vector k-coloring exists is known as the vector chromatic number of $G$. We say that a graph is uniquely vector colorable if all of its optimal vector colorings are the same up to orthogonal transformations.

In this talk we will show that all non-bipartite Kneser graphs have unique vector colorings. Interestingly, the vectors used in the coloring are the vertices of the eigenpolytope of the least eigenvalue of the Kneser graph. Our main tool in proving this result is a sufficient condition for uniqueness from the theory of tensegrity frameworks. We will discuss how this condition may be able to be applied to show uniqueness of vector colorings for a much more general class of graphs.

The above mentioned result on tensegrity frameworks can also be used to prove that, under certain conditions, if $G$ is uniquely vector colorable and $H$ has vector chromatic number strictly larger than $G$, then that the categorical product $G\times H$ is uniquely vector colorable.

Lastly, we will discuss how a graph $G$ having a unique vector coloring often implies that $G$ is a core (has no proper endomorphisms).

This is joint work with Robert Samal, Antonis Varvitsiotis, Chris Godsil, and Brendan Rooney.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
2
  1. 2021 (85)
    1. October (1)
    2. September (8)
    3. August (7)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. 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)