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. 
Lieu178 
OrateurMarc Noy 
Emailhttps://sites.google.com/view/marcnoy//?PHPSESSID=6452921b6d9f996fdb10daebe3b5bf2f 
UrlUniversitat Politècnica de Catalunya 



Aucun document lié à cet événement.

Retour
Retour à l'index