Lorentz Center - Logic and Random Graphs from 31 Aug 2015 through 4 Sep 2015
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    Logic and Random Graphs
    from 31 Aug 2015 through 4 Sep 2015


Scientific Report for the Lorentz center workshop

“Logic and Random Graphs”


Random graphs are mathematical models of networks that have been studied intensively for over half a century, beginning with the seminal work of Erdős and Rényi.

Given the central position of logic within graph theory and theoretical computer science, it comes as no surprise that researchers have studied random graphs from a logical perspective for nearly as long as random graph theory has existed.  Despite its established role within random graph theory, there is a strong, renewed impetus for research activity on random graphs from a logical perspective. This is partly because recent advances in our understanding of various random graph models, including random graphs with a given degree distribution and random graphs embeddable on surfaces, make it possible to attack questions that were out of reach until very recently.

Another reason for the renewed impetus is related to graph limits. After the introduction of graph limits around 2006, many in the field realized that there is a close connection between graph limits and some of the phenomena and in particular the limit objects produced in the theory of logical limit laws of random graphs.


In this five-day workshop, we gathered together some of the most active and influential researchers in the field, with roughly equal proportions of participant working mostly on random graphs, logic or theoretical computer science, and visiting from several parts of North America and Europe.

There were twenty talks spread over five days, which left ample time for (informal) discussions. This appears to have been appreciated by the participants. On Monday there was an open problem session. Several of the participants are now working on the problems posed by others, and one of the open problems was even solved during the workshop. Another nice, concrete result of the workshop was that one of the keynote speakers, Prof. Luczak, managed to solve an old research problem while preparing his presentation.

The workshop provided a useful platform to view future directions for research in the area. Given the even mix of younger and more established scientists, and of different fields, it was an excellent opportunity for many parties to gain new perspectives.


We are grateful to have received additional support from KNAW, NWO and STAR, which greatly contributed to the success of the event.


Ross Kang (Nijmegen, The Netherlands 

Tobias Müller (Utrecht, The Netherlands)

Jaap van Oosten (Utrecht, The Netherlands) 

Oleg Pikhurko (Coventry, United Kingdom)

Anusch Taraz (Hamburg, Germany)