Extending partial isomorphisms of graphs |
| |
Authors: | Ehud Hrushovski |
| |
Affiliation: | (1) Department of Mathematics, M.I.T., 02139 Cambridge, MA, U.S.A. |
| |
Abstract: | Theorem Let 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.Work supported by a Sloan Fellowship and by NSF grant DMS-8903378. |
| |
Keywords: | 05 C 25 |
本文献已被 SpringerLink 等数据库收录! |
|