A357953 Maximum period of a totalistic cellular automaton on a connected graph with n nodes (not counting the state of the updated node itself).

1, 2, 2, 6, 7, 18, 38, 96

Offset

1,2

Comments

Each node can be in one of two states, ON or OFF. The automaton is totalistic, meaning that the state of a node in the next generation depends only on the number of ON-nodes among its neighbors. Since there are finitely many states of the automaton, it will eventually enter a cycle. a(n) is the maximum of the length of that cycle, over all connected graphs with n nodes, all totalistic updating rules, and all initial states.

Links

Table of n, a(n) for n=1..8.

The House of Graphs, Graph 20561.

Eric Weisstein's World of Mathematics, Totalistic Cellular Automaton.

Wikipedia, Cellular automaton.

Formula

a(n) <= A357951(n).

Example

Examples of optimal automata: (The updating rule is given as a set of integers, specifying how many of the neighbors of a node must be ON for the node to be ON in the next generation.)
  n = 1: Path graph; rule {}; the node OFF.
  n = 2: Path graph; rule {0}; both nodes equal.
  n = 3: Path graph; rule {0}; all nodes OFF.
  n = 4: Path graph; rule {1}; one of the end nodes ON.
  n = 5: Complement of the union of a 2-node path and a 3-node path; rule {1,2}; the node of degree 2 ON.
  n = 6: Divisor graph of {1,...,6} (there is an edge between i and j if i is a divisor of j or j is a divisor of i); rule {0,2}; nodes 1 and 2 ON.
  n = 7: Graph 20561 in House of Graphs ('FJe~O' in graph6 format); rule {0,2}; one node of degree 3 ON.
  n = 8: Graph 'G?CidW' in graph6 format; rule {0,2,4}; the node of degree 3 ON.

Crossrefs

Cf. A357951, A357952.

Sequence in context: A060303 A099577 A268500 * A283824 A106168 A106166

Adjacent sequences: A357950 A357951 A357952 * A357954 A357955 A357956

Keyword

nonn,more,hard

Author

Pontus von Brömssen, Oct 22 2022

Status

approved