ITLApplied  Computational Mathematics Division
ACMD Seminar Series
Attractive Image NIST

Reed-Frost Transition on Dense Graphs

Guantao Chen
Department of Mathematics and Statistics, Georgia State University

Wednesday, May 22, 2013 15:00-16:00,
Building 101, Lecture Room C
Wednesday, May 22, 2013 13:00-14:00,
Room 1-4058


The classic Reed-Frost stochastic epidemic process on a population of $n$ elements with probability p can be viewed as a percolation on a complete graph with a given number of initially infective vertices. At each step each infected vertex infects an undeleted and uninfected vertex independently with probability $p$, and all previously infected vertices are removed. The process stops if there is no new infected vertex. The percolation time is the time $t$ when all vertices have been infected or $+\infty$.

In this talk, we extend the the Reed-Frost process from complete graphs to general graphs and obtain a few sufficient conditions on the density of graphs and probability such that with high probability that the percolation time is bounded above by a constant. We also notice that these conditions are best possible in some sense.

Presentation Slides: PDF

Contact: J. Shook

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.

Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2013-05-22.