Geodesic
On the stability and instability of finite dynamical systems with prescribed interaction graphs
Maximilien Gadouleau1
1Durham University
The electronic journal of combinatorics, Tome 26 (2019) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The dynamical properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding, and in the context of hat games, such as the guessing game and Winkler's hat game. The instability of an FDS is the minimum Hamming distance between a state and its image under the FDS, while the stability is the minimum of the reciprocal of the Hamming distance; they are both directly related to Winkler's hat game. In this paper, we study the value of the (in)stability of FDSs with prescribed interaction graphs. The first main contribution of this paper is the study of the maximum stability for interaction graphs with a loop on each vertex. We determine the maximum (in)stability for large enough alphabets and also prove some lower bounds for the Boolean alphabet. We also compare the maximum stability for arbitrary functions compared to monotone functions only. The second main contribution of the paper is the study of the average (in)stability of FDSs with a given interaction graph. We show that the average stability tends to zero with high alphabets, and we then investigate the average instability. In that study, we give bounds on the number of FDSs with positive instability (i.e fixed point free functions). We then conjecture that all non-acyclic graphs will have an average instability which does not tend to zero when the alphabet is large. We prove this conjecture for some classes of graphs, including cycles.
DOI : 10.37236/7296
Classification : 05C82, 05C20, 05C57, 68M10, 68P30, 91A43, 91A12
Mots-clés : Winkler's hat game, Boolean alphabet

Maximilien Gadouleau  1

1 Durham University 
@article{10_37236_7296,
     author = {Maximilien Gadouleau},
     title = {On the stability and instability of finite dynamical systems with prescribed interaction graphs},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {3},
     doi = {10.37236/7296},
     zbl = {1418.05115},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7296/}
}
TY  - JOUR
AU  - Maximilien Gadouleau
TI  - On the stability and instability of finite dynamical systems with prescribed interaction graphs
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7296/
DO  - 10.37236/7296
ID  - 10_37236_7296
ER  - 
%0 Journal Article
%A Maximilien Gadouleau
%T On the stability and instability of finite dynamical systems with prescribed interaction graphs
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/7296/
%R 10.37236/7296
%F 10_37236_7296
Maximilien Gadouleau. On the stability and instability of finite dynamical systems with prescribed interaction graphs. The electronic journal of combinatorics, Tome 26 (2019) no. 3. doi: 10.37236/7296

Cité par Sources :