2017/09/07 by Maximilien Gadouleau, Gadouleau, Maximilien
Biochemistry, Genetics and Molecular Biology · #Combinatorics (math.CO) #FOS: Mathematics #Gene Regulatory Network Analysis #Peroxisome Proliferator-Activated Receptors
paper · pdf · doi:10.48550/arxiv.1709.02171
openalex publication_date 2017/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The dynamical properties of finite dynamical systems (FDSs) have been\ninvestigated in the context of coding theoretic problems, such as network\ncoding, and in the context of hat games, such as the guessing game and\nWinkler's hat game. The instability of an FDS is the minimum Hamming distance\nbetween a state and its image under the FDS, while the stability is the minimum\nof the reciprocal of the Hamming distance; they are both directly related to\nWinkler's hat game. In this paper, we study the value of the (in)stability of\nFDSs with prescribed interaction graphs. The first main contribution of this\npaper is the study of the maximum stability for interaction graphs with a loop\non each vertex. We determine the maximum (in)stability for large enough\nalphabets and also prove some lower bounds for the Boolean alphabet. We also\ncompare the maximum stability for arbitrary functions compared to monotone\nfunctions only. The second main contribution of the paper is the study of the\naverage (in)stability of FDSs with a given interaction graph. We show that the\naverage stability tends to zero with high alphabets, and we then investigate\nthe average instability. In that study, we give bounds on the number of FDSs\nwith positive instability (i.e fixed point free functions). We then conjecture\nthat all non-acyclic graphs will have an average instability which does not\ntend to zero when the alphabet is large. We prove this conjecture for some\nclasses of graphs, including cycles.\n