Geodesic
Finite factors of Bernoulli schemes and distinguishing labelings of directed graphs
The electronic journal of combinatorics, Tome 19 (2012) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/6
Classification : 05C78, 05C20, 60G10, 11B73
Mots-clés : Bell numbers, Bernoulli scheme, directed graph, distinguishing number, finitarily Markovian, Markov, variable-length Markov 
@article{10_37236_6,
     author = {Andrew Lazowski and Stephen M. Shea},
     title = {Finite factors of {Bernoulli} schemes and distinguishing labelings of directed graphs},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {1},
     doi = {10.37236/6},
     zbl = {1243.05212},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/6/}
}
TY  - JOUR
AU  - Andrew Lazowski
AU  - Stephen M. Shea
TI  - Finite factors of Bernoulli schemes and distinguishing labelings of directed graphs
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/6/
DO  - 10.37236/6
ID  - 10_37236_6
ER  - 
%0 Journal Article
%A Andrew Lazowski
%A Stephen M. Shea
%T Finite factors of Bernoulli schemes and distinguishing labelings of directed graphs
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/6/
%R 10.37236/6
%F 10_37236_6
Andrew Lazowski; Stephen M. Shea. Finite factors of Bernoulli schemes and distinguishing labelings of directed graphs. The electronic journal of combinatorics, Tome 19 (2012) no. 1. doi: 10.37236/6

Cité par Sources :