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:

Finite dynamical systems, hat games, and coding theory.

Gadouleau, Maximilien (2018) 'Finite dynamical systems, hat games, and coding theory.', SIAM journal on discrete mathematics., 32 (3). pp. 1922-1945.


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.

Item Type:Article
Full text:(VoR) Version of Record
Download PDF
Publisher Web site:
Publisher statement:© 2018, Society for Industrial and Applied Mathematics
Date accepted:31 May 2018
Date deposited:04 October 2018
Date of first online publication:01 August 2018
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar