2021/03/18 by Andrzej Grzesik, Grzesik, Andrzej, Daniel Král͏̌ +3 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2103.10354
openalex publication_date 2021/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The notion of first order convergence of graphs unifies the notions of convergence for sparse and dense graphs. Nešetřil and Ossona de Mendez [J. Symbolic Logic 84 (2019), 452-472] proved that every first order convergent sequence of graphs from a nowhere-dense class of graphs has a modeling limit and conjectured the existence of such modeling limits with an additional property, the strong finitary mass transport principle. The existence of modeling limits satisfying the strong finitary mass transport principle was proved for first order convergent sequences of trees by Nešetřil and Ossona de Mendez [Electron. J. Combin. 23 (2016), P2.52] and for first order sequences of graphs with bounded path-width by Gajarský et al. [Random Structures Algorithms 50 (2017), 612-635]. We establish the existence of modeling limits satisfying the strong finitary mass transport principle for first order convergent sequences of graphs with bounded tree-width.