Simple dynamics on graphs

DOI10.1016/J.TCS.2016.03.013MaRDI QIDQ266275zbMATH OpenOpenAlexFDO

Authors Maximilien Gadouleau, Adrien Richard

Publication date 13 April 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04688

Boolean network discrete dynamical system fixed point interaction graph

Applications of graph theory (05C90) Dynamical systems involving maps of trees and graphs (37E25) Combinatorics in computer science (68R05)

Abstract: Does the interaction graph of a finite dynamical system can force this system to have a "complex" dynamics ? In other words, given a finite interval of integers

A

, which are the signed digraphs

G

such that every finite dynamical system

f : A^{n} o A^{n}

with

G

as interaction graph has a "complex" dynamics ? If

| A | g e q 3

we prove that no such signed digraph exists. More precisely, we prove that for every signed digraph

G

there exists a system

f : A^{n} o A^{n}

with

G

as interaction graph that converges toward a unique fixed point in at most

l f l o o r l o g_{2} n f l o o r + 2

steps. The boolean case

| A | = 2

is more difficult, and we provide partial answers instead. We exhibit large classes of unsigned digraphs which admit boolean dynamical systems which converge toward a unique fixed point in polynomial, linear or constant time.

Review text

Let \(f\) be a \textit{finite dynamical system}, that is, a function \(f:A^n\rightarrow A^n\), \(x=(x_1,\ldots,x_n) \mapsto f(x)=(f_1(x),\ldots,f_n(x))\), where \(A=\{0,\ldots,s-1\}\). Such a finite dynamical system is more succinctly called a \textit{function over \(A\)}. Its \textit{interaction digraph} has vertex set \(\{1,\ldots,n\}\) and an arc from \(j\) to \(i\) if \(f_i\) depends on \(x_j\). The arc may be labelled indicating whether \(f_i(x)\) is an increasing function of \(x_j\), decreasing function of \(x_j\) or neither. In this case we say that the interaction graph is \textit{signed}. If \(f\) has (signed or unsigned) interaction digraph \(D\), then \(D\) is said to admit \(f\). In applications, one may possess considerable information about the interaction digraph, but know little about \(f\). This paper considers what one may deduce about \(f\) given its (signed or unsigned) interaction digraph, in particular, given a (signed or unsigned) digraph \(D\) and the value of \(s\), does \(D\) admit a function \(f\) over \(A\) such that \(f^k\) is constant? Such a function is called \textit{nilpotent} and the smallest value of \(k\) is called the \textit{class} of \(f\).NEWLINENEWLINEThe authors show that if \(s\geq 4\), then every signed digraph \(D\), admits a function over \(A\) of class at most 2 and a similar result holds when \(s=3\), except that now the class may be as large as \(\lfloor \log n \rfloor +2\). The Boolean case, that is when \(s=2\), is more complicated. Indeed, there are signed digraphs that do not admit a function over \(\{0,1\}\). To simplify matters, the authors consider only unsigned digraphs and give two different sufficient conditions for a strong digraph to admit a nilpotent Boolean function, one case leading to a constant upper bound on the class and the other not. In the special case where \(D\) is symmetric, that is the arc \((i,j)\) is present if and only if the arc \((j,i)\) is present, the authors show that \(D\) admits a Boolean nilpotent function of class 3, providing \(D\) is connected and not \(K_2\).

Recommendations

Cites work

Cited in

(18)

This page was built for publication: Simple dynamics on graphs

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