Reducts of the random graph
Reducts of the random graph
复制标题
随机图的约简
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
S. Thomas
中科院分区：
文献类型：
--
作者：
S. Thomas
设Γ是具有如下性质的唯一(直到同构)可数图：(*)给定Γ的任意两个有限不交子集U和V，存在一个连接到U中的每个顶点而不连接到V中的任何顶点的顶点z∈Γ。因此，Γ是可数的、泛的、齐次的图，也称为随机图。本文研究Γ的约化，这里定义Γ的一个约化是一个置换群(G，Γ)，使得：(I)Aut(Γ)≤G；和(Ii)G是Sym(Γ)的闭子群。等价地，对于某些语言L，存在这样的结构：(Iii)有宇宙Γ；(Iv)对于每个R∈，L在Γ中是不带参数的可定义的；以及(V)G=aut()。
Let Γ be the unique (up to isomorphism) countable graph with the following property: (*) Given any two finite disjoint subsets U and V of Γ, there exists a vertex z ∈ Γ joined to every vertex in U and to none in V. Thus Γ is the countable, universal, homogeneous graph; also known as the random graph. In this paper, we shall study the reducts of Γ Here a reduct of Γ is defined to be a permutation group (G, Γ) such that: (i) Aut(Γ) ≤ G; and (ii) G is a closed subgroup of Sym(Γ). Equivalently, there exists a structure for some language L such that: (iii) has universe Γ; (iv) for each R ∈ L, is definable without parameters in Γ; and (v) G = Aut().