Fixed point theorem on graphs? Originally posted here: https://math.stackexchange.com/questions/276167/fixed-point-theorem-on-graphs
--
I have a graph $G=(V,E)$ where to each vertex $v$ I have associated a value, $\hat{v}$ (ie I have a "network" in the terminology here http://snap.stanford.edu/snap/index.html ).
Let $\phi : \hat{V} \rightarrow \hat{V}$ be the function which takes the value associated to each node and replaces it with median of the values of the adjacent nodes.
Empirically, iterating $\phi$ converges. Why?
edit: The graph is large and follows this model: http://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model . Also, for ~1% of nodes, $\phi$ is the identity. There is some related work here: http://www.cs.cmu.edu/~zhuxj/pub/CMU-CALD-02-107.pdf
edit: Looks like I can just replace the $P(j \rightarrow i)$ in the label propagation paper with $P(j \rightarrow i) = 1\; if \; \text{j is the median, }0 \text{ else}$, then I can copy their convergence result.
edit: Wait, no. If I do that then P changes each step so it's not a direct copy...
 A: If I am not mistaken, this problem was discussed in the article
Zbl 0194.13702
Lyubich, Yu.I.; Tabachnikov, M.I. Subharmonic functions on a directed graph.
Siberian Math. J. 10, 432-442 (1969).
(unfortunately in Russian; I don't know whether there is an English translation)
A: Here are a few thoughts: 


*

*It is easiest to ignore the case of unequal middle values, for example if every vertex has odd degree. Then the set of labels can only stay the same or  get smaller so eventually the states must cycle (perhaps in a cycle of length 1=fixed point).

*It is enough to consider the case that the vertex values are only $0$ and $1$. If I tell you at the start only which vertices are "high" (above a threshhold $t$) and which are low (less than or equal to $t$) that information alone will be enough decide which vertices are high and which are low at each future stage. We can keep track of all the values by running a few of these thresh-hold graphs in parallel.
I can certainly see 


*

*fixed points: Just split into two (or $k$) groups of moderate size and make sure that each vertex has the majority of its neighbors in its own group. To get fancier (with lots of label values), make the maximum and minimum groups very large, make sure everyone has at least one neighbor with its own label and then make extra edges into the maximum and minimum groups to make sure the medians stay where they should.

*cycles of length $2$ Two groups each with the majority of its labels going to the other group. Or 
After I made this illustration I had the insight that there is simply alternation between a $3/7$ high/low split and $7/3$ or $4/6$ and $6/4$, but I still like the picture.
In a few experiments on the Peterson graph (starting with distinct labels) a cycle of length two happened over $95\\%$ of the time. That is probably exactly the same as saying that with $0,1$ labels a two cycle happened this often with an even split, two thirds of the time with a $4/6$ split and one sixth of the time with a $3/7$ split. In that case it would be easy to figure out the exact probabilities.
Other graphs could be explored. For a pentagonal prism the chance of a two cycle is higher. Even with a $8/2$ split it is $22\\%$ (OK, I can see why) whereas this can not happen in a Peterson Graph.
Q: Can there be cycles of length three or larger? I did not see any but I did not look all that hard. However I would guess not.
It might be worth considering weighted edges, then the examples above can have merely $k$  vertices.

Consider large  graphs (random or structured) with random labels $0$ and $1.$ Then the situation is like voting with everyone swayed by their friends (over many rounds) or some lattice with points magnetized up or down then affecting their neighbors (so this must be studied someplace). If the labels are assigned with very unequal frequencies then one would expect a sea of the majority value with islands of the minority value which shrink (or grow) for a while before stabilizing or going away (or going into a few two cycles). Big islands with lakes with little islands (containing ponds) in them would be possible by pre-planning but perhaps unlikely by chance. As the probabilities become closer to equal it would take a longer and longer time to stabilize with a phase transition at some point which might be very interesting to consider.

A final thought is that the tie breaking problem for an even number of neighbors could be avoided by saying that the value at the vertex is also counted in the median calculations when needed to break a tie. Weighted edges would also avoid this problem (if the weights were random enough to avoid ties).
