摘要：

A graph is word-representable if its adjacency structure can be encoded by alternation of letters in a word. This simple combinatorial definition leads to a rich and surprisingly deep theory connecting graph theory, combinatorics on words, and graph orientations. In this talk, we focus on the representation number of a graph - the smallest k such that the graph can be represented by a k-uniform word (that is, a word in which each letter appears exactly k times). This parameter provides a quantitative measure of how complex a word representation must be and raises natural structural and extremal questions.

We survey known results on representation numbers for important graph classes, including trees, cycles, circle graphs, prisms, crown graphs, and hypercubes. While some families admit small representation numbers (e.g., circle graphs are exactly the 2-representable graphs), others require significantly larger values. We discuss extremal constructions, recent advances on the representation number of the n-cube, and several intriguing open problems, including the possible gap between known upper and lower bounds for graphs with large representation numbers.

简介：

Kitaev 教授的研究兴趣涉及组合数学和图论及其应用的各个方面，已在《Journal of Combinatorial Theory, Series A》等期刊发表140 余篇论文，并著有专著《Patterns in Permutations and Words》、《Words and Graphs》。现任《Journal of Combinatorial Theory, Series A》和《Proceedings of the Edinburgh Mathematical Society》 编委。