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.

Creative Commons BY 3.0 DE

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