Unique Vector Colorings: Core Concepts
|Affiliation:||Nanyang Technological University|
|Room:||Mathematics and Computer Building (MC) 6486|
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.
200 University Avenue West
Waterloo, ON N2L 3G1