Anthony Metcalfe: Directed random graphs and the Tracy-Widom distribution

We give a brief introduction to the theory of random graphs by recalling some known results about the standard Erdos-Renyi random graph. We then consider a natural generalisation to 2-dimensional random graphs equipped with a partial order. We recount the results of a recent paper of Konstantopulous and Trinajstic: As the size of the graph increases, the the maximum length of all paths in the graph, appropriately rescaled and centered, converges in distribution to the Tracy-Widom distribution. This distribution is also observed as the the asymptotic limit of the distribution of the largest eigenvalue of a large GUE random matrix.