What Makes a Finite Network High Dimensional: Erdos-Renyi Scaling for Finite Graphs
Christian Borgs, Microsoft Theory Research
November 7, 2003, Wean 7220, 3:30

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.