Density of safe matrices (Winkler modell of percolation): FSU Jena, November 7, 2005

(downloadable from: \underline{http://compalg.inf.elte.hu/∼tony/Percolation})

A binary matrix B = [B_{ij}]_{m×n}is called good, if it contains at most one 1’s in each column; the matrix is called schedulable, if it can be transformed into a good matrix repeating the following operation: we remove any zero element m_{i,j} = 0, shift the elements m_{i,j+1}, … m_{i,n} to left and add a new element m_{i,n} = 0 to the i-th row of the matrix; the matrix is called safe, if for any k (k = 1, …, n) holds that the first k columns of the matrix contain at most k 1’s.

Let Z = [z_{ij}]_{m×n} be a matrix containing independent random variables having the join distribution P (z_{i,j} = 1) = p and P (z_{i,j} = 0) = 1 − p. In the case m ≥ 1 we give lower and upper bound of the asymptotic probability of the event that a concrete realisation of the matrix Z is schedulable.

REFERENCES

P. Balister, B. Bollobás, M. Walters (2004), Continuum percolation with steps in an annulus. Ann. Appl. Probab. 14/4 1869–1879. http://arxiv.org/find.

B. Bollobas, O. Riordan (2005), A short proof of the Harris-Kesten theorem. Electronic manuscript, http://arxiv.org/find.

I. Derényi, G. Palla, T. Vicsek (2005), Clique percolation in random networks. Phys. Rev. Lett 94 160–202. http://arxiv.org/find.

W. Feller, (1968), An Introduction to Probability Theory and its Applications. John Wiley and Sons, New York.

P. Gács (2002), Clairvoyant scheduling of random walks (submitted to Electronic Journal of Probability). Short version: Clairvoyant scheduling of random walks. In: Proc. of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 99–108 (electronic), ACM, New York, 2002. http://www.cs.bu.edu/fac/gacs/recentpubl.html.

P. Gács (2004), Compatible sequences and a slow Winkler percolation. Combin. Probab. Comput. 13/6, 815–856. \underline{http://www.cs.bu.edu/fac/gacs/recent-publ.html}.

G. R. Grimmett, (1999), Percolation. Springer, Berlin, 1999.

T. E. Harris (1960), A lower bound for the critical probability in a certain percolation process. Proc. of the Cambridge Phil. Soc. 56 13–20.

H. Kesten (1982), Percolation Theory for Mathematicians. Birkhäuser, Boston. D. Schauffer (1985), Introduction to Percolation Theory. Taylor & and Francis,

London, 1985.

R. P. Stanley (1999), Enumerative Combinatorics, Volume 2. Cambridge Studies in Advanced Mathematics, 62. Cambridge University Press, Cambridge.

N. J. Vilenkin (1972), Combinatorial Mathematics for Recreation. Mir Publisher, Moscow.

P. Winkler (2000), Dependent percolation and colliding random walks, Random Structures & Algorithms 16/1 58–84. http://www.math.dartmouth.edu/∼pw/papers/pubs.html.