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

Igor Dolinka; Robert Duncan Gray; Jillian Dawn McPhee; James David Mitchell; Martyn Quick

doi:10.1017/S030500411500078X

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

Igor Dolinka, Robert Duncan Gray, Jillian Dawn McPhee, James David Mitchell, Martyn Quick

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	437-462
Number of pages	26
Journal	Mathematical Proceedings of the Cambridge Philosophical Society
Volume	160
Issue number	3
Early online date	21 Jan 2016
DOIs	https://doi.org/10.1017/S030500411500078X
Publication status	Published - May 2016

Keywords

Existentially closed graphs
Algebraically closed graphs
Random graph
Endomorphism monoid
Countable universal graph
Countable universal bipartite graph

Access to Document

10.1017/S030500411500078X

Automorphism groups of countable algebraically closed graphs and endomorphisms of the random graph
© 2016, Publisher / the Author(s). This work is made available online in accordance with the publisher’s policies. This is the author created, accepted version manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at journals.cambridge.org / https://dx.doi.org/10.1017/S030500411500078X
Accepted author manuscript, 318 KB

http://arxiv.org/abs/1408.4107

Handle.net

Persistent link

Cite this

@article{016f9aa6521d486e923b577c66302168,

title = "Automorphism groups of countable algebraically closed graphs and endomorphisms of the random graph",

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{\"u}tzenberger group. Similar results are proved for the countable universal directed graph and the countable universal bipartite graph.",

keywords = "Existentially closed graphs, Algebraically closed graphs, Random graph, Endomorphism monoid, Countable universal graph, Countable universal bipartite graph",

author = "Igor Dolinka and Gray, \{Robert Duncan\} and McPhee, \{Jillian Dawn\} and Mitchell, \{James David\} and Martyn Quick",

year = "2016",

month = may,

doi = "10.1017/S030500411500078X",

language = "English",

volume = "160",

pages = "437--462",

journal = "Mathematical Proceedings of the Cambridge Philosophical Society",

issn = "0305-0041",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

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

AU - Dolinka, Igor

AU - Gray, Robert Duncan

AU - McPhee, Jillian Dawn

AU - Mitchell, James David

AU - Quick, Martyn

PY - 2016/5

Y1 - 2016/5

N2 - 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.

AB - 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.

KW - Existentially closed graphs

KW - Algebraically closed graphs

KW - Random graph

KW - Endomorphism monoid

KW - Countable universal graph

KW - Countable universal bipartite graph

UR - https://www.scopus.com/pages/publications/84955253873

U2 - 10.1017/S030500411500078X

DO - 10.1017/S030500411500078X

M3 - Article

SN - 0305-0041

VL - 160

SP - 437

EP - 462

JO - Mathematical Proceedings of the Cambridge Philosophical Society

JF - Mathematical Proceedings of the Cambridge Philosophical Society

IS - 3

ER -

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

Abstract

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Automata Languages Decidability: Automata, Languages, Decidability in Algebra

Finiteness Conditions and Index: Finiteness Conditions and Index in Semigroups and Monoids

Martyn Quick

Cite this

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

Abstract

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Projects

Automata Languages Decidability: Automata, Languages, Decidability in Algebra

Finiteness Conditions and Index: Finiteness Conditions and Index in Semigroups and Monoids

Profiles

Martyn Quick

Cite this