<i>k</i> -11-representations of graphs, revisited

Abstract In this paper, we study the existence of $k$ - $11$ -representations of graphs. Inspired by work on permutation patterns, these representations are ways of representing graphs by words where adjacencies between vertices are captured by patterns in the corresponding letters. Our main result is that all graphs are $1$ - $11$ -representable, answering a question originally raised by Cheon et al. in 2018 and repeated in several follow-up papers – including a very recent paper, where it was shown that all graphs on at most $8$ vertices are $1$ - $11$ -representable. Moreover, we prove that all graphs are permutationally $1$ - $11$ -representable – that is representable as the concatenation of permutations of the vertices – answering the existence question in extremely strong fashion. Our construction leads to nearly optimal bounds on the length of the words, as well. It can, moreover, be adapted to represent all acyclic orientations of graphs; this generalizes the fact that word-representations capture semi-transitive orientations of graphs. Our construction also adapts easily to other $k \geq 2$ as well, giving representations using a linear number of permutations when the best known previous bounds used a quadratic number. Finally, we also consider the (non-)existence of ‘even–odd’-representations of graphs. This answers a question raised by Wanless after a conference talk in 2018.