##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Sergey Kitaev

#### Reykjavik University

## Representable graphs

##### Abstract:

A graph $G=(V,E)$ is representable if there exists a word $W$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $W$ if and only if $(x,y) \in E$ for each $x \neq y$. If $W$ is $k$-uniform (each letter of $W$ occurs exactly $k$ times in it) then $G$ is called $k$-representable. The notion of representable graphs appears in study, by Seif and later by Kitaev and Seif, of the Perkins semigroup which has played central role in semigroup theory since 1960. Thus, the objects in question being on border between combinatorics on words and graph theory, come from needs in algebra. In my talk, I will discuss some properties of representable graphs. In particular, I will give examples of non-representable graphs and will discuss certain wide classes of graphs that are 2- and 3-representable. I will conclude with a number of open problems in this direction of research. This is a joint work with Artem Pyatkin.

Host: Jeff Remmel

### November 14, 2006

### 3:00 PM

### AP&M 7321

****************************