{"docId":2978,"paperId":2978,"url":"https:\/\/dmtcs.episciences.org\/2978","doi":"10.46298\/dmtcs.2978","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":261,"name":"DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems"}],"section":[{"sid":66,"title":"Proceedings","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-01196145","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-01196145v1","dateSubmitted":"2017-01-31 10:21:35","dateAccepted":null,"datePublished":"2011-01-01 00:00:00","titles":{"en":"A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks"},"authors":["Richard, Adrien"],"abstracts":{"en":"We are interested in fixed points in Boolean networks, $\\textit{i.e.}$ functions $f$ from $\\{0,1\\}^n$ to itself. We define the subnetworks of $f$ as the restrictions of $f$ to the hypercubes contained in $\\{0,1\\}^n$, and we exhibit a class $\\mathcal{F}$ of Boolean networks, called even or odd self-dual networks, satisfying the following property: if a network $f$ has no subnetwork in $\\mathcal{F}$, then it has a unique fixed point. We then discuss this \"forbidden subnetworks theorem''. We show that it generalizes the following fixed point theorem of Shih and Dong: if, for every $x$ in $\\{0,1\\}^n$, there is no directed cycle in the directed graph whose the adjacency matrix is the discrete Jacobian matrix of $f$ evaluated at point $x$, then $f$ has a unique fixed point. We also show that $\\mathcal{F}$ contains the class $\\mathcal{F'}$ of networks whose the interaction graph is a directed cycle, but that the absence of subnetwork in $\\mathcal{F'}$ does not imply the existence and the uniqueness of a fixed point."},"keywords":[["feedback circuit"],["Boolean network"],["fixed point"],["self-dual Boolean function"],["discrete Jacobian matrix"],"[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]","[MATH.MATH-DS] Mathematics [math]\/Dynamical Systems [math.DS]","[NLIN.NLIN-CG] Nonlinear Sciences [physics]\/Cellular Automata and Lattice Gases [nlin.CG]","[MATH.MATH-CO] Mathematics [math]\/Combinatorics [math.CO]"]}