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.
|Full text:||(VoR) Version of Record|
Download PDF (432Kb)
|Publisher Web site:||https://doi.org/10.1137/15M1044758|
|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|