Reducts of the generic digraph

DOI10.1016/J.APAL.2015.12.006MaRDI QIDQ904153zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Lovkush Agarwal

Publication date 12 January 2016

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.4820

zbMATH Keywords

digraphpermutation grouphomogeneous structurecanonical functionreductclosed group

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Group actions on combinatorial structures (05E18) Maximal subgroups (20E28) Interpolation, preservation, definability (03C40) Infinite automorphism groups (20B27)

Abstract: The generic digraph $(D,E)$ is the unique countable homogeneous digraph that embeds all finite digraphs. In this paper, we determine the lattice of reducts of $(D,E)$, where a structure $mathcalM$ is a reduct of $(D,E)$ if it has domain $D$ and all its $emptyset$-definable relations are $emptyset$-definable relations of $(D,E)$. As $(D,E)$ is $alep{h}_0$-categorical, this is equivalent to determining the lattice of closed groups that lie in between Aut$(D,E)$ and Sym$(D)$.

Recommendations

• Reducts of the random graph
• Reducts of random hypergraphs
• Reducts of the random bipartite graph
• \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
• The 42 reducts of the random ordered graph

Cites work

• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 3080680 (Why is no real title available?)
• Decidability of definability
• Partitions of finite relational and set systems
• Reducts of Ramsey structures
• Reducts of random hypergraphs
• Reducts of the random graph
• Reducts of the random partial order
• The 116 reducts of (ℚ, <, a)
• The 42 reducts of the random ordered graph
• Transitivity of permutation groups on unordered sets

Cited in

(8)

• Two Fraïssé-style theorems for homomorphism-homogeneous relational structures
• The reducts of the homogeneous binary branching \(C\)-relation
• \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
• Permutation groups with small orbit growth
• Permutation monoids and MB-homogeneity for graphs and relational structures
• Reducts of the random bipartite graph
• scientific article; zbMATH DE number 7406819 (Why is no real title available?)
• Construction of a transitive reduction of an acyclic digraph

This page was built for publication: Reducts of the generic digraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q904153)