Asynchronous threshold networks

LetG=(V,E) be a graph with an initial signs(v)∈{±1} for every vertexv∈V. When a certexv becomesactive, it resets its sign tos′(v) which is the sign of the majority of its neighbors(s′(v)=1 if there is a tie).G is in astable state if,s′(v) for allv∈V. We show that for every graphG=(V,E) and every initial signs, there is a sequencev 1,v 2,...,v r of vertices ofG, in which no vertex appears more than once, such that ifv i becomes active at timei, (1≤i≤r), then after theser stepsG reaches a stable state. This proves a conjecture of Miller. We also consider some generalizations to directed graphs with weighted edges.