Limits of Rauzy Graphs of Low-Complexity Words

Abstract

We consider Benjamini-Schramm limits of Rauzy Graphs of low-complexity words. Low-complexity words are infinite words (over a finite alphabet), for which the number of subwords of length n is bounded by some Kn --- examples of such a word include the Thue-Morse word 01101001... and the Fibonacci word. Rauzy graphs Rn (omega) have the length n subwords of omega as vertices, and the oriented edges between vertices indicate that two words appear immediately adjacent to each other in omega (with overlap); the edges are also equipped with labels, which indicate what "new letter" was appended to the end of the terminal vertex of an edge. In a natural way, the labels of consecutive edges in a Rauzy graph encode subwords of omega. The Benjamini-Schramm limit of a sequence of graphs is a distribution on (possibly infinite) rooted graphs governed by the convergence in distribution of random neighborhoods of the sequence of finite graphs.

In the case of Rauzy graphs without edge-labelings, we establish that the Rauzy graphs of aperiodic low-complexity words converge to the line graph in the Benjamini-Schramm sense. In the same case, but for edge-labelled Rauzy graphs, we also prove that that the limit exists when the frequencies of all subwords in the infinite word, omega, are well defined (when the subshift of omega is uniquely ergodic), and we show that the limit can be identified with the unique ergodic measure associated to the subshift generated by the word. The eventually periodic (i.e. finite) cases are also shown. Finally, we show that for non-uniquely ergodic systems, the Benjamini-Schramm limit need not exist ---though it can in some instances--- and we provide examples to demonstrate the variety of possible behaviors.