Home›Programmable matter›Self-organising particle systems›Compression›Separation of coloured particles
Separation of coloured particles
Particles of two colours, following a local stochastic rule, must cluster by colour (or mix).
Problem statement and measuresexpand
Each particle has one of two colours. Particles run a local Markov chain with a bias \(\lambda\) towards more neighbours and a bias \(\gamma\) towards neighbours of the same colour. The system should be compressed and separated (few pairs of neighbours of different colours), or integrated (colours mixed), with high probability in the stationary distribution.
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Moves
unknown
\(\text{eventually}\) vs —
unknown
— vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.