https://www.dagstuhl.de/22061

06. – 11. Februar 2022, Dagstuhl-Seminar 22061

Logic and Random Discrete Structures

Organisatoren

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

Auskunft zu diesem Dagstuhl-Seminar erteilen

Susanne Bach-Bernhard zu administrativen Fragen

Andreas Dolzmann zu wissenschaftlichen Fragen

Dokumente

Teilnehmerliste
Gemeinsame Dokumente
Programm des Dagstuhl-Seminars [pdf]

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

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.