Logic and Random Graphs

Random graphs are mathematical models of networks that have been studied intensively for over half a century, beginning with the seminal work of Erdős and Rényi. Random graphs are often used to test algorithms and to simulate and predict the behavior of dynamic networks. Partly because of their relevance to phenomena such as the internet, social and biological networks, research activity on random graphs has increased tremendously over the last decade. More recently, the study of very large (not-necessarily-random) networks has led to the introduction of graph limits. This very exciting research frontier is closely related to random graphs and still in a state of rapid development.

Naturally, properties of graphs that can be expressed in formal logic have long played a central role within both theoretical computer science and graph theory. They are for instance relevant to databases, software verification, and property testing. On the more theoretical side, they are intimately linked to the study of algorithms, complexity and structural graph theory. A fundamental theorem due to Fagin (1974) for instance shows that the complexity class NP coincides exactly with the collection of algorithmic decision problems that can be expressed as a sentence in existential second-order (ESO) logic, and graph minor theory can be rephrased in the language of monadic second-order (MSO) logic.

Given the central position of logic within graph theory, it comes as no surprise that researchers have studied random graphs from a logical perspective for nearly as long as random graph theory has existed. The first work in this direction is due to Glebskii et al. (1969) and, independently, Fagin (1976). Their striking result states that if we pick a graph uniformly at random from all graphs on n vertices, then there is a zero-one law for first-order (FO) logic. This means that for any graph property that can be expressed as a sentence in first-order logic, the probability that it holds either tends to one or to zero (as n tends to infinity).

Since then, the existence (or not) of such zero-one laws has been established for many different models of random graphs and various logics. The subject also has surprising connections to other, seemingly far-removed branches of mathematics, such as number theory and topology.

Despite its established role within random graph theory, there is a strong, renewed impetus for research activity on random graphs from a logical perspective. This is partly because recent advances in our understanding of various random graph models, including random graphs with a given degree distribution and random graphs embeddable on surfaces, make it possible to attack questions that were out of reach until very recently.

Another reason for the renewed impetus is related to graph limits.

After the introduction of graph limits around 2006, many in the field realized that there is a connection between graph limits and some of the phenomena and in particular the limit objects produced in the theory of logical limit laws of random graphs. A recent sequence of preprints by Ossona de Mendez and Nesetril created an explicit link between graph limits and first-order logic. Logic moreover plays an integral role in the recent flag algebras framework, which not only has had a deep impact on extremal combinatorics, but also provides a natural viewpoint on graph limits.

The main goals of the workshop are to facilitate the exchange of techniques, questions and ideas that will lead to a better understanding of random graphs and graph limits from a logical perspective; and to form new (international) collaborations for the exploration of this exciting research frontier.