*Site best viewed with IE 6.0, Netscape 6.0, or Mozilla
1.4 or better*

### What Makes a Finite Network High-Dimensional: Random Graph Scaling for Finite
Graphs

Jennifer Chayes

Microsoft Corporation

Many models of practical interest, such as 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 key properties of these models is the behavior of the largest connected
component as the underlying edge density is varied. While this behavior is
well understood for the complete graph in the context of random graph theory,
not much was known for general finite graphs.

In this work we formulate a sufficient condition under which transitive finite
graphs exhibit the same scaling behavior as the complete graph, i.e., the
same size of the dominant component and width of the critical window. Our
condition is related to a well-known condition in percolation theory on infinite
graphs, and more generally in field theories of mathematical physics, where
it characterizes high-dimensionality. We verify this condition for many graphs
of interest including the n-cube and the Hamming cube. Our techniques are
a combination of methods from mathematical physics, in particular the lace
expansion, and methods from combinatorics

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

2/9/04

*Dynamic menus by **
*