Number Theory Seminar

Speaker: Naina Ralaivaosaona (Stellenbosch University)

Title: The phase transition in random digraphs

Abstract: Directed graphs (or digraphs) are graphs in which the edges are oriented. These structures are just as important as the undirected graphs; they occur naturally in many applications. For example,  directed acyclic graphs (DAGs) are the underlying structure of Bayesian Networks. Random undirected graphs have been studied extensively in the literature since the seminal work of Erdős and Rényi in 1959. One of the most spectacular results in the theory of random graphs is the so-called sharp threshold phenomenon. This phenomenon is also known to occur for random digraphs. However, the structure of digraphs through the critical phase remains largely unknown. Recently, we considered an analytic approach to the analysis of digraphs using generating functions and advanced contour integration techniques. In this talk, I will introduce these techniques and discuss some of the results that we obtained from them. This talk is based on joint work with Dovgal, De Panafieu, Rasendrahasina, and Wagner.