Finite Dynamical Systems, Hat Games, and Coding Theory

Abstract

The properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding and index coding, and in the context of hat games, such as the guessing game and Winkler's hat game. In this paper, we relate the problems mentioned above to properties of FDSs, including the number of fixed points, their stability, and their instability. We first introduce the guessing dimension and the coset dimension of an FDS and their counterparts for directed graphs. Based on the coset dimension, we then refine the existing equivalences between network coding and index coding. We also introduce the concept of the instability of FDSs and we study the stability and the instability of directed graphs. We prove that the instability always reaches the size of a minimum feedback vertex set for large enough alphabets. We also obtain some nonstable bounds independent of the number of vertices of the graph. We then relate the stability and the instability to the guessing number. We also exhibit a class of sparse graphs with large girth that have high stability and high instability; our approach is code-theoretic and uses the guessing dimension. Finally, we prove that the affine instability is always asymptotically greater than or equal to the linear guessing number.