Abstract
We construct uncountable graphs in which any two isomorphic subgraphs of size at most 3 can be carried one to the other by an automorphism of the graph, but in which some isomorphism between 2-element subsets does not extend to an automorphism. The corresponding phenomenon does not occur in the countable case. The construction uses a suitable construction of infinite homogeneous coloured chains.
Similar content being viewed by others
References
Droste, M. (1986) Complete embeddings of linear orderings and embeddings of lattice ordered groups, Israel J. Math. 56, 315–334.
Droste, M. and Macpherson, H. D. (1991) On k-homogeneous posets and graphs, J. Comb. Theory Ser. A 56, 1–15.
Droste, M. and Shelah, S. (1985) A construction of all normal subgroup lattices of 2-transitive automorphism groups of linearly ordered sets, Israel J. Math. 51, 223–261.
Droste, M., Giraudet, M. and Macpherson, H. D. (1995) Periodic ordered permutation groups and cyclic orderings, J. Comb. Theory Ser. B 63, 310–321.
Droste, M., Giraudet, M., Macpherson, H. D. and Sauer, N. (1994) Set-homogeneous graphs, J. Comb. Theory Ser. B 62, 63–95.
Fraïsse, R. (1986) Theory of Relations, North-Holland, Amsterdam.
Mekler, A. H. (1993) Homogeneous partially ordered sets, in N. W. Sauer, R. E. Woodrow and B. Sands (eds), Finite and Infinite Combinatorics in Sets and Logic, Proceedings NATO ASI conference in Banff 1991, Kluwer, Dordrecht, pp. 279–288
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Droste, M., Giraudet, M. & Macpherson, D. Set-Homogeneous Graphs and Embeddings of Total Orders. Order 14, 9–20 (1997). https://doi.org/10.1023/A:1005880810385
Issue Date:
DOI: https://doi.org/10.1023/A:1005880810385