The other day Christina Goldschmidt gave a very nice talk on results obtained by James Norris and R. W. R. Darling: in their paper they use fluid limit techniques in order to study properties a Random graphs. This approach has long been used to analyse queuing systems for example.
1. Erdos Renyi Random Graph model
Remember that the Erdos Renyi random graph is a graph with vertices such that any two of them are connected with probability , independently.
This model of random graphs has been extensively studied and this has long been known that undergoes a phase transition at : for , the largest component of has a size of order while for the largest connected component , also called the giant component, has size of order . In another blog entry, another consequence of this phase transition has been used.
One can even show that for there exists a constant such that for any ,
Simply put, the largest connected component of has size approximatively equal to . Maybe surprisingly, this is quite simple to compute the value of through fluid limit techniques.
2. Exploration of the graph
Let be a configuration of . This configuration is explored through a classical depth-first algorithm. To keep track of what is doing, a process is introduced. This process captures essentially all the information needed to study the size of the connected component: it is then shown that behaves essentially deterministically when looked under the appropriate scale.
- initilisation: t=0: Color all the vertices in green, the current vertex is and define .
- t=t+1: Color the current vertex in red (=visited): if a vertex is connected to and is green, color it in grey ( this vertex has still to be visited, but its ‘parent’ has already been visited): these are the children of .
- update the following way, , and
- if has children, choose one of them and make it the new current vertex. Go to .
- If has no children then the new current vertex is its parent. Go to .
- if has no children and no parent, the new current vertex is one of the remaining (if any) green vertex. Go to
- else: we are finished.
A moment of though reveals that and reaches precisely when the connected component of the vertex has all been explored. Then reaches precisely when the second connected component has all been explored, etc … This is why if and then the connected components have size exactly for . The largest component has size .
3. Fluid Limit
It is quite easy to show why the rescaled process should behave like a differential equation (ie: fluid limit). While exploring the first component, represents the number of gray vertices at time so that represents the number of green vertices: this is why
so that where . Also, the variance statisfies so that all the ingredients for a fluit limit are present: converges to the differential equation
whose solution is . This is why is implicitly defined as the solution of
As expected, and .
Leave a Reply