Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-28T14:17:39.478Z Has data issue: false hasContentIssue false
  • English
  • Français

Automorphism groups of countable algebraically closed graphs and endomorphisms of the random graph

Published online by Cambridge University Press:  21 January 2016

IGOR DOLINKA ,
ROBERT D. GRAY ,
JILLIAN D. McPHEE ,
JAMES D. MITCHELL  and
MARTYN QUICK
IGOR DOLINKA
Affiliation:
Department of Mathematics and Informatics, University of Novi Sad, Trg Dositeja Obradovića 4, 21101 Novi Sad, Serbia. e-mail: [email protected]
ROBERT D. GRAY
Affiliation:
School of Mathematics, University of East Anglia, Norwich NR4 7TJ. e-mail: [email protected]
JILLIAN D. McPHEE
Affiliation:
School of Mathematics & Statistics, University of St Andrews, St Andrews, Fife KY16 9SS, Scotland. e-mail: [email protected]; [email protected]; [email protected]
JAMES D. MITCHELL
Affiliation:
School of Mathematics & Statistics, University of St Andrews, St Andrews, Fife KY16 9SS, Scotland. e-mail: [email protected]; [email protected]; [email protected]
MARTYN QUICK
Affiliation:
School of Mathematics & Statistics, University of St Andrews, St Andrews, Fife KY16 9SS, Scotland. e-mail: [email protected]; [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We establish links between countable algebraically closed graphs and the endomorphisms of the countable universal graph R. As a consequence we show that, for any countable graph Γ, there are uncountably many maximal subgroups of the endomorphism monoid of R isomorphic to the automorphism group of Γ. Further structural information about End R is established including that Aut Γ arises in uncountably many ways as a Schützenberger group. Similar results are proved for the countable universal directed graph and the countable universal bipartite graph.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 160 , Issue 3 , May 2016 , pp. 437 - 462
Copyright
Copyright © Cambridge Philosophical Society 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bonato, A. and Delić, D.The monoid of the random graph. Semigroup Forum 61 (2000), 138–148.Google Scholar
[2]Cameron, P. J.The random graph. The Mathematics of Paul Erdős, II. Algorithms Combin. 14 (Springer-Verlag, Berlin, 1997), 333–351.Google Scholar
[3]Cameron, P. J. and Nešetřil, J.Homomorphism-homogeneous relational structures. Combin. Probab. Comput. 15 (2006), 91–103.CrossRefGoogle Scholar
[4]Clifford, A. H. and Preston, G. B.The Algebraic Theory of Semigroups, Vol. I. Math. Surveys No. 7 (Amer. Math. Soc., Providence, RI, 1961).Google Scholar
[5]Dolinka, I.A characterization of retracts in certain Fraïssé limits. Math. Log. Quart. 58 (2012), 46–54.Google Scholar
[6]Dolinka, I.The Bergman property for endomorphism monoids of some Fraïssé limits. Forum Math. 26 (2014), 357–376.Google Scholar
[7]de Groot, J.Groups represented by homeomorphism groups. Math. Annalen 138 (1959), 80–120.Google Scholar
[8]Evans, D. M.Examples of ℵ0-categorical structures. Automorphisms of first-order structures. Oxford Sci. Publ. (Oxford Univ. Press, New York, 1994), 33–72.Google Scholar
[9]Fraïssé, R.Sur certaines relations qui généralisent l'ordre des nombres rationnels. C. R. Acad. Sci. Paris 237 (1953), 540–542.Google Scholar
[10]Frucht, R.Herstellung von Graphen mit vorgegebener abstrakter Gruppe. Compositio Math. 6 (1939), 239–250.Google Scholar
[11]Goldstern, M., Grossberg, R. and Kojman, M.Infinite homogeneous bipartite graphs with unequal sides. Discrete Math. 149 (1996), 69–82.Google Scholar
[12]Hodges, W.A Shorter Model Theory. (Cambridge University Press, Cambridge, 1997).Google Scholar
[13]Howie, J. M.Fundamentals of Semigroup Theory. London Math. Soc. Monographs New Ser. 12 (Oxford University Press, Oxford, 1995).Google Scholar
[14]Lockett, D. C. and Truss, J. K.Generic endomorphisms of homogeneous structures. Groups and model theory. Contemp. Math. 576 (Amer. Math. Soc., Providence, RI, 2012), 217–237.Google Scholar
[15]Macpherson, H. D. and Tent, K.Simplicity of some automorphism groups. J. Algebra 342 (2011), 40–52.Google Scholar
[16]Magill, K. D. Jr., and Subbiah, S.Green's relations for regular elements of semigroups of endomorphisms. Canad. J. Math. 26 (1974), 1484–1497.Google Scholar
[17]McPhee, J. D.Endomorphisms of Fraïssé Limits and Automorphism Groups of Algebraically Closed Relational Structures. PhD thesis, University of St Andrews, 2012.Google Scholar
[18]Rhodes, J. and Steinberg, B.The q-Theory of Finite Semigroups. Springer Monographs Math. (Springer, New York, 2009).Google Scholar
[19]Sabidussi, G.Graphs with given infinite group. Monat. Math. 64 (1960), 64–67.Google Scholar
[20]Truss, J. K.The group of the countable universal graph. Math. Proc. Cambridge Philos. Soc. 98 (1985), 213–245.Google Scholar