Geodesic
Modeling limits in hereditary classes: reduction and application to trees
Jaroslav Nešetřil1 ; Patrice Ossona de Mendez2
1Univerzita Karlova v Praze
2Centre National de la Recherche Scientifique - and - Univerzita Karlova v Praze
The electronic journal of combinatorics, Tome 23 (2016) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The study of limits of graphs led to elegant limit structures for sparse and dense graphs. This has been unified and generalized by the authors in a more general setting combining analytic tools and model theory to ${\rm FO}$-limits (and $X$-limits) and to the notion of modeling. The existence of modeling limits was established for sequences in a bounded degree class and, in addition, to the case of classes of trees with bounded height and of graphs with bounded tree depth. The natural obstacle for the existence of modeling limit for a monotone class of graphs is the nowhere dense property and it has been conjectured that this is a sufficient condition. Extending earlier results here we derive several general results which present a realistic approach to this conjecture. As an example we then prove that the class of all finite trees admits modeling limits.
DOI : 10.37236/5628
Classification : 05C12, 05C42, 03C13, 03C98
Mots-clés : relational structure, graph limits, structural limits, Radon measures, Stone space, model theory, first-order logic, measurable graph

Jaroslav Nešetřil  1   ; Patrice Ossona de Mendez  2

1 Univerzita Karlova v Praze
2 Centre National de la Recherche Scientifique - and - Univerzita Karlova v Praze 
@article{10_37236_5628,
     author = {Jaroslav Ne\v{s}et\v{r}il and Patrice Ossona de Mendez},
     title = {Modeling limits in hereditary classes: reduction and application to trees},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {2},
     doi = {10.37236/5628},
     zbl = {1339.05096},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5628/}
}
TY  - JOUR
AU  - Jaroslav Nešetřil
AU  - Patrice Ossona de Mendez
TI  - Modeling limits in hereditary classes: reduction and application to trees
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5628/
DO  - 10.37236/5628
ID  - 10_37236_5628
ER  - 
%0 Journal Article
%A Jaroslav Nešetřil
%A Patrice Ossona de Mendez
%T Modeling limits in hereditary classes: reduction and application to trees
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5628/
%R 10.37236/5628
%F 10_37236_5628
Jaroslav Nešetřil; Patrice Ossona de Mendez. Modeling limits in hereditary classes: reduction and application to trees. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/5628

Cité par Sources :