Model Theory and Combinatorics

Collection Model Theory and Combinatorics

Organisateur(s)
Date(s) 26/01/2018 - 02/02/2018
00:00:00 / 00:00:00
8 20

A sequence of graphs is FO-convergent if the probability of satisfaction of every first-order formula converges. A graph modeling is a graph, whose domain is a standard probability space, with the property that every definable set is Borel. It was known that FO-convergent sequences of graphs do not always admit a modeling limit, and it was conjectured that this is the case if the graphs in the sequence are sufficiently sparse. Precisely, two conjectures were proposed:1) If a FO-convergent sequence of graphs is residual, that is, if for every integer d the maximum relative size of a ball of radius d in the graphs of the sequence tends to zero, then the sequence has a modeling limit. 2) A monotone class of graphs C has the property that every FO-convergent sequence of graphs from C has a modeling limit if and only if C is nowhere dense, that is, if and only if for each integer p there is N(p) such that the pth subdivision of the complete graph on N(p) vertices does not belong to C. In this talk we present the proof of both conjectures. This solves some of the main problems in the area and among others provides an analytic characterization of the nowhere dense–somewhere dense dichotomy.

Informations sur la vidéo

  • Date de captation 30/01/2018
  • Date de publication 31/01/2018
  • Institut IHP
  • Format MP4

Domaine(s)

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis