A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks
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-d...
| Autor principal: | |
|---|---|
| Formato: | Artigo |
| Idioma: | English |
| Publicado em: |
Discrete Mathematics & Theoretical Computer Science
2011-01-01
|
| coleção: | Discrete Mathematics & Theoretical Computer Science |
| Assuntos: | |
| Acesso em linha: | https://dmtcs.episciences.org/2978/pdf |
| _version_ | 1827323992186290176 |
|---|---|
| author | Adrien Richard |
| author_facet | Adrien Richard |
| author_sort | Adrien Richard |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:02:44Z |
| format | Article |
| id | doaj.art-3c36c06046084a649bbc4ff4621289e1 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:02:44Z |
| publishDate | 2011-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-3c36c06046084a649bbc4ff4621289e12024-03-07T14:50:09ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502011-01-01DMTCS Proceedings vol. AP,...Proceedings10.46298/dmtcs.29782978A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworksAdrien Richard0Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe BIOINFOWe 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.https://dmtcs.episciences.org/2978/pdffeedback circuitboolean networkfixed pointself-dual boolean functiondiscrete 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] |
| spellingShingle | Adrien Richard A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks Discrete Mathematics & Theoretical Computer Science 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] |
| title | A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks |
| title_full | A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks |
| title_fullStr | A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks |
| title_full_unstemmed | A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks |
| title_short | A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks |
| title_sort | fixed point theorem for boolean networks expressed in terms of forbidden subnetworks |
| topic | 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] |
| url | https://dmtcs.episciences.org/2978/pdf |
| work_keys_str_mv | AT adrienrichard afixedpointtheoremforbooleannetworksexpressedintermsofforbiddensubnetworks AT adrienrichard fixedpointtheoremforbooleannetworksexpressedintermsofforbiddensubnetworks |