{
  "id": "1602.03109",
  "version": "v1",
  "published": "2016-02-09T18:15:30.000Z",
  "updated": "2016-02-09T18:15:30.000Z",
  "title": "Number of fixed points and disjoint cycles in monotone Boolean networks",
  "authors": [
    "Julio Aracena",
    "Adrien Richard",
    "Lilian Salinas"
  ],
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.IT",
    "math.IT",
    "q-bio.MN"
  ],
  "abstract": "Given a digraph $G$, a lot of attention has been deserved on the maximum number $\\phi(G)$ of fixed points in a Boolean network $f:\\{0,1\\}^n\\to\\{0,1\\}^n$ with $G$ as interaction graph. In particular, a central problem in network coding consists in studying the optimality of the classical upper bound $\\phi(G)\\leq 2^{\\tau}$, where $\\tau$ is the minimum size of a feedback vertex set of $G$. In this paper, we study the maximum number $\\phi_m(G)$ of fixed points in a {\\em monotone} Boolean network with interaction graph $G$. We establish new upper and lower bounds on $\\phi_m(G)$ that depends on the cycle structure of $G$. In addition to $\\tau$, the involved parameters are the maximum number $\\nu$ of vertex-disjoint cycles, and the maximum number $\\nu^{*}$ of vertex-disjoint cycles verifying some additional technical conditions. We improve the classical upper bound $2^\\tau$ by proving that $\\phi_m(G)$ is at most the largest sub-lattice of $\\{0,1\\}^\\tau$ without chain of size $\\nu+1$, and without another forbidden-pattern of size $2\\nu^{*}$. Then, we prove two optimal lower bounds: $\\phi_m(G)\\geq \\nu+1$ and $\\phi_m(G)\\geq 2^{\\nu^{*}}$. As a consequence, we get the following characterization: $\\phi_m(G)=2^\\tau$ if and only if $\\nu^{*}=\\tau$. As another consequence, we get that if $c$ is the maximum length of a chordless cycle of $G$ then $2^{\\nu/3^c}\\leq\\phi_m(G)\\leq 2^{c\\nu}$. Finally, with the technics introduced, we establish an upper bound on the number of fixed points of any Boolean network according to its signed interaction graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-02-09T18:15:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "fixed points",
      "monotone boolean networks",
      "maximum number",
      "interaction graph",
      "classical upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160203109A"
    }
  }
}