Ne\v{s}et\v{r}il and Ossona de Mendez recently proposed a new definition of graph convergence called structural convergence. The structural convergence framework is based on the probability of satisfaction of logical formulas from a fixed fragment of first-order formulas. The flexibility of choosing the fragment allows to unify the classical notions of convergence for sparse and dense graphs. Since the field is relatively young, the range of examples of convergent sequences is limited and only a few methods of construction are known. Our aim to extend the variety of constructions by considering the gadget construction that appears, e.g., in studies of homomorphisms. We show that, when restricting to the set of sentences, the application of gadget construction on an elementarily convergent sequence and elementarily convergent gadgets results in an elementarily convergent sequence. For the general case, we show counterexamples witnessing that a generalization to the full first-order convergence is not possible without additional assumptions. Moreover, we give several different sufficient conditions to ensure the convergence, one of them states that the resulting sequence is first-order convergent if the replaced edges are dense in the original sequence of structures.
翻译:Nev{s} et\ v{r}il 和 Ossona de Mendez 最近提出了一个称为结构趋同的图形趋同的新定义。 结构趋同框架基于从一阶公式固定的碎片中逻辑公式的满足概率。 选择碎片的灵活性可以统一稀薄和稠密的图形的经典趋同概念。 由于字段相对年轻, 趋同序列的示例范围有限, 并且只有几种构建方法为人所知。 我们的目的是扩大各种构造, 考虑显示的组合结构, 例如对同质式学的研究。 我们表明, 当限制句子组时, 将组合构件在元素趋同序列和元素趋同组合组合组中应用为元素趋同序列。 对于一般案例, 我们展示了相反的示例, 证明如果没有额外的假设, 就不可能将第一级趋同完全趋同。 此外, 我们给出了几个不同的充分的条件来确保趋同性, 其中一个条件是, 如果被取代的边缘的原始结构是密度, 则导致的顺序是第一级趋同。