Asynchronous threshold networks (Q1089351)

Let \(G=(V,E)\) be a graph with an initial sign \(s(v)\in \{\pm 1\}\) for every vertex \(v\in V\). When a vertex 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 state if \(s(v)=s'(v)\) for all \(v\in V\). We show that for every graph \(G=(V,E)\) and every initial signs, there is a sequence \(v_ 1,v_ 2,...,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\(\leq i\leq 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.