Longest and heaviest paths in random directed graphs

Our speaker is Prof. Takis Konstantopoulos (University of Liverpool)

Abstract: I will give an overview of research in the area of random directed graphs with possibly random edge weights. We are interested in longest paths between two vertices (or heaviest paths if there are weights). Typically, the longest path satisfies a law of large numbers and a central limit theorem (which gives a non-normal distribution in the limit if the vertex set is not one-dimensional). The constant in the law of large numbers as a function of the graph parameters and weight distributions cannot be computed explicitly except, perhaps, in very simple cases. A lot of work has been done in obtaining bounds and in studying its behaviour. For example, is it a smooth function of the connectivity parameter p? These kinds of graphs appear in several areas: in computer science, in statistical physics, in performance evaluation of computer systems and in mathematical ecology. They originated in a paper by Barak and Erdos but have also been studied independently, in connection with the applications above. The questions asked are related to the so-called last passage percolation problems because we can interpret “longest” in a time sense (what’s the worst case road that will take us from a point to another point?). As such, it is not surprising that in some cases, the limiting behaviour is related to limits of large random matrices. However, the complete picture is not understood and so open problems will also be presented. This is a long-standing ongoing project, based on several papers (completed or in progress) with Sergey Foss, Denis Denisov, Katja Trinajstic, Artem Pyatkin, Bastien Mallein and Sanjay Ramassamy.

Contact: This seminar is taking place on Zoom. If you are interested in joining us, please contact Lanpeng Ji (l.ji@leeds.ac.uk) or Konstantinos Dareiotis (k.dareiotis@leeds.ac.uk) for Zoom detail.