×

Reducts of the generic digraph. (English) Zbl 1329.05305

Summary: 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 \(\mathcal{M}\) is a reduct of \((D, E)\) if it has domain \(D\) and all its \(\varnothing\)-definable relations are \(\varnothing\)-definable relations of \((D, E)\). As \((D, E)\) is \(\aleph_0\)-categorical, this is equivalent to determining the lattice of closed groups that lie in between \(\operatorname{Aut}(D, E)\) and \(\operatorname{Sym}(D)\).

MSC:

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

References:

[1] Bennett, J., The reducts of some infinite homogeneous graphs and tournaments (1997), Rutgers University, Ph.D. thesis
[2] Bodirsky, M.; Pinsker, M., Reducts of Ramsey structures, (Grohe, M.; Makowsky, J., Model Theoretic Methods in Finite Combinatorics. Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics, vol. 558 (2011), American Mathematical Society), 489-519 · Zbl 1261.03118
[3] Bodirsky, M.; Pinsker, M.; Pongrácz, A., The 42 reducts of the random ordered graph, Proc. Lond. Math. Soc. (3), 111, 3, 591-632 (2015) · Zbl 1382.03057
[4] Bodirsky, M.; Pinsker, M.; Tsankov, T., Decidability of definability, J. Symbolic Logic, 78, 1036-1054 (2013) · Zbl 1327.03008
[5] Cameron, P., Transitivity of permutation groups on unordered sets, Math. Z., 148, 127-139 (1976) · Zbl 0313.20022
[6] Fraïssé, R., Sur certaines relations généralisent l’ordre des nombres rationnels, C. R. Acad. Sci. Paris, 237, 540-542 (1953) · Zbl 0051.03803
[7] Hodges, W., A Shorter Model Theory (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0873.03036
[8] Junker, M.; Ziegler, M., The 116 reducts of \((Q, <, 0)\), J. Symbolic Logic, 74, 861-884 (2008) · Zbl 1189.03041
[9] Kaplan, I.; Simon, P., The affine and projective groups are maximal, Trans. Amer. Math. Soc. (2015), in press
[10] Nešetřil, J.; Rödl, V., Partitions of relational and set systems, J. Combin. Theory Ser. A, 22, 289-312 (1977) · Zbl 0361.05017
[11] Pach, P.; Pinsker, M.; Pluhár, G.; Pongrácz, A.; Szabó, C., Reducts of the random partial order, Adv. Math., 267, 94-120 (2014) · Zbl 1403.03053
[12] Thomas, S., Reducts of the random graph, J. Symbolic Logic, 56, 176-181 (1991) · Zbl 0743.05049
[13] Thomas, S., Reducts of random hypergraphs, Ann. Pure Appl. Logic, 80, 165-193 (1996) · Zbl 0865.03025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.