Evènement pour le groupe Séminaire Méthodes Formelles

Date 2019-02-12  11:00-12:00
TitreLogic and random graphs 
RésuméWe look at properties of graphs that can be expressed in first order (FO) logic. Given such a property A and a class G of random graphs, we are interested in the limiting probability that a graph in G satisfies A, when the number of vertices goes to infinity. First we survey what is known for the classical model G(n,p), including zero-one laws and the celebrated theorem of Shelah and Spencer. Then we move to classes of graphs defined by a global condition, such as being acyclic or planar, under the uniform distribution. We survey recent results on zero-one laws, convergence laws, and non-convergence phenomena, both in FO and in the stronger monadic second order (MSO) logic. In particular, for graphs embeddable in a fixed surface other than the sphere, there is a striking difference between the results in FO and MSO logic. 
OrateurMarc Noy 
UrlUniversitat Politècnica de Catalunya 

Aucun document lié à cet événement.

Retour à l'index