FO limits of trees

26 November 2013
14:30
Abstract
Nesetril and Ossona de Mendez introduced a new notion of convergence of graphs called FO convergence. This notion can be viewed as a unified notion of convergence of dense and sparse graphs. In particular, every FO convergent sequence of graphs is convergent in the sense of left convergence of dense graphs as studied by Borgs, Chayes, Lovasz, Sos, Szegedy, Vesztergombi and others, and every FO convergent sequence of graphs with bounded maximum degree is convergent in the Benjamini-Schramm sense. FO convergent sequences of graphs can be associated with a limit object called modeling. Nesetril and Ossona de Mendez showed that every FO convergent sequence of trees with bounded depth has a modeling. We extend this result to all FO convergent sequences of trees and discuss possibilities for further extensions. The talk is based on a joint work with Martin Kupec and Vojtech Tuma.
  • Combinatorial Theory Seminar