Interdisciplinary Stochastic Processes Colloquium

Tuesday August 19;  4.10 - 5.00    room 60 Evans

Speaker: Christian Borgs (Microsoft Research)

Title: "What Makes a Finite Network High Dimensional:  
	Erdos-Renyi Scaling for Finite Graphs."

*** if you wish to join speaker for lunch, come to 351 Evans at 1.00pm ***
Abstract:

Many models of practical relevance, like faulty wireless networks, are 
well described by random subgraphs of finite graphs, or, more probabilistically, 
by percolation on finite graphs.  For both theoretical and practical reasons, 
one of the most interesting properties of these models is the behavior of the 
largest connected component as the underlying edge density is varied.
While the behavior of the largest component is well understood for the complete 
graph, which was first systematically studied by Erdos and Renyi in 1963, 
not much was known for general finite graphs.  
In the work presented in this talk we formulate a sufficient condition under 
which transitive graphs on N vertices exhibit the same scaling behavior as 
the complete graph, i.e. a scaling window of width N^{-1/3} in which the
size of the largest component is of order N^{2/3}.  Our condition is 
related to a well known condition in percolation theory on infinite
graphs, where it characterizes high dimensionality. 

This work is in collaboration with Jennifer Chayes, Gordon Slade, Joel 
Spencer and Remco van der Hofstad.