Modeling Limits in Hereditary Classes: Reduction and Application to Trees

Limits of graphs were initiated recently in the two extreme contexts of dense and bounded degree graphs. This led to elegant limiting structures called graphons and graphings. These approach have been unified and generalized by authors in a more general setting using a combination of analytic tools and model theory to 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. These seemingly very special classes is in fact a key step in the development of limits for more general situations. 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 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.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00912153
Author Nesetril, Jaroslav, Ossona de Mendez, Patrice
Maintainer CCSD
Last Updated May 8, 2026, 00:24 (UTC)
Created May 8, 2026, 00:24 (UTC)
Identifier hal-00912153
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Computer Science Institute of Charles University [Prague] (IUUK) ; Univerzita Karlova [Praha, Česká republika] = Charles University [Prague, Czech Republic] = Université Charles [Prague, Republique tchèque] (UK)
creator Nesetril, Jaroslav
date 2013-12-01T00:00:00
harvest_object_id b09137f4-5db1-43b7-9700-e92764a58ccf
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-03-12T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1312.0441
set_spec type:UNDEFINED