Topic and Goals of the Seminar

The analysis of large random discrete structures, such as trees, graphs, or permutations, is a focus of research in contemporary discrete mathematics. Logic provides a useful and powerful formalism for expressing and classifying discrete structures; moreover, it is intimately linked to the study of algorithms, computational complexity, and structural graph theory. Over the past several decades, researchers have studied random discrete structures from a logical perspective. The first significant result in this direction was the zero-one law for first-order logic under the uniform measure; this seminal result, was followed by the discovery of ‘logical limit laws’ or ‘convergence laws’ for several different models of random discrete structures and for various logics of significance in computer science. In more recent years, a renewed impetus has emerged for research activity on random discrete structures from a logical perspective. This is in part due to the availability of new methods and techniques, including asymptotic enumeration, discrete harmonic analysis, an extension of Gowers norms, and limit structures. Exciting new results on random geometric graphs, graphs on surfaces, classes of sparse graphs, graph limits, and flag algebras have been established. On the computer science side, there has been a systematic exploration of probabilistic databases, which has brought together databases, logic, and random structures. The main aim of this seminar has been to bring together some of the foremost experts from these different fields, as well as junior researchers who may become motivated to work deeper in the frontier of logic and random structures. In addition to making tangible progress on some of the currently outstanding open problems in this area, we wanted to establish new connections between (classical) random discrete structures, flag algebras, and sparse graph limits, both in terms of identifying new research questions and embarking on new collaborations, as well as fruitful interaction between foundational research and different application areas, including probabilistic databases.

Organisation and Activities

Despite the restrictions and problems caused by corona pandemic, the seminar had originally been intended as a non-hybrid event with all participants on site. At the end, however, this turned out to be infeasible; as a result, two of the invited survey talks and a number of the contributed talks had to be given remotely via Zoom.

The organisers created a schedule consisting of four invited one-hour survey talks, and more focussed regular contributions proposed by the participants. The survey talks were given by

• Albert Atserias on certifying the chromatic number of a random graph;
• Fiona Skerman on the inference of underlying community structures in partially observed graphs;
• Dan Suciu on probabilistic databases;
• Patrice Ossona de Mendez on limits of graphs.

The talks of Fiona Skerman and Patrice Ossona de Mendez were given over Zoom.

In addition, there were 18 contributed talks, 11 of which were given on site, and 7 remotely via Zoom.

Overall, the organisers regard the seminar to have been a very successful scientific event. There was a general view shared by all participants that the community working on logic and random structures is in excellent shape, with interesting new developments and exciting results in many different directions. The participants clearly expressed the wish to a have a future meeting of this community, be in in Dagstuhl or elsewhere, within the next two to three years.

The organisers are grateful to the Scientific Directorate and to the staff of the Center for their support of this seminar.

Creative Commons BY 4.0

Erich Grädel, Phokion G. Kolaitis, and Marc Noy