l Bi-resolving graph homomorphisms and application to symbolic dynamics
Speaker
l Jung Uijin (KAIST)
Date
l 2009-08-21
Link
l
DownLoad
l
Etc
l 2009 Combinatorics Workshop
The theory of resolving graph homomorphisms intertwines graph theory and symbolic dynamics.
We show that given two graphs G and H, there is a bi-resolving (resp. bi-covering) graph
homomorphism from G to H if and only if there is a subamalgamation matrix S such that AGS ≤
SAH and STAG ≤ AHST (resp. AGS = SAH and STAG = AHST), where AG and AH are the
adjacency matrices of G and H, respectively. We investigate the bi-covering extensions of bi-
resolving homomorphisms and give several sufficient conditions for a bi-resolving
homomorphism to have a bi-covering extension with an irreducible domain. Using these
results, we present the extension property in symbolic dynamics.