![](https://d3ilqtpdwi981i.cloudfront.net/x81tvXbN9YcWU3XjQLFE8xEl8k8=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/4d/1e/bf/4d1ebf8e-705c-47d0-a459-469292a7a111/thumbnail_f17992a3-0258-4740-95e4-ec3eb5006ad5.jpg)
A labeling of a graph is a function from the vertices of the graph to some finite set. In 1996, Albertson and Collins 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.
Available at: http://works.bepress.com/andrew_lazowski/1/
Originally published:
Lazowski, Andrew and Stephen M. Shea. "Finite Factors of Bernoulli Schemes and Distinguishing Labelings of Directed Graphs." The Electronic Journal of Combinatorics, 19 (2012), P1.