NDLI: Finite Dynamical Systems, Hat Games, and Coding Theory

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Gadouleau, Maximilien
Copyright Year	2018
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.
Sponsorship	Engineering and Physical Sciences Research Council
Starting Page	1922
Ending Page	1945
Page Count	24
File Format	PDF
ISSN	08954801
DOI	10.1137/15M1044758
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	32
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2018-08-01
Access Restriction	Subscribed
Subject Keyword	network coding index coding Linear codes, general hat games Directed graphs (digraphs), tournaments Cooperative games finite dynamical systems stability guessing number
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Hat Guessing Games

Hat Guessing Games

Fixed Points of Boolean Networks, Guessing Graphs, and Coding Theory

New Constructions and Bounds for Winkler's Hat Game

Counting dynamical systems over finite fields

Counting distinct functional graphs from linear finite dynamical systems

A construction for the hat problem on a directed graph

On the Number of Distinct Functional Graphs of Affine-Linear Transformations over Finite Fields

Surjective Extensions of Sliding-Block Codes

Finite Dynamical Systems, Hat Games, and Coding Theory

Similar Documents

Hat Guessing Games

Hat Guessing Games

Fixed Points of Boolean Networks, Guessing Graphs, and Coding Theory

New Constructions and Bounds for Winkler's Hat Game

Counting dynamical systems over finite fields

Counting distinct functional graphs from linear finite dynamical systems

A construction for the hat problem on a directed graph

On the Number of Distinct Functional Graphs of Affine-Linear Transformations over Finite Fields

Surjective Extensions of Sliding-Block Codes

Finite Dynamical Systems, Hat Games, and Coding Theory