Model Theory and Combinatorics

Collection Model Theory and Combinatorics

Organizer(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.

Information about the video

  • Date of recording 30/01/2018
  • Date of publication 31/01/2018
  • Institution IHP
  • Format MP4

Domain(s)

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback