Asynchronous threshold networks

Let G=(V,E) be a graph with an initial sign s(v)∈{±1} for every vertex v∈V. When a certex v becomes active, it resets its sign to s′(v) which is the sign of the majority of its neighbors (s′(v)=1 if there is a tie). G is in a stable state if, s′(v) for all v∈V. We show that for every graph G=(V,E) and every initial signs, there is a sequence v ₁, v ₂, ...,v _r of vertices of G, in which no vertex appears more than once, such that if v _i becomes active at time i, (1≤i≤r), then after these r steps G reaches a stable state. This proves a conjecture of Miller. We also consider some generalizations to directed graphs with weighted edges.