Models of Random Graphs

Gregory McColm

(University of Southern Florida)

There are many models of random structures around -- more than just random n-vertex, m-edge graphs, or the n-vertex trees, etc -- and which one you use depends on what you want to do. Many of these models fix a number of vertices, and then choose a number of edges: sometimes, the edges are tossed in, one at a time. We take a general look at these models, and at 'upwards closed' properties of graphs (properties which, once true, remain true if more edges are added), and we look at some applications of some of these models. We will also look at the asymptotic probabilities of logical queries on these models.
Tuesday 15th April 1997, 14:30
Seminar Room 322
Department of Computer Science