Lorentz Center

International center for scientific workshops

International center for scientific workshops

Current Workshop | Overview | Back | Home | Search | | ||||||||||

## 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. [Back] |