Minimal functions on the random graph
Minimal functions on the random graph
复制标题
随机图上的最小函数
DOI：
--
复制
发表时间：
2010
影响因子：
1
通讯作者：
M. Pinsker
中科院分区：
文献类型：
--
作者：
M. Bodirsky;M. Pinsker
我们证明，在随机图上存在一个由 14 个非难有限函数组成的系统，该系统具有以下性质：随机图上的任何非三维函数都会通过自动构成和拓扑闭包生成该系统的一个函数，而且该系统是最小的，即该系统的任何子集都不具有相同的性质。该定理是通过证明随机图有限幂中图元着色的拉姆齐型定理，并应用该定理找到随机图上任何函数行为的规律模式而得到的。作为我们方法的模型理论推论，我们重新得到了西蒙-托马斯（Simon Thomas）对随机图的一阶封闭归纳进行分类的定理，并证明了该定理的一些细化；我们还得到了在原始正定义下封闭的最大归纳的分类，并证明了随机图的所有归纳都是模型完备的。
We show that there is a system of 14 non-trivial finitary functions on the random graph with the following properties: Any non-trivial function on the random graph generates one of the functions of this system by means of composition with automorphisms and by topological closure, and the system is minimal in the sense that no subset of the system has the same property. The theorem is obtained by proving a Ramsey-type theorem for colorings of tuples in finite powers of the random graph, and by applying this to find regular patterns in the behavior of any function on the random graph. As model-theoretic corollaries of our methods we rederive a theorem of Simon Thomas classifying the first-order closed reducts of the random graph, and prove some refinements of this theorem; also, we obtain a classification of the maximal reducts closed under primitive positive definitions, and prove that all reducts of the random graph are model-complete.