Evènement pour le groupe Graphes et Logique

Date 2011-01-18  12:00-13:00
TitreZero-one laws, random structures, and generic first-order logic  
RésuméIn this talk I will try to explain the nature of various zero-one laws in terms of the “large scale “ or “generic” logic. One of the most famous zero-one laws is about finite graphs: for every first-order 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 zero-one 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 model-theoretic 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 zero-one 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. 
Lieusalle 76 
OrateurAlexei Miasnikov 
UrlStevens Institute - McGill University 

Aucun document lié à cet événement.

Retour à l'index