论文标题
小工具的结构和结构融合
Gadget construction and structural convergence
论文作者
论文摘要
Nešet松和Ossona de Mendez最近提出了一种新的图形收敛定义，称为结构收敛。结构收敛框架是基于从一阶公式固定片段中满足逻辑公式的可能性。选择片段的灵活性允许统一稀疏和致密图的经典融合概念。由于该场相对年轻，因此收敛序列的示例范围是有限的，只有几种构造方法。我们的目的是通过考虑小工具结构来扩展各种结构。我们表明，在限制句子集时，小工具在基本收敛序列上的应用会产生基本收敛的序列。另一方面，我们展示了反例，目睹了对完整一阶收敛的概括，如果没有其他假设。我们提供几种不同的条件，以确保完整的融合。其中之一指出，如果替换的边缘在结构的原始序列中密集，则结果序列是一阶收敛。
Nešetř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 is to extend the variety of constructions by considering the gadget construction. We show that, when restricting to the set of sentences, the application of gadget construction on elementarily convergent sequences yields an elementarily convergent sequence. On the other hand, we show counterexamples witnessing that a generalization to the full first-order convergence is not possible without additional assumptions. We give several different sufficient conditions to ensure the full 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.
