Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 20451

Logic and Random Discrete Structures Cancelled

( Nov 01 – Nov 06, 2020 )

Please use the following short url to reference this page:

Dagstuhl Seminar 22061: Logic and Random Discrete Structures (2022-02-06 - 2022-02-11) (Details)




The analysis of large random discrete structures, such as trees, graphs, or permutations, is a main research focus in contemporary discrete mathematics. The overall goal is to understand the “typical structure'' of objects from a given class by studying the behavior of a randomly chosen object from that class. Logic provides a useful and powerful formalism for classifying discrete structures and for expressing properties of discrete structures; for this reason, the lens of logic has also been used in the study of random discrete structures.

The connections between logic and random discrete structure trace their origin to the discovery of the zero-one law for first-order logic on finite structures under the uniform probability measure, a celebrated result due to Glebskii et al. and, independently, to Fagin. Since the discovery of this result five decades ago, logical limit laws or convergence laws have been established for several different models of random discrete structures and for various logics, including fragments of second-order logic and extensions of first-order logic with fixed-point constructs. Furthermore, fundamental algorithmic problems associated with the computation of asymptotic probabilities have been explored.

In recent years, connections between logic and random discrete structures have emerged in different frameworks that span a broad spectrum of areas, from extremal combinatorics to modeling uncertainty in data, and typically use distinct techniques. For example, the frameworks of graph limits and flag algebras are concerned with the study of asymptotic densities of structures, while the framework of probabilistic databases is concerned with the study of queries posed against inherently uncertain data. Logic has been successfully used in all these frameworks to provide a coherent viewpoint and to contribute to the establishment of unifying results.

The main aim of this Dagstuhl Seminar is to bring together researchers, both junior and senior, from different areas, such as logic, combinatorics, data uncertainty, and randomized algorithms, to share state-of-the-art advances in the interaction between these areas, present overviews of methods and techniques based on the combination of logic and discrete random structures, discuss open problems, and shape future directions of research in these fields.

Copyright Erich Grädel, Phokion G. Kolaitis, Tobias Müller, and Marc Noy

  • Erich Grädel (RWTH Aachen, DE) [dblp]
  • Tobias Müller (University of Groningen, NL) [dblp]
  • Marc Noy (UPC Barcelona Tech, ES) [dblp]

  • data structures / algorithms / complexity
  • verification / logic

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