# Existence of a Graph and Vertices Function

Let $G$ be a connected, undirected graph, with countably infinite set vertices and countably infinite set of edges. Assume the degree of each vertex is finite.

Let each vertex carry one of two values: $1$ or $-1$.

Now, repeatedly update $G$ by replacing the value at each vertex with the value carried by most of its neighbors (in case of a draw - the value of the vertex remains unchanged). Note that the value at each vertex depends only on the values of its neighbors in the $previous$ state of the whole graph, i.e. the replacement takes place at all vertices simultaneously.

Does there exist such a graph as described, with certain initial values at vertices, that contains a vertex where the value is $not$ eventually constant, after many updates, and not eventually changes with a period of two (e.g. $1$, $-1$, $1$, $-1$...)?

Thank you.

## 1 Answer

Consider an "infinitely tall binary tree": Let the vertices be labeled by pairs of integers $\mathbb N\times\mathbb Z$ and let there be edges between every $(a,b)$ and $(\lfloor a/2\rfloor, b+1)$.

This graph is 3-regular.

In the initial state the value at $(a,b)$ is $+1$ if $|b|$ is a prime and $-1$ otherwise.

As you run the automaton, pattern will keep moving up one line per turn, and since it is not periodic, no cell has a periodic state.