Extending partial isomorphisms of graphs
Extending partial isomorphisms of graphs
复制标题
扩展图的部分同构
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
E. Hrushovski
中科院分区：
文献类型：
--
作者：
E. Hrushovski
定理设X是有限图。则存在一个有限图Z，它包含X作为一个导出子图，使得X的导出子图之间的每一个同构都扩张为Z的一个自同构.结果表明，对任意n，存在Rado图R（随机可数图）的"一般自同构元组"的概念：对几乎所有的自同构σ 1，…，R（在Baire范畴意义下）的σ n和τ 1，（R，σ 1，…，σ n），τ n（R，τ 1，.，τ n）。这个问题出现在Hodges，Hodgkinson，Lascar和Shelah最近的一篇论文中，其中定理被用来证明R的小指数性质。
TheoremLet X be a finite graph. Then there exists a finite graph Z containing X as an induced subgraphs, such that every isomorphism between induced subgraphs of X extends to an automorphism of Z.The graphZ may be required to be edge-transitive. The result implies that for anyn, there exists a notion of a “genericn-tuple of automorphism” of the Rado graphR (the random countable graph): for almost all automorphism σ1,..., σn and τ1 ofR (in the sense of Baire category), (R,σ1,...,σn), ≅ (R,τ1,...,τn). The problem arose in a recent paper of Hodges, Hodgkinson, Lascar and Shelah, where the theorem is used to prove the small index property forR.