Graph sequences sampled from Robinson graphons
Graph sequences sampled from Robinson graphons
复制标题
DOI：
10.1016/j.ejc.2023.103859
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
Changpishit et al.(2015) 中引入的图子空间上的函数 Γ 旨在测量图子 w 表现 Robinson 性质的程度：对于所有 x< y< z，w (x, z)≤ min {w (x, y), w (y, z)}。罗宾逊图元形成了具有自然线嵌入的图模型，因此大多数边缘都是局部的。函数 Γ 与割范数 ‖⋅‖□ 兼容，从某种意义上说，割范数接近的图元具有相似的 Γ 值。特别是，任何与所有 Robinson 图子集割范数接近的图子都具有较小的 Γ 值。在这里，我们通过证明每个图元 w 都可以用罗宾逊图元 R w 来近似，使得 ‖ w− R w ‖□ 以 Γ (w) 为界，从而证明相反的情况。然后，我们使用泛函分析中的经典技术来证明，当且仅当 Γ (G n)→ 0 时，收敛图序列 {G n} 会收敛到罗宾逊图子。最后，使用概率技术，我们表明从罗宾逊图子采样的图序列 Γ 的收敛速度可能会存在很大差异，具体取决于 w 表现出罗宾逊性质的强度。
The function Γ on the space of graphons, introduced in Chuangpishit et al.(2015), aims to measure the extent to which a graphon w exhibits the Robinson property: for all x< y< z, w (x, z)≤ min {w (x, y), w (y, z)}. Robinson graphons form a model for graphs with a natural line embedding so that most edges are local. The function Γ is compatible with the cut-norm‖⋅‖□, in the sense that graphons close in cut-norm have similar Γ-values. In particular, any graphon close in cut-norm to the set of all Robinson graphons has small Γ-values. Here we show the converse, by proving that every graphon w can be approximated by a Robinson graphon R w so that‖ w− R w‖□ is bounded in terms of Γ (w). We then use classical techniques from functional analysis to show that a converging graph sequence {G n} converges to a Robinson graphon if and only if Γ (G n)→ 0. Finally, using probabilistic techniques we show that the rate of convergence of Γ for graph sequences sampled from a Robinson graphon can differ substantially depending on how strongly w exhibits the Robinson property.