We are studying a random graph model of networks like the World-Wide Web where we keep the graph oriented and allow random deletions of vertices and edges. In so doing we are trying to generalise the following two papers: The first paper has orientation but does not allow for deletions and the second has deletions but does not allow for orientation. With guidance, the undergraduate student will set up (difference) equations for the expected number of vertices of degree k at time t and use various methods to try to solve them, including Laplace’s method and generating functions. The prerequisites are good mathematical skills, especially some knowledge of linear algebra and differential equations.
 Colin Cooper, Alan Frieze, and Juan Vera,
 Béla Bollobás, Christian Borgs,
Jennifer T. Chayes, and Oliver Riordan, , ACM-SIAM Symposium on Discrete Algorithms
(SODA), January 2003, pp. 132-139.
in Internet Mathematics.
Other REUs for Summer 2004
Algorithms for Dynamic Point Location with Good Practical Performance
A Bezier-Based Approach to Unstructured Moving Meshes
Evaluation of Algorithms for the List Update Problem
Exploring PLS-Completeness of Simple Stochastic Game (or Stable Circuit Problem)
Fast and Compact Data Structures
The Game of NimG (Nim on Graphs)
Random Graph Models of Large Real-World Networks
Solving Partial Differential Equations Numerically
Back to the REU page