Dr Maximilien Gadouleau m.r.gadouleau@durham.ac.uk
Associate Professor
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.
Gadouleau, M. (2019). On the stability and instability of finite dynamical systems with prescribed interaction graphs. Electronic Journal of Combinatorics, 26(3), Article P3.32
Journal Article Type | Article |
---|---|
Acceptance Date | Jul 25, 2019 |
Online Publication Date | Aug 16, 2019 |
Publication Date | Aug 16, 2019 |
Deposit Date | Aug 29, 2019 |
Publicly Available Date | Aug 29, 2019 |
Journal | Electronic Journal of Combinatorics |
Electronic ISSN | 1077-8926 |
Publisher | Electronic Journal of Combinatorics |
Peer Reviewed | Peer Reviewed |
Volume | 26 |
Issue | 3 |
Article Number | P3.32 |
Public URL | https://durham-repository.worktribe.com/output/1294340 |
Publisher URL | https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i3p32 |
Published Journal Article
(349 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nd/4.0/
Copyright Statement
© The author. Released under the CC BY-ND license (International 4.0).
Factorisation in the semiring of finite dynamical systems
(2024)
Journal Article
Graphs with minimum fractional domatic number
(2023)
Journal Article
Bent functions in the partial spread class generated by linear recurring sequences
(2022)
Journal Article
Expansive automata networks
(2020)
Journal Article
Elementary, finite and linear vN-regular cellular automata
(2020)
Journal Article
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search