ICE-TCS Lecture Series - Magnús Mar Halldórsson - Graphs made from words

Abstract:

This talk will celebrate the first collaborative work between different subgroups of ICE-TCS. Sergey Kitaev and his colleagues have studied graphs formed from the interleaving of letters in a word. More precisely, given a word over some alphabet, we can form a graph with the letters of the alphabet as vertices, with two vertices adjacent if those letters occur alternatingly in the word. Their motivation for studying this class comes from algebra, but other applications include robot scheduling.

When faced with a new class of graphs, several immediate questions pop up:

• Which graphs belong (and which ones do not) in the class,
• How large do the words need to be to represent all such graphs, and
• Can we come up with alternative representations, that in particular make it easier to answer structural and algorithmic questions about these graphs?

We will discuss recent answers to these questions.

This is joint work with Artem Pyatkin (Sobolev Institute of Mathematics) and Sergey Kitaev (Reykjavik University).