
Evènement pour le groupe Graphes et Logique
Date  20110118 12:0013:00 
Titre  Zeroone laws, random structures, and generic firstorder logic 
Résumé  In this talk I will try to explain the nature of various zeroone laws in terms of the “large scale “ or “generic” logic.
One of the most famous zeroone laws is about finite graphs: for every firstorder sentence of graph theory either this sentence or its negation holds almost surely on all finite graphs. The large scale first order logic is an “asymptotic” version of the classical first order logic, where the notion of truth is more relaxed, so in this case a first order sentence holds in a given structure A if it holds “almost surely” in A. It turns out that the zeroone law above means precisely that the large scale first order theory of the complete graph C on countably many vertices (the universe of all the finite graphs!) is complete in the classical modeltheoretic meaning. Furthermore, this large scale theory is precisely the standard first order theory of the random subgraphs of C, which are the famous Rado, or Erdos graphs. Here one can see exactly what are the formulas that hold almost surely on all finite graphs.
I will show that similar zeroone laws hold for Cayley graphs of arbitrary finitely generated groups and describe their large scale theories. Surprisingly, these theories are closely related to percolation on groups.
Large scale theories of groups itself (not their Cayley graphs) are much more mysterious. However, recent progress on Tarski problems allows one to describe large scale theories of arbitrary hyperbolic groups  in the large scale logic they look precisely like free groups. 
Lieu  salle 76 
Orateur  Alexei Miasnikov 
Email  amiasnikov@gmail.com 
Url  Stevens Institute  McGill University 
Aucun document lié à cet événement. RetourRetour à l'index
 