Counting Fixed Points and Pure 2-Cycles of Tree Cellular Automata

Abstract

Cellular automata are synchronous discrete dynamical systems used to describe complex dynamic behaviors. The dynamic is based on local interactions between the components, these are defined by a finite graph with an initial node coloring with two colors. In each step, all nodes change their current color synchronously to the least/most frequent color in their neighborhood and in case of a tie, keep their current color. After a finite number of rounds these systems either reach a fixed point or enter a 2-cycle. The problem of counting the number of fixed points for cellular automata is #P-complete. In this paper we consider cellular automata defined by a tree. We propose an algorithm with run-time $O(n\varDelta )$ to count the number of fixed points, here $\varDelta$ is the maximal degree of the tree. We also prove upper and lower bounds for the number of fixed points. Furthermore, we obtain corresponding results for pure cycles, i.e., instances where each node changes its color in every round. We provide examples demonstrating that the bounds are sharp.

1 Introduction

A widely used abstraction of classical distributed systems such as multi-agent systems are graph automata. They evolve over time according to some simple local behaviors of its components. They belong to the class of synchronous discrete-time dynamical systems. A common model is as follows: Let G be a graph, where each node is initially either black or white. In discrete-time rounds, all nodes simultaneously update their color based on a predefined local rule. Locality means that the color associated with a node in round t is determined by the colors of the neighboring nodes in round $t-1$. As a local rule we consider the minority and the majority rule that arises in various applications and as such have received wide attention in recent years, in particular within the context of information spreading. Such systems are also known as graph cellular automata. It is well-known [9, 19] that they always converge to configurations that correspond to cycles either of length 1 – a.k.a. fixed points – or of length 2, i.e., such systems eventually reach a stable configuration or toggle between two configurations.

One branch of research so far uses the assumption that the initial configuration is random. Questions of interest are on the expected stabilization time of this process [25] and the dominance problem [18].

In this paper we focus on counting problems related to cellular automata, in particular counting the number of fixed points and pure 2-cycles, i.e., instances where each node changes its color in every round. This research is motivated by applications of so-called Boolean networks (BN) [11], i.e., discrete-time dynamical systems, where each node (e.g., gene) takes either 0 (passive) or 1 (active) and the states of nodes change synchronously according to regulation rules given as Boolean functions. Since the problem of counting the fixed points of a BN is in general #P-complete [3, 8, 21], it is interesting to find graph classes, for which the number of fixed points can be efficiently determined. These counting problems have attracted a lot of research in recent years [4, 6, 13].

We consider tree cellular automata, i.e., the defining graphs are finite trees. The results are based on a characterization of fixed points and pure 2-cycles for tree cellular automata [22]. The authors of [22] describe algorithms to enumerate all fixed points and all pure cycles. Since the number of fixed points and pure 2-cycles can grow exponentially with the tree size, these algorithms are unsuitable to efficiently compute these numbers. We prove the following theorem.

Theorem 1

The number of fixed points and the number of pure 2-cycles of a tree with n nodes and maximal node degree $\varDelta$ can be computed in time $O(n\varDelta )$.

We also prove the following theorem with upper and lower bounds for the number of fixed points of a tree improving results of [22] (parameter r is explained in Sect. 4.3). In the following, the $i^{th}$ Fibonacci number is denoted by $\mathbb {F}_i$.

Theorem 2

A tree with n nodes, diameter D and maximal node degree $\varDelta$ has at least $\max \left( 2^{r/2+1}, 2\mathbb {F}_D\right)$ and at most $\min \left( 2^{n-\varDelta }, 2\mathbb {F}_{n-\lceil \varDelta /2\rceil }\right)$ fixed points.

For the number of pure cycles we prove the following result, which considerably improves the bound of [22].

Theorem 3

A tree with maximal degree $\varDelta$ has at most $\min \left( 2^{n-\varDelta }, 2\mathbb {F}_{\lfloor n/2\rfloor }\right)$ pure 2-cycles.

We provide examples demonstrating ranges where these bounds are sharp. All results hold for the minority and the majority rule. We also formulate several conjectures about counting problems and propose future research directions. A long version of the paper including all proofs and more results is available [23].

2 State of the Art

The analysis of fixed points of minority/majority rule cellular automata received limited attention so far. Královič determined the number of fixed points of a complete binary tree for the majority process [12]. For the majority rule he showed that this number asymptotically tends to $4n(2\alpha )^n$, where n is the number of nodes and $\alpha \approx 0.7685$. Agur et al. did the same for ring topologies [2], the number of fixed point is in the order of $\varPhi ^n$, where $\varPhi = (1 +\sqrt{5})/2$. In both cases the number of fixed points is an exponentially small fraction of all configurations.

A related concept are Boolean networks (BN). They have been extensively used as mathematical models of genetic regulatory networks. The number of fixed points of a BN is a key feature of its dynamical behavior. A gene is modeled by binary values, indicating two transcriptional states, active or inactive. Each network node operates by the same nonlinear majority rule, i.e., majority processes are a particular type of BN [24]. The number of fixed points is an important feature of the dynamical behavior of a BN [5]. It is a measure for the general memory storage capacity. A high number implies that a system can store a large amount of information, or, in biological terms, has a large phenotypic repertoire [1]. However, the problem of counting the fixed points of a BN is in general #P-complete [3]. There are only a few theoretical results to efficiently determine this set [10]. Aracena determined the maximum number of fixed points regulatory Boolean networks, a particular class of BN [5].

Recently, Nakar and Ron studied the dynamics of a class of synchronous one-dimensional cellular automata for the majority rule [16]. They proved that fixed points and 2-cycles have a particular spatially periodic structure and give a characterization of this structure. Concepts related to fixed points of the minority/majority process are global defensive 0-alliance or monopolies [14].

Most research on discrete-time dynamical systems on graphs is focused on bounding the stabilization time. Good overviews for the majority (resp. minority) process can be found in [25] (resp. [17]). Rouquier et al. studied the minority process in the asynchronous model, i.e., not all nodes update their color concurrently [20]. They showed that the stabilization time strongly depends on the topology and observe that the case of trees is non-trivial.

2.1 Notation

Let $T=(V,E)$ be a finite, undirected tree with $n=|V|$. The maximum degree of T is denoted by $\varDelta (T)$, the diameter by D(T). The parameter T is omitted in case no ambiguity arises. A star graph is a tree with $n-1$ leaves. A l -generalized star graph is obtained from a star graph by inserting $l-1$ nodes into each edge, i.e., $n=l\varDelta +1$. For $F\subseteq E$ and $v\in V$ denote by $deg_{F}(v)$ the number of edges in F incident to v. Note that $deg_{F}(v)\le deg(v)$. For $i \ge 2$ denote by $E^i(T)$ the set of edges of T, where each end node has degree at least i. For $v\in V$ denote the set of v’s neighbors by N(v). For $e=(v_1,v_2)\in E^2(T)$ let $T_i$ be the subtree of T consisting of e and the connected component of $T\setminus e$ that contains $v_i$. We call $T_i$ the constituents of T for e. $T_1$ and $T_2$ together have $n+2$ nodes. We denote the $i^{th}$ Fibonacci number by $\mathbb {F}_i$, i.e., $\mathbb {F}_0=0, \mathbb {F}_1=1$, and $\mathbb {F}_i=\mathbb {F}_{i-1}+\mathbb {F}_{i-2}$.

3 Synchronous Discrete-Time Dynamical Systems

Let $G=(V,E)$ be a finite, undirected graph. A coloring c assigns to each node of G a value in $\{0,1\}$ with no further constraints on c. Denote by $\mathcal {C}(G)$ the set of all colorings of G, i.e., $|\mathcal {C}(G)|=2^{|V|}$. A transition process $\mathcal {M}$ is a mapping $\mathcal {M}: \mathcal {C}(G) \longrightarrow \mathcal {C}(G)$. Given an initial coloring c, a transition process produces a sequence of colorings $c, \mathcal {M}(c), \mathcal {M}(\mathcal {M}(c)),\ldots$. We consider two transition processes: Minority and Majority and denote the corresponding mappings by $\mathcal {MIN}$ and $\mathcal {MAJ}$. They are local mappings in the sense that the new color of a node is based on the current colors of its neighbors. To determine $\mathcal {M}(c)$ the local mapping is executed in every round concurrently by all nodes. In the minority (resp. majority) process each node adopts the minority (resp. majority) color among all neighbors. In case of a tie the color remains unchanged (see Fig. 1). Formally, the minority process is defined for a node v as follows:

$$\mathcal {MIN}(c)(v) = {\left\{ \begin{array}{ll} c(v) &{} \text {if } |N^{c(v)}(v)| \le |N^{1-c(v)}(v)|\\ 1-c(v) &{} \text {if } |N^{c(v)}(v)| > |N^{1-c(v)}(v)| \end{array}\right. }$$

$N^i(v)$ denotes the set of v’s neighbors with color i ($i=0,1$). The definition of $\mathcal {MAJ}$ is similar, only the binary operators $\le$ and > are reversed. Some results hold for both the minority and the majority process. To simplify notation we use the symbol $\mathcal {{M}}$ as a placeholder for $\mathcal {{MIN}}$ and $\mathcal {{MAJ}}$.

Fig. 1.

For the coloring on the left $\mathcal {{MIN}}$ reaches after 5 rounds a fixed point. $\mathcal {{MAJ}}$ reaches for the same initial coloring after one round a monochromatic coloring.

Let $c\in \mathcal {C}(G)$. If $\mathcal {M}(c)=c$ then c is called a fixed point. It is called a 2-cycle if $\mathcal {M}(c)\not =c$ and $\mathcal {M}(\mathcal {M}(c))=c$. A 2-cycle is called pure if $\mathcal {M}(c)(v) \not =c(v)$ for each node v of G, see Fig. 2. Denote by $\mathcal {F}_{\mathcal {M}}(G)$ (resp. $\mathcal {P}_{\mathcal {M}}(G)$) the set of all $c\in \mathcal {C}(G)$ that constitute a fixed point (resp. a pure 2-cycle) for $\mathcal {M}$.

Fig. 2.

Examples for the $\mathcal {MIN}$ rule. The coloring of the first (resp. second) tree is a fixed point (resp. a pure 2-cycle). The right two colorings are a non-pure 2-cycle.

Let T be a tree. The following results are based on a characterization of $\mathcal {F}_{\mathcal {M}}(T)$ and $\mathcal {P}_{\mathcal {M}}(T)$ by means of subsets of E(T) [22]. Let $E_{fix}(T)$ be the set of all $\mathcal {F}$ -legal subsets of E(T), where $F\subseteq E(T)$ is $\mathcal {F}$ -legal if $2deg_{F}(v) \le deg(v)$ for each $v\in V$. Each $\mathcal {F}$-legal set is contained in $E^2(T)$, hence $|E_{fix}(T)|\le 2^{|E^2(T)|}$. Theorem 1 of [22] proves that $|\mathcal {F}_{\mathcal {M}}(T)| = 2|E_{fix}(T)|$, see Fig. 3. Let $E_{pure}(T)$ be the set of all $\mathcal {P}$-legal subsets of E(T), where $F\subseteq E(T)$ is $\mathcal {P}$-legal if $2deg_{F}(v) < deg(v)$ for each $v\in V$. Thus, $\mathcal {P}$-legal subsets are contained in $E^3(T)$ and therefore $|E_{pure}(T)|\le 2^{|E^3(T)|}$. Theorem 4 of [22] proves that $|\mathcal {P}_{\mathcal {M}}(T)| = 2|E_{pure}(T)|$. For the tree in Fig. 3 we have $E_{pure}(T)=\{\emptyset \}$, thus $|\mathcal {P}_{\mathcal {M}}(T)|=2$. The pure colorings are the two monochromatic colorings. Given these results it is unnecessary to treat $\mathcal {{MIN}}$ and $\mathcal {{MAJ}}$ separately. To determine the number of fixed points (resp. pure 2-cycles) it suffices to compute $|E_{fix}(T)|$ (resp. $|E_{pure}(T)|$).

Fig. 3.

A tree T with $E_{fix}(T)=\{\emptyset , \{(1,3)\}\}$ and the corresponding fixed points for $\mathcal {MIN}$, the other two can be obtained by inverting colors.

4 Fixed Points

In this section we propose an efficient algorithm to determine $|\mathcal {F}_{\mathcal {M}}(T)|$, we provide upper and lower bounds for $|\mathcal {F}_{\mathcal {M}}(T)|$ in terms of n, $\varDelta$, and D, and discuss the quality of these bounds. As stated above, it suffices to consider $E_{fix}(T)$ and there is no need to distinguish the minority and the majority model. The following lemma is crucial for our results. It allows to recursively compute $|E_{fix}(T)|$. For a node v define $E_{fix}(T,v)=\{F\in E_{fix}(T)\;|\;2(deg_{F}(v)+1)\le deg(v)\}$.

Lemma 1

Let T be a tree, $e=(v_1,v_2)\in E^2(T)$, and $T_i$ the constituents of T for e. Then $|E_{fix}(T)|= |E_{fix}(T_1,v_1)||E_{fix}(T_2,v_2)| + |E_{fix}(T_1)||E_{fix}(T_2)|$.

Proof

Let $A= \{F\in E_{fix}(T)\;|\;e \in F\}$ and $B= \{F\in E_{fix}(T)\;|\;e \not \in F\}$. Then $A \cap B=\emptyset$ and $A\cup B= E_{fix}(T)$, i.e., $|E_{fix}(T)|= |A|+|B|$. If $F\in A$ then $F\setminus e \cap T_i \in E_{fix}(T_i,v_i)$ since $T_1\cap T_2=\{e\}$. Hence, $|A| \le |E_{fix}(T_1,v_1)||E_{fix}(T_2,v_2)|$. If $F\in B$ then $F \cap T_i \in E_{fix}(T_i)$, i.e., $|B| \le |E_{fix}(T_1)||E_{fix}(T_2)|$. This yields,

$$|E_{fix}(T)|\le |E_{fix}(T_1,v_1)||E_{fix}(T_2,v_2)| + |E_{fix}(T_1)||E_{fix}(T_2)|.$$

If $F_i \in E_{fix}(T_i,v_i)$, then $F_1\cup F_2 \cup \{e\} \in A$. If $F_i \in E_{fix}(T_i)$, then $F_1\cup F_2\in B$. Hence, $|E_{fix}(T_1,v_1)||E_{fix}(T_2,v_2)| + |E_{fix}(T_1)||E_{fix}(T_2)|\le |E_{fix}(T)|$.   $\square$

If $deg_T(v_i)\equiv 0 (2)$, then $E_{fix}(T_i,v_i) = E_{fix}(T_i\!\setminus \!\{v_i\})$. This yields a corollary.

Corollary 1

Let $P_n$ be a path with n nodes, then $|E_{fix}(P_n)|= F_{n-1}$.

4.1 Computing $|\mathcal {F}_{\mathcal {M}}(T)|$

Algorithm 1 of [22] enumerates all elements of $E_{fix}(T)$ for a tree T. Since $|E_{fix}(T)|$ can grow exponentially with the size of T, it is unsuitable to efficiently determine $|E_{fix}(T)|$. In this section we propose an efficient novel algorithm to compute $|E_{fix}(T)|$ in time $O(n\varDelta )$ based on Lemma 1. The algorithm operates in several steps. Let us define the input for the algorithm. First, each node $v_i$ is annotated with $b_i=\lfloor deg(v_i)/2\rfloor$. Let $T_R$ be the tree obtained form T by removing all leaves of T; denote by t the number of nodes of $T_R$. Select a node of $T_R$ as a root and assign numbers $1,\ldots ,t$ to nodes in $T_R$ using a postorder depth-first search. Direct all edges towards higher numbers, i.e., the numbers of all predecessors of a node i are smaller than i, see Fig. 4 for an example. The annotated rooted tree $T_R$ is the input to Algorithm 1.

Fig. 4.

From left to right: Tree T, annotation of T, $T_R$, a postorder numbering of $T_R$.

Algorithm 1 recursively operates on two types of subtrees of $T_R$ which are defined next. For $k=1,\ldots ,t-1$ denote by $T_k$ the subtree of $T_R$ consisting of k’s parent together with all nodes connected to k’s parent by paths using only nodes with numbers at most k (see Fig. 5). Note that $T_R=T_{t-1}$. For $k=1,\ldots ,t$ denote by $S_k$ the subtree of $T_R$ consisting of all nodes from which node k can be reached. In particular $S_{t}=T_R$, and if k is a leaf then $S_{k}$ consist of node k only.

Fig. 5.

The subtrees $T_1,\ldots T_7$ of the tree from Fig. 4. Note that $S_4=T_3$ and $S_3=\{3\}$.

For a subtree S of $T_R$ with largest node s and $b\ge 0$ denote by w(S, b) the number of subsets F of E(S) with $deg_{F}(i)\le b_i$ for all nodes i of S (recall that $b_i$ is defined above) and $deg_{F}(s)\le b$. Let $w(S,-1)=0$. Clearly if $b\ge b_{s}$ then $w(S,b)=w(S,b_{s})$. If S consists of a single node s then s is a leaf and $E(S)=\emptyset$; therefore $w(S,b)=1$ for all $b\ge 0$. Note that $w(S,b_s-1) = |E_{fix}(S,s)|$. The following observation shows the relation between $|E_{fix}(T)|$ and $w(T_{k},b)$.

Lemma 2

$|E_{fix}(T)|=w(T_{t-1},b_t)$ for any tree T.

The next lemma shows how to recursively compute $w(T_k,b)$ using Lemma 1.

Lemma 3

Let i be an inner node of $T_R$, k a child of i, and $b\ge 0$. Let $\delta _{b,0}=0$ if $b=0$ and 1 otherwise. If k is the smallest child of i, then

$$\begin{aligned} w(T_k,b)=w(S_{k},b_k) + w(S_{k},b_k-1)\delta _{b,0}. \end{aligned}$$

Otherwise let $j\not =k$ be the largest child of i such that $j<k$. Then

$$\begin{aligned} w(T_k,b)=w(T_j,b)w(S_{k},b_k) + w(T_j,b-1)w(S_{k},b_k-1). \end{aligned}$$

Proof

The proof for both cases is by induction on k. Consider the first case. If k is a leaf then $w(S_{k},b)=1$ for all $b\ge 0$ and $w(S_{k},-1)=0$. This is the base case. Assume k is not a leaf. $T_k$ consists of node i, $S_{k}$ and the edge $e=(i,k)$. If $b=0$ then $\delta _{b,0}=0$ and $w(T_k,0)=w(S_{k},b_k)$ by definition. Let $b>0$, i.e., $\delta _{b,0}=1$. Let $f_i$ (resp. $f_o$) be the number of $F\subseteq E(T_k)$ with $deg_{F}(l)\le b_l$ for all nodes l of $T_k$, $deg_{F}(i)\le b$ and $e\in F$ (resp. $e\not \in F$). Let $F \subseteq E(T_k)$. If $e\in F$ let $\hat{F} = F\setminus e$. Then $\hat{F}\in E(S_{k})$, $deg_{\hat{F}}(l)\le b_l$ for all nodes $l\not = k$ in $S_{k}$ and $deg_{\hat{F}}(k)\le b_k-1$, hence $f_i\le w(S_{k},b_k-1)$. If $e\not \in F$ then $F\in E(S_{k})$ and $deg_{F}(l)\le b_l$ for all nodes l in $S_{k}$, hence $f_o\le w(S_{k},b_k)$. Thus, $w(T_k,b)\le w(S_{k},b_k) + w(S_{k},b_k-1)$. On the other hand, let $F\in E(S_{k})$ such that $deg_{F}(l)\le b_l$ for all nodes $l\not = k$ in $S_{k}$. If $deg_{F}(k)\le b_k-1$ then $F\cup \{e\}$ contributes to $w(T_k,b)$ and if $deg_{F}(k)\le b_k$ then F contributes to $w(T_k,b)$. Thus $w(T_k,b)\ge w(S_{k},b_k) + w(S_{k},b_k-1)$.

Consider the second statement. The case that k is a leaf follows immediately from Lemma 1. Assume that k is not a leaf. We apply Lemma 1 to $T_k$ and edge (i, k). Then $T_j \cup (i,k)$ and $S_{k}\cup (i,k)$ are the constituents of $T_k$. Note that $E_{fix}(S_{k} \cup (i,k),i) = w(S_{k},b_k-1)$ and $E_{fix}(T_{j} \cup (i,k),k) = w(T_{j},b-1)$.   $\square$

Algorithm 1 makes use of Lemma 2 and 3 to determine $w(T_{t-1},b_t)$, which is equal to $|E_{fix}(T)|$. Let $B=\max \{b_i\;|\;i=1,\ldots , t\}$, clearly $B\le \varDelta /2$. Algorithm 1 uses an array W of size $[0,t-1] \times [0,B]$ to store the values of $w(\cdot ,\cdot )$. The first index is used to identify the tree $T_k$. To simplify notation this index can also have the value 0. To store the values of $w(S_{k},b)$ in the same array we define for each inner node k an index l(k) as follows $l(k)=k-1$ if k is not a leaf and $l(k)=0$ otherwise. Then clearly $S_k=T_{l(k)}$ if k is not a leaf. More importantly, the value of $w(S_{k},b)$ is stored in W(l(k), b) for all k and b.

The algorithm computes the values of W for increasing values of $k< t$ beginning with $k=0$. If W(j, b) is known for all $j<k$ and all $b\in [0,B]$ we can compute W(k, b) for all values of b in [0, B] using Lemma 3. Finally we have $w(t-1,b_t)$ which is equal to $|E_{fix}(T)|$. Theorem 1 follows from Lemma 2 and 3.

4.2 Upper Bounds for $|\mathcal {F}_{\mathcal {M}}(T)|$

The definition of $E_{fix}(T)$ immediately leads to a first upper bound for $|\mathcal {F}_{\mathcal {M}}(T)|$.

Lemma 4

$|E_{fix}(T)| \le 2^{n-\varDelta -1}$.

Proof

Theorem 1 of [22] implies $|E_{fix}(T)| \le 2^{|E^2(T)|}$. Note that $|E^2(T)|=n-1-l$, where l is the number of leaves of T. It is well known that $l=2+\sum _{j=3}^\varDelta (j-2)D_j$, where $D_j$ denotes the number of nodes with degree j. Thus,

$$|E^2(T)| = n-3-\sum _{j=3}^\varDelta (j-2)D_j\le n-3 -(\varDelta -2) = n-\varDelta -1.$$

   $\square$

For $\varDelta < n -\lceil n/3\rceil$ the bound of Lemma 4 is not attained. Consider the case $n=8, \varDelta =4$. The tree from Fig. 6 with $x=1$ has 14 fixed points, this is the maximal attainable value.

Fig. 6.

If $x\ge \varDelta /2$ then $|\mathcal {F}_{\mathcal {M}}(T)|= 2^{n-\varDelta }$.

For $\varDelta < n/2$ we will prove a much better bound than that of Lemma 4. For this we need the following technical result.

Lemma 5

Let $T=(V,E)$ be a tree with a single node v that has degree larger than 2. Let $\mathcal{D}=[dist(w,v)\;|\;w\in V, w\not =v]$ be the multi-set with the distances of all nodes to v. Then

$$|E_{fix}(T)|= \sum _{S\subset \mathcal{D}, |S|\le \varDelta /2}~\prod _{s\in S} \mathbb {F}_{s-1} \prod _{s\in \mathcal{D}\setminus S}\mathbb {F}_{s}.$$

Proof

Let $\mathcal{P}$ be the set of all $\varDelta$ paths from v to a leaf of T. Let $F\in E_{fix}(T)$. Then $\mathcal{P}_F= \{P \in \mathcal{P} \;|\;F \cap P \not \in E_{fix}(P)\}$. Let $P\in \mathcal{P}_F$ and $v_P$ the node of P adjacent to v. Then $(v,v_P)\in F$. This yields $|\mathcal{P}_F|\le \varDelta /2$. For $P\in \mathcal{P}$ let $\hat{P}$ be an extension of P by an edge (v, x) with a new node x. Then $F \cap P \in E_{fix}(\hat{P})$ for each $P\in \mathcal{P}_F$. By Cor. 1 there are $\mathbb {F}_{|P|-2}$ possibilities for $F\cap P$. Let $\bar{\mathcal{P}}_F= \mathcal{P} \setminus \mathcal{P}_F$. For $P\in \bar{\mathcal{P}}_F$ we have $(v,v_P)\not \in F$. Hence, $F \cap P \in E_{fix}(P)$. By Cor. 1 there are $\mathbb {F}_{|P|-1}$ possibilities for $F\cap P$. Also $|\bar{\mathcal{P}}_F|= \varDelta - |\mathcal{P}_F|$.

Let $\mathcal{P}_1 \subset \mathcal{P}$ with $|\mathcal{P}_1|\le \varDelta /2$ and $\hat{F}_P\in E_{fix}(\hat{P})$ for all $P\in \mathcal{P}_1$ and $F_P\in E_{fix}(P)$ for all $P\in \mathcal{P}\setminus \mathcal{P}_1$. Then the union of all $\hat{F}_P$ and all $F_P$ is a member of $E_{fix}(T)$. This yields the result.   $\square$

Corollary 2

Let T be a l-generalized star graph. Then

$$|E_{fix}(T)|= \sum _{i=0}^{\lfloor \varDelta /2 \rfloor }\left( {\begin{array}{c}\varDelta \\ i\end{array}}\right) \mathbb {F}_{l-1}^i \mathbb {F}_{l}^{\varDelta -i}.$$

The corollary yields that a star graph (i.e. $l=1$) has two fixed points. For $l=2$ we have the following result.

Lemma 6

Let T be a 2-generalized star graph. Then $|E_{fix}(T)|\le \mathbb {F}_{n-\lceil \varDelta /2\rceil }$.

Proof

We use Corollary 2. If $\varDelta \equiv 0(2)$ then

$$|E_{fix}(T)|= \sum _{i=0}^{\lfloor \varDelta /2 \rfloor }\left( {\begin{array}{c}\varDelta \\ i\end{array}}\right) = \frac{1}{2}\left( 2^\varDelta + \left( {\begin{array}{c}\varDelta \\ \varDelta /2\end{array}}\right) \right) \le \mathbb {F}_{3\varDelta /2+1} = \mathbb {F}_{n-\varDelta /2},$$

otherwise $|E_{fix}(T)| =2^{\varDelta -1} \le \mathbb {F}_{n-\lceil \varDelta /2\rceil }$.   $\square$

In Theorem 2 we prove that the upper bound of Lemma 6 holds for all trees. First, we prove two technical results.

Lemma 7

Let T be a tree and v a leaf of T with neighbor w. Let $n_l$ (resp. $n_{i}$) be the number of neighbors of w that are leaves (resp. inner nodes). If $n_l>n_{i}$ then $E_{fix}(T)=E_{fix}(T\setminus v)$.

Proof

Clearly, $E_{fix}(T\setminus v)\subseteq E_{fix}(T)$. Let $F\in E_{fix}(T)$. Then $deg_{F}(w)\le n_i$. Thus, $2deg_{F}(w)\le 2n_i\le n_l-1+n_i=deg_T(w)-1$. Hence, $F\in E_{fix}(T\setminus v)$, i.e., $E_{fix}(T)\subseteq E_{fix}(T\setminus v)$.   $\square$

Lemma 8

Let T be a tree and v, w, u a path with $deg(v)=1$ and $deg(w)=2$. Then $|E_{fix}(T)|\le |E_{fix}(T_v)|+|E_{fix}(T_w)|$ with $T_v=T\setminus v$ and $T_w=T_v\setminus w$.

Proof

Let $F\in E_{fix}(T)$ and $e=(u,w)$. If $e\in F$ then $F\setminus e \in E_{fix}(T_w)$ otherwise $F \in E_{fix}(T_v)$. This proves the lemma.   $\square$

Lemma 9

$|E_{fix}(T)| \le \mathbb {F}_{n-\lceil \varDelta /2\rceil }$ for a tree T with n nodes.

Proof

The proof is by induction on n. If $\varDelta =2$ the result holds by By Cor. 1. If T is a star graph then $|\mathcal {F}_{\mathcal {{M}}}(T)|=2$, again the result is true. Let $\varDelta > 2$ and T not a star graph. Thus, $n>4$. There exists an edge (v, w) of T where v is a leaf and all neighbors of w but one are leaves. If $deg(w)>2$ then there exists a neighbor $u\not =v$ of w that is a leaf. Let $T_u=T\setminus u$. Then $|E_{fix}(T)|=|E_{fix}(T_u)|$ by Lemma 7. Since $\varDelta (T_u)\ge \varDelta (T)-1$ we have by induction $|E_{fix}(T)|=|E_{fix}(T_u)| \le \mathbb {F}_{n-1-\lceil \varDelta (T_u)/2\rceil }\le \mathbb {F}_{n-\lceil \varDelta (T)/2\rceil }$. Hence, we can assume that $deg(w)=2$.

Let $u\not =v$ be the second neighbor of w. Denote by $T_v$ (resp. $T_w$) the tree $T\setminus v$ (resp. $T\setminus \{v,w\}$). By Lemma 8 we have $|E_{fix}(T)|\le |E_{fix}(T_v)|+|E_{fix}(T_w)|$. If there exists a node different from u with degree $\varDelta$ then $|E_{fix}(T)|\le \mathbb {F}_{n-1-\lceil \varDelta /2\rceil } + \mathbb {F}_{n-2-\lceil \varDelta /2\rceil } = \mathbb {F}_{n-\lceil \varDelta /2\rceil }$ by induction. Hence we can assume that u is the only node with degree $\varDelta$. Repeating the above argument shows that T is 2-generalized star graph with center node u. Hence, $|E_{fix}(T)| \le \mathbb {F}_{n-\lceil \varDelta /2\rceil }$ by Lemma 6.   $\square$

Lemmas 4 and 9 prove the upper bound of Theorem 2. The bound of Lemma 9 is sharp for paths. Note that for a fixed value of n the monotone functions $\mathbb {F}_{n-\lceil \varDelta /2\rceil }$ and $2^{n-\varDelta }$ intersect in $\varDelta \in (\lceil n/2\rceil , \lceil n/2\rceil +1)$.

4.3 Lower Bounds for $|\mathcal {F}_{\mathcal {M}}(T)|$

A trivial lower bound for $|\mathcal {F}_{\mathcal {M}}(T)|$ for all trees is $1+|E_{fix}(T)|$. It is sharp for star graphs. For a better bound other graph parameters besides n are required.

Lemma 10

Let T be a tree and $T_L$ the tree obtained from T by removing all leaves. Then $|E_{fix}(T)|\ge 2^{r/2}$, where r is the number of inner nodes of $T_L$.

Proof

By induction we prove that $T_L$ has a matching M with r/2 edges. Then $M\subseteq E_{fix}(T)$ and each subset of M is $\mathcal {F}$-legal.    $\square$

Applying Lemma 10 to a 2-generalized star graph yields a lower bound of 1, which is far from the real value. Another lower bound for $|E_{fix}(T)|$ uses D, the diameter of T. Any tree T with diameter D contains a path of length $D+1$. Thus, $|E_{fix}(T)|\ge F_{D}$ by Cor. 1. This completes the proof of Theorem 2. We show that there are trees for which $|E_{fix}(T)|$ is much larger than $F_{D}$. Let $n,D,h\in \mathbb {N}$ with $n-2 > D \ge 2(n-1)/3$ and $n-D-1\le h\le 2D-n+1$. Let $T_{n,D,h}$ be a tree with n nodes that consists of a path $v_0,\ldots ,v_D$ and another path of length $n-D-2$ attached to $v_h$. Clearly, $T_{n,D,h}$ has diameter D. Also $deg(v_h)=3$, all other nodes have degree 1 or 2. Figure 7 shows $T_{n,D,h}$.

Fig. 7.

A tree $T_{n,D,h}$.

Lemma 11

$|E_{fix}(T_{n,D,h})| = \mathbb {F}_D\mathbb {F}_{n-D-1} + \mathbb {F}_{h} \mathbb {F}_{D-h}\mathbb {F}_{n-D-2}$.

Proof

Let $e=(v_h,v_{D+1})$ and $T_{v_h},T_{v_{D+1}}$ the constituents of T for e. Then $|E_{fix}(T)|= |E_{fix}(T_{v_h},v_h)||E_{fix}(T_{v_{D+1}},v_{D+1})| + |E_{fix}(T_{v_h})||E_{fix}(T_{v_{D+1}})|$ by Lemma 1. Clearly, $|E_{fix}(T_{v_h},v_h)|= \mathbb {F}_h\mathbb {F}_{D-h}$ and $|E_{fix}(T_{v_{D+1}},v_{D+1})|= \mathbb {F}_{n-D-2}$ by Cor. 1.    $\square$

Lemma 17 of [23] determines the value $h_0$ for which $|E_{fix}(T_{n,D,h})|$ is maximal and show that $|{E}_{fix}(T_{n,D,h_0})| = \mathbb {F}_D\mathbb {F}_{n-D-1} + \mathbb {F}_{h_0} \mathbb {F}_{D-h_0}\mathbb {F}_{n-D-2}$. Let $T_{n,D}$ be a tree that maximizes the number of fixed points among all trees with n nodes and diameter D. An interesting question is about the structure of $T_{n,D}$. By an exhaustive search among all trees with $n\le 34$ there was just a single case where this was not a star-like tree (all nodes but one have degree 1 or 2) that maximizes the number of fixed points (see [23]). We have the following conjecture.

Conjecture 1

Except for a finite number of cases for each combination of n and D there exists a star-like graph that maximizes the number of fixed points.

4.4 Special Cases

Lemma 12

Let T be a tree with $n\ge 4$ and $\varDelta \ge n -\lceil n/3\rceil$ then $|E_{fix}(T)|\le 2^{n-\varDelta -1}$. This bound is sharp.

Proof

First we construct a tree $T_m$ realizing this bound. Let $T_m$ be a tree with a single node v with degree $\varDelta$, $x=2\varDelta -n+1$ neighbors of v are leaves and the remaining $\varDelta -x=n-\varDelta -1$ neighbors have degree 2 (see Fig. 6). Assumption $\varDelta \ge n -\lceil n/3\rceil$ implies $\varDelta -x \le \varDelta /2$. Hence $E_{fix}(T_m)= \sum _{i=0}^{\varDelta -x}\left( {\begin{array}{c}\varDelta -x\\ i\end{array}}\right) =2^{\varDelta -x}= 2^{n-\varDelta -1}$ (see also Lemma 5).

Let v be a node of T with degree $\varDelta$. Assume that at most two neighbors of v are leaves. Then $n\ge \varDelta + 1 + \varDelta -2= 2\varDelta -1$. This yields $\varDelta \le (n+1)/2$, which contradicts the assumption $\varDelta \ge n -\lceil n/3\rceil$. Hence, at least three neighbors of v are leaves. Let w be a non-leaf neighbor of v and $e=(v,w)$. Without loss of generality we can assume that $deg(w)=2$ and that the neighbor $v'\not = v$ is a leaf. Next we apply Lemma 1. Let x be a neighbor of v that is a leaf. Note that $E_{fix}(T_v,u)= E_{fix}(T_v\setminus \{w,x\})$. By induction we have $|E_{fix}(T_v,u)|\le 2^{n-\varDelta -2}$. We also have $|E_{fix}(T_v)|\le 2^{n-\varDelta -2}$. This yields the upper bound.    $\square$

Let T be a tree with $n -\lceil n/3\rceil > \varDelta > (n-1)/2$. In [23] it is proved that $|E_{fix}(T)| \le \sum _{i=0}^{\lfloor \varDelta /2\rfloor } \left( {\begin{array}{c}n-\varDelta -1\\ i\end{array}}\right)$. This bound is sharp. Let $\tau _{n,\varDelta }$ be the maximal value of $|E_{fix}(T)|$ for all trees T with n nodes and maximal degree $\varDelta$. We have the following conjecture. If this conjecture is true, it would be possible to determine the structure of all trees with $|E_{fix}(T)|=\tau _{n,\varDelta }$.

Conjecture 2

$\tau _{n,\varDelta } = \tau _{n-1,\varDelta } +\tau _{n-2,\varDelta }$ for $\varDelta < (n-1)/2$.

5 Pure 2-Cycles

In this section we prove an upper bound for $|\mathcal {P}_{\mathcal {M}}(T)|$. We use the fact $|\mathcal {P}_{\mathcal {M}}(T)| = 2|E_{pure}(T)|$ from [22]. Algorithm 1 is easily adopted to compute $|E_{pure}(T)|$. The difference between $\mathcal {F}$-legal and $\mathcal {P}$-legal is that instead of $2deg_{F}(v) \le deg(v)$ condition $2deg_{F}(v) < deg(v)$ is required. If deg(v) is odd then the conditions are equivalent. Thus, it suffices to define for each node $v_i$ with even degree $b_i=\lfloor deg(v_i)/2\rfloor -1$. Hence, $|E_{pure}(T)|$ can be computed in time $O(n\varDelta )$.

Note that $E_{pure}(T) \subseteq E_{fix}(T)$ with $E_{pure}(T)=E_{fix}(T)$ if all degrees of T are odd. Thus, $|E_{pure}(T)|\le F_{n-\lceil \varDelta /2\rceil }$. In this section we prove the much better general upper bound stated in Theorem 3. We start with an example. Let $n\equiv 0(2)$ and $H_n$ the tree with n nodes consisting of a path $P_n$ of length n/2 and a single node attached to each inner node of $P_n$ (see Fig. 8). Since all non-leaves have degree 3 we have $E_{pure}(H_n)=E_{fix}(P_n)$, thus, $|E_{pure}(H_n)|\le F_{n/2}$ by Corollary 1. We prove that $F_{\lfloor n/2\rfloor }$ is an upper bound for $|E_{pure}(T)|$ in general.

Fig. 8.

The graph $H_{10}$, edges of $E^3(H_{10})$ are depicted as solid lines.

We first state a few technical lemmas and then prove Theorem 3. The proof of the first Lemma is similar to Lemma 7.

Lemma 13

Let T be a tree, v a leaf with neighbor w, and $T'=T\setminus v$. Let $n_l$ (resp. $n_{i}$) be the number of neighbors of w that are leaves (resp. inner nodes). If $n_l>n_{i}+1$ then $|E_{pure}(T)|=|E_{pure}(T')|$.

For a tree T let $T^2$ be the tree obtained from T by recursively removing each node v with degree 2 and connecting the two neighbors of v by a new edge. Note that $T^2$ is uniquely defined and $deg_{T^2}(v) = deg_T(v)$ for each node v of $T^2$.

Lemma 14

$E_{pure}(T)\subseteq E_{pure}(T^2)$ for each tree T.

Proof

Let w be a node v of T with degree 2. Let $T'$ be the tree obtained from T by removing w and connecting the two neighbors of w by a new edge. Let $F \in E_{pure}(T)$. Since $deg(w)=2$ no edge of F is incident to w. Thus, for all $v\not =w$ we have $2deg_{F}(v)< deg_T(v)=deg_{T'}(v)$, i.e., $F\in E_{pure}(T')$. Hence, $E_{pure}(T)\subseteq E_{pure}(T')$ and the statement follows by induction.    $\square$

Proof

(Proof of Theorem 3). Proof by induction on n. The statement is true for $n\le 5$ as can be seen by a simple inspection of all cases. Let $n\ge 6$. By Lemma 14 we can assume that no node of T has degree 2. Let $\hat{T}$ be the tree induced by the edges in $E^3(T)$. $\hat{T}$ includes all inner nodes of T. Let u be a node of $\hat{T}$ such that all neighbors of u in $\hat{T}$ except one are leaves. Denote the neighbors of u in $\hat{T}$ that are leaves by $v_1,\ldots ,v_d$ with $d\ge 1$, i.e., $deg_{\hat{T}}(u)=d+1$. Let $e_i=(u,v_i)$. By Lemma 13 we can assume $deg_T(v_i)=3$ for $i=1,\ldots ,d$. Denote the two neighbors of $v_i$ in $T\setminus \hat{T}$ by $v_i^a$ and $v_i^b$. Let $H_1=\{F\in E_{pure}(T) \;|\;e_1\not \in F\}$ and $T'=T\setminus \{v_1^a,v_2^b\}$. Clearly $H_1=E_{pure}(T')$. Thus, $|H_1|\le \mathbb {F}_{\lfloor n/2\rfloor -1}$ by induction. Assume that u has a neighbor $u'$ in T that is a leaf in T. Let $F\in E_{pure}(T)\setminus H_1$. Then $F\setminus \{e_1\}\in E_{pure}(T\setminus \{u',v_1,v_1^a,v_1^b\})$. Thus, by induction $|E_{pure}(T)\setminus H_1| \le \mathbb {F}_{\lfloor n/2\rfloor -2}$ and hence, $|E_{pure}(T)|\le \mathbb {F}_{\lfloor n/2\rfloor }$. Therefore we can assume that $deg_T(u) = d+1$, i.e., $d\ge 2$.

Next we expand the definition of $H_1$ as follows. For $i=1,\ldots ,d$ let $H_i= \{F\in E_{pure}(T)\;|\;e_i\not \in F \text { and } e_1,\ldots , e_{i-1} \in F\}$. Thus, $H_i=\emptyset$ for $i\ge (d+3)/2$ since $2deg_F(u) < d+1$. Let $d_0= \lfloor (d+1)/2\rfloor$. Then $E_{pure}(T)=H_1 \cup \ldots \cup H_{d_o}$. We claim that $|H_i|\le \mathbb {F}_{\lfloor n/2\rfloor -(2i-1)}$. The case $i=1$ was already proved above. Let $i\ge 2$ and define $T_i= T\setminus \{v_j,v_j^a,v_j^b\;|\;j=i-1,i\}$. Then $|E_{pure}(T_i)|\le \mathbb {F}_{\lfloor n/2\rfloor -3}$ by induction, hence $|H_2|=|E_{pure}(T_2)|\le \mathbb {F}_{\lfloor n/2\rfloor -3}$. Let $i\ge 3$ and $F\in H_i$. Then $F\setminus \{e_{i-1}\} \in E_{pure}(T_i)$. Clearly, $E_{pure}(T_i)\setminus H_i$ consists of all $F \in E_{pure}(T_i)$ for which $\{e_1,\ldots , e_{i-2}\} \cap F \not = \emptyset$ holds. Hence,

$$|H_i| \le |E_{pure}(T_i)|- |\bigcup _{j=1}^{i-2} E_j^i|\le \mathbb {F}_{\lfloor n/2\rfloor -3} - |\bigcup _{j=1}^{i-2} E_j^i|$$

where $E_j^i=\{F\in E_{pure}(T_i) \;|\;e_{j}\not \in F\}$. We use the following well known identity for $I=\{1,\ldots ,i-2\}$.

$$|\bigcup _{i\in I} E_i|=\sum _{\emptyset \not = J \subseteq I} (-1)^{|J|+1} |\bigcap _{j\in J} E_i|$$

Note that $|\bigcap _{j\in J} E_j^i|\le \mathbb {F}_{\lfloor n/2\rfloor -(|J|+3)}$ by induction. Let $k=i-2$. Then

$$|H_i| \le \mathbb {F}_{\lfloor n/2\rfloor -3} - \sum _{j=1}^{k}(-1)^{j+1} \left( {\begin{array}{c}k\\ j\end{array}}\right) \mathbb {F}_{\lfloor n/2\rfloor -(j+3)}= \sum _{j=0}^{k}(-1)^{j} \left( {\begin{array}{c}k\\ j\end{array}}\right) \mathbb {F}_{\lfloor n/2\rfloor -(j+3)}$$

Note that $\lfloor n/2\rfloor \ge 2k+3$. Lemma 25 of [23] implies $|H_i| \le \mathbb {F}_{\lfloor n/2\rfloor -(2i-1)}$. Then Lemma 15 yields

$$|E_{pure}(T)| \le \sum _{i=1}^{d_0} |H_i|\le \sum _{i=1}^{d_0} \mathbb {F}_{\lfloor n/2\rfloor -(2i-1)} \le \mathbb {F}_{\lfloor n/2\rfloor }.$$

   $\square$

Lemma 15

For each $c\ge 1$ and $d \le \frac{c+1}{2}$ we have $\sum _{i=1}^{d}\mathbb {F}_{c-(2i-1)}\le \mathbb {F}_c$.

Proof

The proof is by induction on d. The cases $d\le 2$ clearly hold. Let $d>2$. By induction we get

$$\sum _{i=1}^{d}\mathbb {F}_{c-(2i-1)}\!=\! \mathbb {F}_{c-1} + \sum _{i=2}^{d}\mathbb {F}_{c-(2i-1)}\! =\! \mathbb {F}_{c-1} + \sum _{i=1}^{d-1}\mathbb {F}_{c-2-(2i-1)} \!{\mathop {\le }\limits ^{\text {Ind.}}}\! \mathbb {F}_{c-1} + \mathbb {F}_{c-2} \!=\! \mathbb {F}_c.$$

6 Conclusion and Open Problems

The problem of counting the fixed points for general cellular automata is #P-complete. In this paper we considered counting problems associated with the minority/majority rule of tree cellular automata. In particular we examined fixed points and pure 2-cycles. The first contribution is a novel algorithm that counts the fixed points and the pure 2-cycles of such an automata. The algorithms run in time $O(\varDelta n)$. It utilizes a characterization of colorings for these automata in terms of subsets of the tree edges. This relieved us from separately treating the minority and the majority rule. The second contribution are upper and lower bounds for the number of fixed points and pure 2-cycles based on different graph parameters. We also provided examples to demonstrate the cases when these bounds are sharp. The bounds show that the number of fixed points (resp. 2-cycles) is a tiny fraction of all colorings.

There are several open questions that are worth pursuing. Firstly, we believe that it is possible to sharpen the provided bounds and to construct examples for these bounds. In particular for the case $\varDelta \le n/2$, we believe that our bounds can be improved. Another line of research is to ext minority/majority rules. One option is to consider the minority/majority not just in the immediate neighborhood of a node but in the r-hop neighborhood for $r>1$ [15]. We believe that this complicates the counting problems considerably. Finally the predecessor existence problem and the corresponding counting problem [7] have not been considered for tree cellular automata. The challenge is to find for a given $c \in \mathcal {C}(T)$ a coloring $c' \in \mathcal {C}(T)$ with $\mathcal {M}(c')=c$. A coloring $c \in \mathcal {C}(T)$ is called a garden of Eden coloring if there doesn’t exist a $c' \in \mathcal {C}(T)$ with $\mathcal {M}(c')=c$. The corresponding counting problem for tree cellular automata is yet unsolved.