19
$\begingroup$

Let $G$ be a connected, undirected graph, with countably infinite set of vertices and countably infinite set of edges. Assume that the degree of each vertex is finite, and moreover, the degrees of all vertices are uniformly bounded.

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

Now, equip each vertex with a Poisson clock ($\lambda=1$), all clocks are independent. At each time the clock of a vertex ticks, the vertex updates its value to be the value of most of its neighbors (in case of a draw $-$ the value of the vertex remains unchanged).

Does there exist such a graph as described, with certain initial values at vertices, such that with $\mathbf{positive}$ probability, there will be a vertex where the value is $not$ eventually constant?

Thank you.

$\mathbf{EDIT:}$ If you wish, for a beginning, analyze the example given by domotorp in his comment (which could be a solution): take the $3$-regular tree with initial values as follows: pick one vertex, it will be $1$. The vertices around it will be $-1$. The vertices at distance $2$ from the initial vertex are again $1$. And so on, changing the value layerwise. In this graph and initial values, will there be a vertex, that with positive probability, will not converge? (Even if the answer for this example is NO, the fact that every vertex in the example almost surely converges is also nontrivial, and a proof of this will also be upvoted.)

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ Is there an easy example of a graph and a deterministic sequence of updates on it that would cause a vertex to change values infinitely often? $\endgroup$
    – Kevin P. Costello
    Commented Dec 16, 2016 at 7:36
  • 9
    $\begingroup$ This is an example of a voter model. I know that the answer is yes for the synchronous voter model (where all clocks tick once per second). Indeed: take $\mathbb Z$ with a uniform i.i.d. distribution of $\pm 1$ at the vertices. Then the set of configurations that converge to all 1's is invariant (so of measure 0 or 1); ditto for the configurations that converge to all $-1$'s. By symmetry, they are both of measure 0. From this, it follows that almost surely, each vertex oscillates infinitely often. $\endgroup$
    – Anthony Quas
    Commented Dec 16, 2016 at 8:51
  • 2
    $\begingroup$ @Anthony: Why couldn't the system freeze in some other state? I think if everyone has a neighbor with whom it shares its value, then there are no more changes. $\endgroup$
    – domotorp
    Commented Dec 16, 2016 at 9:34
  • 3
    $\begingroup$ This model seems to be very similar to the Glauber dynamics of the Ising model. $\endgroup$
    – domotorp
    Commented Dec 16, 2016 at 10:01
  • 2
    $\begingroup$ @Kevin: It's easy to give such an example on an infinite $3$-regular tree. I don't know whether this is an example to the original question. In any frozen configuration each constant-valued component most be infinite. $\endgroup$
    – domotorp
    Commented Dec 16, 2016 at 10:03

2 Answers 2

Reset to default
5
+50
$\begingroup$

Yes, my example is easy to modify after some thought, just take a thick enough layer for each level. More precisely, let $f$ be a sufficiently fast growing function, and define the initial value on any vertex at distance $f(n)\le d< f(n+1)$ from the root as $(-1)^n$. Given $f(n)$, one can also pick a large enough $f(n+1)$ such that independently of the later values the root will get $(-1)^n$ in some time that depends only on $f(n+1)$ with at least $50\%$ probability. This guarantees that with $1$ probability it will switch values infinitely often (just like every other vertex).

In more details, suppose first that $f(n+1)=\infty$, i.e., all but a finite number of vertices have the value $(-1)^n$.

Lemma. If all vertices at distance $>r$ have value $(-1)^n$, then with probability $1$ after a while all vertices will have value $(-1)^n$.

Proof. Vertices further than $r$ can never change value. If a vertex at distance $r$ gets value $(-1)^n$, it will never change again. So eventually all vertices at distance $r$ will also obtain value $(-1)^n$ and we can use induction on $r$.

From this it follows that the root will obtain value $(-1)^n$ in some $T(n)$ time with $90\%$ probability. If $f(n+1)$ is not $\infty$, but just large enough compared to $T(n)$, then the probability of any vertex at distance $r+1$ from the root changing value is less than $10\%$. Therefore, this won't affect the probability of the root changing value.

Improve this answer
$\endgroup$
11
  • $\begingroup$ can you please elaborate on how the root getting a color with probability more than half is dependent only on the n+1 first layers? $\endgroup$
    – co.sine
    Commented Apr 6, 2017 at 11:40
  • $\begingroup$ @co.sine: Done! $\endgroup$
    – domotorp
    Commented Apr 6, 2017 at 12:00
  • $\begingroup$ Sorry for the questions, just want to fully understand your idea: where did the 90% come from? And how is f(n) comparable to T(n)? $\endgroup$
    – co.sine
    Commented Apr 6, 2017 at 12:30
  • $\begingroup$ 90% is any number less than and I do not know how T(n) depends on f(n). $\endgroup$
    – domotorp
    Commented Apr 6, 2017 at 12:48
  • $\begingroup$ Tell me if I'm wrong: you state, that for the $3$-regular tree, for a given vertex named the root, and for any distance $d$ from the root, there exists a natural number $N$ such that if all vertices at distance between $d$ and $d+N$ from the root have the value $c$, and the root has value $-c$, then with probability at least $0.9$ (or any other number) sometime in the future the root will change its value to $c$. $\endgroup$
    – co.sine
    Commented Apr 6, 2017 at 15:58
2
$\begingroup$

Doesn't quite answer the question, but in this paper --

http://people.hss.caltech.edu/~tamuz/papers/retention.pdf

-- it is stated that Tessler and Louidor showed that in the infinite d-regular tree with d even (and random tie-breaking), for uniformly random initial spins, almost surely there are vertices that change their spin infinitely often.

I couldn't actually find the paper being referred to, and it doesn't clearly answer the question because of the random tie-breaking.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Apart from the even degree random tie breaking, their result to applies to almost all initial configurations (a set of initial configuration with measure 1). In a specific initial configuration, convergence or divergence cannot be induced from this result. $\endgroup$
    – co.sine
    Commented Mar 20, 2017 at 10:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .