Self-embedding monoids and the existential Thomas conjecture

Primarily human-written textHuman understanding: all partsmath.LO — Logicmath.GR — Group Theory

Contributed by Dr. András Pongrácz ↗

Version 1 / Nov 15, 2026 / CC BY 4.0

Abstract

We give a countable homogeneous finitely bounded Ramsey structure in a finite relational language with finitely many reducts up to first-order interdefinability but infinitely many self-embedding monoids of reducts. The reducts producing these monoids are first-order interdefinable, while their monoids form a strictly increasing chain. This refutes the existential strengthening of Thomas' conjecture even under the Ramsey hypothesis. The example is an ordered expansion of an equivalence-relation structure. Before the order is added, that structure has exactly five reducts up to first-order interdefinability. We also give a revised proof of the classification of self-embedding monoids for reducts of the countable existentially closed binary branching semilinear order. Exactly five monoids occur, refining its three-class first-order classification. The proof transfers the known classification for the homogeneous binary branching CC-relation from antichains to arbitrary finite configurations. The additional step is a connectivity argument on finite labelled trees, using both preservation and reflection of the reduct's basic relations.

Tools used

OpenAI
ChatGPTVersion GPT-6 Astra

References

  1. S. A. Adeleke and D. Macpherson, Classification of infinite primitive Jordan permutation groups , Proc. London Math. Soc. (3) 72 (1996), no. 1, 63--123. doi:10.1112/plms/s3-72.1.63 (https://doi.org/10.1112/plms/s3-72.1.63).DOI
  2. S. A. Adeleke and P. M. Neumann, Relations related to betweenness: their structure and automorphisms , Mem. Amer. Math. Soc. 131 (1998), no. 623, viii+125 pp. doi:10.1090/memo/0623 (https://doi.org/10.1090/memo/0623).DOI
  3. L. Agarwal, Reducts of the generic digraph , Ann. Pure Appl. Logic 167 (2016), 370--391. doi:10.1016/j.apal.2015.12.006 (https://doi.org/10.1016/j.apal.2015.12.006).DOI
  4. L. Agarwal and M. Kompatscher, 2ℵ02^{\aleph_0} pairwise nonisomorphic maximal-closed subgroups of \(\Sym(\mathbb N)\) via the classification of the reducts of the Henson digraphs , J. Symbolic Logic 83 (2018), no. 2, 395--415. doi:10.1017/jsl.2017.74 (https://doi.org/10.1017/jsl.2017.74).DOI
  5. M. Bodirsky, Cores of countably categorical structures , Log. Methods Comput. Sci. 3 (2007), no. 1, Article 2, 1--16. doi:10.2168/LMCS-3(1:2)2007 (https://doi.org/10.2168/LMCS-3(1:2)2007).DOI
  6. M. Bodirsky, Complexity of Infinite-Domain Constraint Satisfaction , Lecture Notes in Logic 52 , Cambridge University Press, 2021. doi:10.1017/9781107337534 (https://doi.org/10.1017/9781107337534).DOI
  7. M. Bodirsky, D. Bradley-Williams, M. Pinsker and A. Pongrácz, The universal homogeneous binary tree , preprint, 7 September 2014, Corollary 3.3. arXiv:1409.2170v1 (https://arxiv.org/abs/1409.2170v1). The cited completion argument is in this early version, rather than the journal version BBWP18 .arXiv
  8. M. Bodirsky, D. Bradley-Williams, M. Pinsker and A. Pongrácz, The universal homogeneous binary tree , J. Logic Comput. 28 (2018), 133--163. doi:10.1093/logcom/exx043 (https://doi.org/10.1093/logcom/exx043). Preprint: arXiv:1409.2170 (https://arxiv.org/abs/1409.2170).arXivDOI
  9. M. Bodirsky, P. Jonsson and T. V. Pham, The reducts of the homogeneous binary branching CC-relation , J. Symbolic Logic 81 (2016), 1255--1297. doi:10.1017/jsl.2016.37 (https://doi.org/10.1017/jsl.2016.37). Numbered preprint references are to arXiv:1408.2554v2 (https://arxiv.org/abs/1408.2554v2).arXivDOI
  10. M. Bodirsky, P. Jonsson and T. V. Pham, The complexity of phylogeny constraint satisfaction problems , ACM Trans. Comput. Logic 18 (2017), no. 3, Article 23, 23:1--23:42. doi:10.1145/3105907 (https://doi.org/10.1145/3105907).DOI
Show all 40 referencesShow fewer references
  1. M. Bodirsky and M. Junker, ℵ0\aleph_0-categorical structures: endomorphisms and interpretations , Algebra Universalis 64 (2010), 403--417. doi:10.1007/s00012-011-0110-y (https://doi.org/10.1007/s00012-011-0110-y).DOI
  2. M. Bodirsky and J. Kára, The complexity of temporal constraint satisfaction problems , J. ACM 57 (2010), no. 2, Article 9, 9:1--9:41. doi:10.1145/1667053.1667058 (https://doi.org/10.1145/1667053.1667058).DOI
  3. M. Bodirsky and J. Nešetřil, Constraint satisfaction with countable homogeneous templates , J. Logic Comput. 16 (2006), no. 3, 359--373. doi:10.1093/logcom/exi083 (https://doi.org/10.1093/logcom/exi083).DOI
  4. M. Bodirsky and M. Pinsker, Minimal functions on the random graph , Israel J. Math. 200 (2014), 251--296. doi:10.1007/s11856-014-1042-y (https://doi.org/10.1007/s11856-014-1042-y).DOI
  5. M. Bodirsky, M. Pinsker and A. Pongrácz, The 42 reducts of the random ordered graph , Proc. London Math. Soc. (3) 111 (2015), 591--632. doi:10.1112/plms/pdv037 (https://doi.org/10.1112/plms/pdv037).DOI
  6. B. Bodor, Classification of ω\omega-categorical monadically stable structures , J. Symbolic Logic 89 (2024), 460--495. doi:10.1017/jsl.2023.66 (https://doi.org/10.1017/jsl.2023.66).DOI
  7. B. Bodor, Structures with not too fast unlabelled growth , J. Symbolic Logic, First View (2026), 1--52. doi:10.1017/jsl.2026.10239 (https://doi.org/10.1017/jsl.2026.10239).DOI
  8. P. J. Cameron, Transitivity of permutation groups on unordered sets , Math. Z. 148 (1976), 127--139. doi:10.1007/BF01214702 (https://doi.org/10.1007/BF01214702).DOI
  9. P. J. Cameron, Some treelike objects , Quart. J. Math. Oxford (2) 38 (1987), 155--183. doi:10.1093/qmath/38.2.155 (https://doi.org/10.1093/qmath/38.2.155).DOI
  10. M. Droste, Structure of partially ordered sets with transitive automorphism groups , Mem. Amer. Math. Soc. 57 (1985), no. 334, vi+100 pp. doi:10.1090/memo/0334 (https://doi.org/10.1090/memo/0334).DOI
  11. M. Droste, Partially ordered sets with transitive automorphism groups , Proc. London Math. Soc. (3) 54 (1987), no. 3, 517--543. doi:10.1112/plms/s3-54.3.517 (https://doi.org/10.1112/plms/s3-54.3.517).DOI
  12. M. Droste, W. C. Holland and H. D. Macpherson, Automorphism groups of infinite semilinear orders (I) , Proc. London Math. Soc. (3) 58 (1989), no. 3, 454--478. doi:10.1112/plms/s3-58.3.454 (https://doi.org/10.1112/plms/s3-58.3.454).DOI
  13. M. Droste, W. C. Holland and H. D. Macpherson, Automorphism groups of infinite semilinear orders (II) , Proc. London Math. Soc. (3) 58 (1989), no. 3, 479--494. doi:10.1112/plms/s3-58.3.479 (https://doi.org/10.1112/plms/s3-58.3.479).DOI
  14. M. Droste, W. C. Holland and H. D. Macpherson, Automorphism groups of homogeneous semilinear orders: normal subgroups and commutators , Canad. J. Math. 43 (1991), no. 4, 721--737. doi:10.4153/CJM-1991-041-7 (https://doi.org/10.4153/CJM-1991-041-7).DOI
  15. R. L. Graham and B. L. Rothschild, Some recent developments in Ramsey theory , in M. Hall, Jr. and J. H. van Lint (eds.), Combinatorics, Part 2: Graph Theory; Foundations, Partitions and Combinatorial Geometry , Mathematical Centre Tracts 56 , Mathematisch Centrum, Amsterdam, 1974, pp. 61--76. Digitised revised edition (1975) (https://ir.cwi.nl/pub/13259/13259D.pdf).link
  16. A. A. Ivanov, Finite covers, cohomology and homogeneous structures , Proc. London Math. Soc. (3) 78 (1999), 1--28. doi:10.1112/S002461159900163X (https://doi.org/10.1112/S002461159900163X).DOI
  17. M. Junker and M. Ziegler, The 116 reducts of (Q,<,a)(\mathbb Q,<,a) , J. Symbolic Logic 73 (2008), 861--884. doi:10.2178/jsl/1230396752 (https://doi.org/10.2178/jsl/1230396752).DOI
  18. A. S. Kechris, V. G. Pestov and S. Todorcevic, Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups , Geom. Funct. Anal. 15 (2005), 106--189. doi:10.1007/s00039-005-0503-1 (https://doi.org/10.1007/s00039-005-0503-1).DOI
  19. M. Kompatscher and T. V. Pham, A complexity dichotomy for poset constraint satisfaction , in 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) , Leibniz International Proceedings in Informatics 66 , Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2017, 47:1--47:12. doi:10.4230/LIPIcs.STACS.2017.47 (https://doi.org/10.4230/LIPIcs.STACS.2017.47).DOI
  20. H. Lee, Ramsey properties of trees and CC-relations via the partite construction , preprint, 2026. arXiv:2610.18402v1 (https://arxiv.org/abs/2610.18402v1).arXiv
  21. K. Leeb, Vorlesungen über Pascaltheorie , Arbeitsberichte des Instituts für Mathematische Maschinen und Datenverarbeitung 6 , Friedrich-Alexander-Universität Erlangen--Nürnberg, 1973. The ordered-tree theorem is also stated in GrahamRothschild74 .
  22. J. Linman and M. Pinsker, Permutations on the random permutation , Electron. J. Combin. 22 (2015), no. 2, Paper P2.54. doi:10.37236/4910 (https://doi.org/10.37236/4910).DOI
  23. D. Macpherson, A survey of Jordan groups , in R. Kaye and D. Macpherson (eds.), Automorphisms of First-Order Structures , Oxford University Press, Oxford, 1994, pp. 73--110. doi:10.1093/oso/9780198534686.003.0003 (https://doi.org/10.1093/oso/9780198534686.003.0003).DOI
  24. A. Mottet and M. Pinsker, Cores over Ramsey structures , J. Symbolic Logic 86 (2021), 352--361. doi:10.1017/jsl.2021.6 (https://doi.org/10.1017/jsl.2021.6).DOI
  25. P. P. Pach, M. Pinsker, G. Pluhár, A. Pongrácz and Cs. Szabó, Reducts of the random partial order , Adv. Math. 267 (2014), 94--120. doi:10.1016/j.aim.2014.08.008 (https://doi.org/10.1016/j.aim.2014.08.008).DOI
  26. A. Pongrácz, Reducts of the Henson graphs with a constant , Ann. Pure Appl. Logic 168 (2017), 1472--1489. doi:10.1016/j.apal.2017.01.009 (https://doi.org/10.1016/j.apal.2017.01.009).DOI
  27. A. Pongrácz, Existential reducts of the binary branching semilinear order and the Thomas conjecture , unpublished manuscript, 2020. Author's manuscript (https://math.unideb.hu/sites/default/files/upload_documents/semiexist.pdf).link
  28. A. Pongrácz, The existential Thomas Conjecture , in Homogeneous Structures: Model Theory meets Universal Algebra , Oberwolfach Reports 18 (2021), no. 1, 22--23. doi:10.4171/OWR/2021/1 (https://doi.org/10.4171/OWR/2021/1).DOI
  29. S. Thomas, Reducts of the random graph , J. Symbolic Logic 56 (1991), 176--181. doi:10.2307/2274912 (https://doi.org/10.2307/2274912).DOI
  30. S. Thomas, Reducts of random hypergraphs , Ann. Pure Appl. Logic 80 (1996), 165--193. doi:10.1016/0168-0072(95)00061-5 (https://doi.org/10.1016/0168-0072(95)00061-5).DOI

Version history

  1. v1 · 34 pagesSubmitted by Dr. András PongráczInitial depositCurrentNov 14, 2026