We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On the stability and instability of finite dynamical systems with prescribed interaction graphs.

Gadouleau, M. (2019) 'On the stability and instability of finite dynamical systems with prescribed interaction graphs.', The electronic journal of combinatorics., 26 (3).


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.

Item Type:Article
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© The author. Released under the CC BY-ND license (International 4.0).
Date accepted:25 July 2019
Date deposited:29 August 2019
Date of first online publication:16 August 2019
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar