Fixed points of Boolean networks, guessing graphs, and coding theory

DOI10.1137/140988358MaRDI QIDQ3455244zbMATH OpenOpenAlexFDO

Authors Maximilien Gadouleau, Adrien Richard, Søren Riis

Publication date 4 December 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.6144, http://qmro.qmul.ac.uk/xmlui/handle/123456789/25117

zbMATH Keywords

Boolean networkserror-correcting codesfixed pointsguessing numbersigned digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22) Symbolic dynamics (37B10) Dynamical systems involving maps of trees and graphs (37E25) Combinatorics in computer science (68R05)

Abstract: In this paper, we are interested in the number of fixed points of functions $f:A^{n}o{A}^n$ over a finite alphabet $A$ defined on a given signed digraph $D$. We first use techniques from network coding to derive some lower bounds on the number of fixed points that only depends on $D$. We then discover relationships between the number of fixed points of $f$ and problems in coding theory, especially the design of codes for the asymmetric channel. Using these relationships, we derive upper and lower bounds on the number of fixed points, which significantly improve those given in the literature. We also unveil some interesting behaviour of the number of fixed points of functions with a given signed digraph when the alphabet varies. We finally prove that signed digraphs with more (disjoint) positive cycles actually do not necessarily have functions with more fixed points.

Recommendations

• Number of fixed points and disjoint cycles in monotone Boolean networks
• Fixed points and connections between positive and negative cycles in Boolean networks
• Complexity of fixed point counting problems in Boolean networks
• Fixed points and maximal independent sets in AND-OR networks
• Fixed points of Boolean networks with small number of elementary circuits

Cites work

• A combinatorial analogue of the Jacobian problem in automata networks
• A logical calculus of the ideas immanent in nervous activity
• A new table of constant weight codes
• An Equivalence Between Network Coding and Index Coding
• An introduction to sequential dynamical systems
• Closure Solvability for Network Coding and Secret Sharing
• Dynamics of positive automata networks
• ETS IV: Sequential dynamical systems: fixed points, invertibility and equivalence
• Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks
• Fixed points and maximal independent sets in AND-OR networks
• Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
• Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework
• scientific article; zbMATH DE number 4042465 (Why is no real title available?)
• scientific article; zbMATH DE number 3771418 (Why is no real title available?)
• scientific article; zbMATH DE number 45557 (Why is no real title available?)
• scientific article; zbMATH DE number 50840 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3228263 (Why is no real title available?)
• scientific article; zbMATH DE number 3410920 (Why is no real title available?)
• scientific article; zbMATH DE number 3065933 (Why is no real title available?)
• Index Coding With Side Information
• Information flows, graphs and their guessing numbers
• Iterative behaviour of generalized majority functions
• Lower bounds for constant weight codes
• Maximum number of fixed points in AND-OR-NOT networks
• Maximum number of fixed points in regulatory Boolean networks
• Modeling and analysis of gene regulatory networks
• Multistationarity, the basis of cell differentiation and memory. II: Logical analysis of regulatory networks in terms of feedback circuits
• Necessary conditions for multistationarity in discrete dynamical systems
• Network information flow
• Neural networks and physical systems with emergent collective computational abilities
• On periodical behaviour in societies with symmetric influences
• On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory
• Positive circuits and maximal number of fixed points in discrete dynamical systems
• Probability Inequalities for Sums of Bounded Random Variables
• Problems in Network Coding and Error Correcting Codes Appended by a Draft Version of S. Riis “Utilising Public Information in Network Coding”
• The generalized Gilbert-Varshamov bound is implied by Turan's theorem [code construction]
• Upper bounds for constant-weight codes

Cited in

(16)

• Positive and negative cycles in Boolean networks
• On the flora of asynchronous locally non-monotonic Boolean automata networks
• Fixed points and connections between positive and negative cycles in Boolean networks
• On the rank and periodic rank of finite dynamical systems
• Fixed points and maximal independent sets in AND-OR networks
• Complexity of fixed point counting problems in Boolean networks
• Fixed points in conjunctive networks and maximal independent sets in graph contractions
• Maximum number of fixed points in AND-OR-NOT networks
• Simple dynamics on graphs
• Asynchronous simulation of Boolean networks by monotone Boolean networks
• Finite dynamical systems, hat games, and coding theory
• Number of fixed points and disjoint cycles in monotone Boolean networks
• On the influence of the interaction graph on a finite dynamical system
• The maximal coordination principle in regulatory Boolean networks
• k-independent Boolean networks
• Creation of fixed points in block-parallel Boolean automata networks

This page was built for publication: Fixed points of Boolean networks, guessing graphs, and coding theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3455244)