On a distributed clustering process of Coffman, Courtois, Gilbert and Piret

Coffman et al. (1991) have introduced a flow process in graphs, where each vertex gets an initial random resource, and where at each time vertices with large resources tend to attract resources from neighbours. The initial resources are assumed to be i.i.d., with a continuous distribution. We are mainly interested in the following question: does, with probability 1, the resource of each vertex change only finitely many times? Coffman et al. concentrate mainly on the case where the graph corresponds with the integer points on the line, in which case it is easily seen that the answer to the above question is positive. For higher-dimensional lattices they make general remarks which suggest that the answer to the above question is still positive. However, no proof seems to be known. We restrict to the case of the square lattice, and, by a percolation approach, we reduce the question above to the question whether a certain quantity, which can be obtained from a finite computation, is sufficiently small. This computation is, however, still too long to be executed in an acceptable time. We therefore apply Monte Carlo simulation for this finite problem, which gives overwhelming evidence that, for the square lattice, the answer to the main question is positive.

• View at Publisher

Full Text ( Final Version , 81kb )