Marc Noy. Limiting probabilities of first order sentences in sparse random graphs (invited talk)
Channel: Computational Logic and Applications
Date: 2020-10-12

15th Workshop
Computational Logic and Applications (https://cla.tcs.uj.edu.pl/)
12-13 October 2020

Speaker: Marc Noy
Title: Limiting probabilities of first order sentences in sparse random graphs (invited talk)
Abstract:
Given a class of random graphs G and a first order property A, we consider the limiting probability that A is satisfied in G when the number of vertices goes to infinity. In the classical random graph model G(n,p=c/n) in the sparse regime, we find a critical value c′∼0.93 such that the set of limiting probabilities is dense in the interval [0,1] if and only if c\gt c′

We will sketch the proof of this result and will discuss its extension to sparse hypergraphs and other models of random sparse random graphs.

(Joint work with Alberto Larrauri and Tobias Müller)