\documentclass[b5paper,10pt]{book}
\usepackage{InfAlgMaj28}
%%\textheight = 551pt



\setcounter{page}{1}
\setcounter{chapter}{1}


\begin{document}
\thispagestyle{empty}

\vspace{-2mm}
\textcolor{blue}{\section*{Density of safe matrices 
(Winkler modell of percolation): FSU Jena, November 7, 2005}}

\vspace{-2mm}
(downloadable from: 
\hrefun{http://compalg.inf.elte.hu/$\sim$tony/Percolation}{\textbf{http://compalg.inf.elte.hu/$\sim$tony/Percolation}})

\vspace{1.5mm}
A binary matrix $B = [B_{ij}]_{m \times n}$is called \textcolor{blue}{\ki{good}}, 
if it contains at most one 1's in each column; 
the matrix is called \textcolor{blue}{\ki{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},$ $\ldots 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 \textit{safe,} if for any $k \ (k = 1, \ldots, n)$ holds that the first $k$ columns of the 
matrix contain at most $k$ 1's.

Let $\mathbf{Z} = [z_{ij}]_{m\times 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 \geq 1$ we give 
lower and upper bound of the asymptotic probability of the event that a concrete realisation of the matrix $Z$ 
is schedulable. 


\hspace{4cm} \textcolor{magenta}{\textbf{REFERENCES}}

P. Balister, B. Bollob�s, M. Walters (2004),  
\textit{Continuum percolation with steps in an annulus.} 
\textit{Ann. Appl. Probab.} \textbf{14/4} 1869--1879. 
http://arxiv.org/find.

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

I. Der�nyi, G. Palla, T. Vicsek (2005), 
\textit{Clique percolation in random networks.} \textit{Phys. Rev. Lett} 
\textbf{94} 160--202. http://arxiv.org/find.

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

P. G�cs (2002), \emph{Clairvoyant scheduling of random walks} 
(submitted to Electronic Journal of Probability). 
Short version:  \textit{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/recent-publ.html.

P. \textcolor{blue}{\textbf{G�cs}} (2004), \emph{Compatible sequences and a 
slow \textcolor{magenta}{Winkler percolation}}. 
Combin. Probab. Comput. \textbf{13/6}, 815--856. 
\hrefun{http://www.cs.bu.edu/fac/gacs/recent-publ.html}{http://www.cs.bu.edu/fac/gacs/recent-publ.html}.

G. R. \textcolor{blue}{\textbf{Grimmett}}, (1999), \textcolor{magenta}{\emph{Percolation.}} Springer, Berlin, 1999. 

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


H. Kesten (1982), \emph{Percolation Theory for Mathematicians.} Birkh�user, Boston.

D. Schauffer (1985), \textit{Introduction to Percolation Theory.} 
Taylor \& and Francis, London, 1985.

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

N. J. Vilenkin (1972), \emph{Combinatorial Mathematics for Recreation}. Mir Publisher, Moscow. 

P. Winkler (2000), \emph{Dependent percolation and colliding random walks,} 
Random Structures \& Algorithms \textbf{16/1} 58--84. http://www.math.dartmouth.edu/$\sim$pw/papers/pubs.html.




\end{document}
