Compatible Sequences and a Slow Winkler Percolation

DOI10.1017/S0963548304006340MaRDI QIDQ4650642zbMATH OpenOpenAlexFDO

Authors Peter Gács

Publication date 18 February 2005

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0011008

zbMATH Keywords

colliding random walkscompatible sequencesdependent percolationmulti-scale analysispower-law behavioursynchronization problem

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graph theory (including graph drawing) in computer science (68R10) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41)

Abstract: Two infinite 0-1 sequences are called compatible when it is possible to cast out 0's from both in such a way that they become complementary to each other. Answering a question of Peter Winkler, we show that if the two 0-1-sequences are random i.i.d. and independent from each other, with probability p of 1's, then if p is sufficiently small they are compatible with positive probability. The question is equivalent to a certain dependent percolation with a power-law behavior: the probability that the origin is blocked at distance n but not closer decreases only polynomially fast and not, as usual, exponentially.

Recommendations

• Compatible sequences and a slow Winkler percolation
• Percolation on sequences of graphs
• Percolation on dense graph sequences
• Percolation on random graphs with a fixed degree sequence
• Slow convergence in bootstrap percolation
• Percolation in Random Cantor Sets
• Stochastic domination and comb percolation
• A combinatorial result with applications to self-interacting random walks
• Ergodicity and indistinguishability in percolation theory
• Percolation of coalescing random walks

Cited in

(9)

• Oriented percolation in a random environment
• Percolation and disorder-resistance in cellular automata
• Scheduling of non-colliding random walks
• Clairvoyant embedding in one dimension
• On a Form of Coordinate Percolation
• Lipschitz embeddings of random sequences
• Compatible sequences and a slow Winkler percolation
• Clairvoyant scheduling of random walks
• On the Compatibility of Binary Sequences

This page was built for publication: Compatible Sequences and a Slow Winkler Percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4650642)