go-v.orgdoi

Finite Factors of Bernoulli Schemes and Distinguishing Labelings of Directed Graphs

Andrew Lazowski, Stephen M. Shea · The Electronic Journal of Combinatorics · 2012

  • DOI 10.37236/6
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2012

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2012

Abstract

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.

Open the resolved locator · 10.37236/6

Metadata licence: OpenAlex metadata (CC0)