https://www.dagstuhl.de/22061

February 6 – 11 , 2022, Dagstuhl Seminar 22061

Logic and Random Discrete Structures

Organizers

Erich Grädel (RWTH Aachen, DE)
Phokion G. Kolaitis (University of California – Santa Cruz, US)
Marc Noy (UPC Barcelona Tech, ES)

For support, please contact

Susanne Bach-Bernhard for administrative matters

Andreas Dolzmann for scientific matters

Documents

List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule (Upload here)

(Use personal credentials as created in DOOR to log in)

Motivation

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 Dagstuhl Seminar is 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 expect that new connections may be made between (classical) random discrete structures, flag algebras, and sparse graph limits, both in terms of identifying new research questions and embarking on new collaborations. Furthermore, we expect that there will be fruitful interaction between foundational research and different application areas, including probabilistic databases.

The seminar will feature three or four tutorials or broad overview talks on different topics, so that all participants develop a common background. In addition, there will be a few long talks and several short talks in which state-of-the-art advances will be communicated. The program will be complemented by one or two problem sessions and by a discussion assessing the seminar and planning the next steps. The schedule will provide ample time for informal interactions and collaboration between participants.

Motivation text license
  Creative Commons BY 4.0
  Erich Grädel, Phokion G. Kolaitis, and Marc Noy

Classification

  • Databases
  • Discrete Mathematics
  • Logic In Computer Science

Keywords

  • Logic
  • Model theory
  • Random Graphs
  • Combinatorics
  • Complexity theory

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.