Word-Representable Graphs: Orientations, Posets, and Bounds

Word-representable graphs were originally introduced by Kitaev and Pyatkin, motivated by work of Kitaev and Seif in algebra. Since their introduction, however, there has been a great deal of work in understanding their graph theoretical properties. In this paper, we introduce tools from partially ordered sets, Ramsey theory as well as probabilistic methods to study them. Through these, we settle a number of open problems in the field, regarding both the existence and length of word-representations for various classes of graphs.