Finite factors of Bernoulli schemes and distinguishing labelings of directed graphs (Q426739)

Summary: A labeling of a graph is a function from the vertices of the graph to some finite set. In 1996, \textit{M. O. Albertson} and \textit{K. L. Collins} [ibid. 3, No. 1, Research paper R18, 17 p. (1996); printed version J. Comb. 3, No. 1, 259--275 (1996; Zbl 0851.05088)] defined distinguishing labelings of undirected graphs. Their definition easily extends to directed graphs. Let \(G\) be a directed graph associated to the \(k\)-block presentation of a Bernoulli scheme \(X\). We determine the automorphism group of \(G\), and thus the distinguishing labelings of \(G\). A labeling of \(G\) defines a finite factor of \(X\). We define demarcating labelings and prove that demarcating labelings define finitarily Markovian finite factors of \(X\). We use the Bell numbers to find a lower bound for the number of finitarily Markovian finite factors of a Bernoulli scheme. We show that demarcating labelings of \(G\) are distinguishing.