3:00 pm Wednesday, December 2, 2015
Random Structures: Bipodal Random Graphs above Erdos-Renyi by Lorenzo Sadun (The University of Texas at Austin) in 8.136
We consider large dense random graphs on N vertices in which the density of an associated sub-graph H (say, a triangle) is slightly higher than would be expected from an Erdos-Renyi graph. We prove that as , the structure of the random graph becomes ``bipodal''. This means that there are two classes of vertices, say red and blue, and fixed edge probabilities for red-red, red-blue, and blue-blue edges. Furthermore, this behavior is universal, in that it applies to all choices of sub-graph H. Submitted by
|
|