Compression
Particles following a local stochastic rule must gather into a configuration with small perimeter.
Problem statement and measuresexpand
Starting connected, the \(n\) particles perform a Markov chain (at each step one particle, chosen at random, proposes a move and accepts it with a probability that depends only on its neighbourhood) with bias \(\lambda\) towards having more neighbours. The system is \(\alpha\)-compressed if its perimeter is at most \(\alpha\) times the minimum possible.
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
Markov chain, sequential
standard settingverifiedFor \(\lambda > 2+\sqrt2\) the system eventually compresses; for \(\lambda < 2.17\) it expands.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Memory: constant memory
- Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.
- Scheduler: sequential
- At most one particle is active at any time.
- Orientation: no orientation
- Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
- Randomness: randomized
- Particles flip fair coins; guarantees hold with high probability or in expectation.
- Initial shape: holes allowed
- The initial set of occupied nodes induces a connected subgraph; it may enclose empty regions.
- Connectivity during execution: stays connected
- At every time the occupied nodes induce a connected subgraph.
What is known
Results, in order of publication
Introductory and current best; with all but exponentially small probability.
Open questions
Behaviour for \(2.17 \le \lambda \le 2+\sqrt2\), and bounds on the convergence time.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.