Continuous Methods in Graph Statistics

Dr. Patrick Bahls
University of North Carolina at Asheville

Thursday, April 24, 2008

4:00 p.m., Manchester Hall Room 016

 

Recall that a tree is a connected, acyclic (undirected) graph. There are a number of means of constructing trees "at random." We will examine the trees resulting from some of these methods, making use of continuous approximations and differential equations to analyze a variety of statistics concerning these trees. For instance, we will compute the expected distance between the ith and jth vertices constructed according to the classical Erdos-Renyi algorithm, examining the implications these estimates have for the diameter of a randomly constructed tree. We will also derive a formula for the expected degree of the ith vertex constructed according to general variations on this algorithm. All work has been done jointly with Samuel R. Kaplan. The talk will assume no knowledge of graph theory and will be accessible to undergraduate students with a background in basic differential equations.

Refreshments will be served at 3:30 p.m. in Manchester Hall Room 336.

Host contact: parslerj@wfu.edu