110. self-organized segregation on the grid
Name: Hamed Omidvar
Grad Year: 2020
We consider a probabilistic dynamical model of local interactions in self-organized systems in which agents of two types are randomly located on a grid graph and evolve by changing their types depending on the configuration of their neighboring agents. In the language of statistical physics, this corresponds to the Glauber dynamics of the two-dimensional, zero-temperature Ising model, with initial Bernoulli parameter $p=1/2$, and local magnetization threshold $\tau$. The model has wide applicability, ranging from physics, to social science, economics, epidemiology, computer science, and engineering. It has largely resisted rigorous analysis until recently, when some results have appeared in the theoretical computer science literature. Within this context, we enlarge the interval of the values of $ au$ that leads to the formation of large areas of agents of a single type from the known size $epsilon>0$ to size $\approx 0.134$. Namely, we show that for $0.433 < \tau < 1/2$ (and by symmetry $1/2<\tau<0.567$), the expected size of the largest region containing agents of the same type is exponential in the size of the neighborhood. We further extend these results to regions where the ratio of the number of agents of one type and the number of agents of the other type vanishes quickly as the size of the neighborhood grows. In this case, we show that for $0.344 < \tau \leq 0.433$ (and by symmetry for $0.567 \leq \tau<0.656$) the expected size of the largest region with this property is exponential in the size of the neighborhood. This behavior is reminiscent of supercritical percolation, where small clusters of empty sites can be observed within any sufficiently large region of the occupied percolation cluster. The exponential bounds that we provide also imply that complete coverage of the whole grid by agents of a single type, does not occur with high probability for $p=1/2$ and the range of tolerance considered. The model has wide applicability, ranging from statistical physics, to social science, economics, epidemiology, computer science, Nanotechnology, and engineering.
Industry Application Area(s)
Internet, Networking, Systems | Life Sciences/Medical Devices & Instruments | Materials