First order limits of sparse graphs: Plane trees and path-width
First order limits of sparse graphs: Plane trees and path-width
复制标题
稀疏图的一阶极限：平面树和路径宽度
DOI：
10.1002/rsa.20676
复制
发表时间：
2017
影响因子：
1
通讯作者：
Gajarský J
中科院分区：
文献类型：
--
作者：
Gajarský J
Nešetřil 和 Ossona de Mendez 引入了一阶收敛的概念，试图统一稀疏图和稠密图的收敛概念。已知存在无极限建模（极限的解析表示）的图的一阶收敛序列。从积极的一面来看，没有长路径的树或图的每个一阶收敛序列（具有有界树深度的图）都具有极限建模。我们通过证明平面树的每个一阶收敛序列（在平面中嵌入的树）和具有有界路径宽度的图的每个一阶收敛序列都具有极限建模来强化这些结果。 © 2016 Wiley periodicals, Inc. 随机结构。阿尔格., 50, 612–635, 2017
Nešetřil and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree‐depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path‐width has a limit modeling. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 612–635, 2017