4:00 pm Wednesday, March 11, 2015
Faculty Colloquium: Phase transitions in random graphs by Lorenzo Sadun (U.T. Austin) in RLM 5.104
Large random graphs serve to model complex networks. As such, it makes sense to study the likelihood of certain properties, what a typical graph with those properties looks like. We will see that there can be phase transitions, in which the answers to these questions change suddenly as the parameters cross certain thresholds. The first third of the talk is devoted to setting up the thermodynamic formalism for large, dense, random graphs. What is a random graph? What are graphons? What are the different notions of entropy, and why are they the equivalent? In the middle third, I'll present a specific ``edge-triangle'' model and explore the different phases and different sorts of phase transitions that occur. It is observed that all phases are ``multipodal", meaning that the vertices of typical graphs group into a finite number of clusters, with edges between nodes in cluster i and nodes in cluster j occurring independently with probability p_{ij}. This is backed up by extensive numerics and perturbative expansions, but has only been proven rigorously along some special curves. In the last third I'll present a different model, involving "k-stars" instead of triangles, and prove that all phases are multipodal. Finally, I'll present some conjectures and open problems. This is joint work with Rick Kenyon, Charles Radin and Kui Ren. Submitted by
|
|