\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Hamed Amini}
%
%
\medskip
\noindent
%
%
{\bf Bootstrap Percolation and Diffusion in Random Graphs with Given Vertex Degrees}
%
%
\vskip 5mm
\noindent
%
%
%
%
We consider diffusion in random graphs with given vertex degrees.  Our
diffusion model can be viewed as a variant of a cellular automaton
growth process: assume that each node can be in one of the two
possible states, inactive or active.  The parameters of the model are
two given functions $\theta: {\Bbb N} \rightarrow {\Bbb N}$ and
$\alpha:{\Bbb N} \rightarrow [0,1]$.  At the beginning of the process,
each node $v$ of degree $d_v$ becomes active with probability
$\alpha(d_v)$ independently of the other vertices. Presence of the
active vertices triggers a percolation process: if a node $v$ is
active, it remains active forever. And if it is inactive, it will
become active when at least $\theta(d_v)$ of its neighbors are active.
In the case where $\alpha(d) =\alpha$ and $\theta(d) =\theta$, for
each $d \in {\Bbb N}$, our diffusion model is equivalent to what is
called bootstrap percolation. The main result of this paper is a
theorem which enables us to find the final proportion of the active
vertices in the asymptotic case, i.e., when $n \rightarrow
\infty$. This is done via analysis of the process on the multigraph
counterpart of the graph model.



\bye