\documentclass[11pt,a4paper]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern,microtype} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage[margin=28mm]{geometry} \usepackage{float} \usepackage{tikz} \usetikzlibrary{arrows.meta,positioning} \usepackage{caption} \captionsetup{font=small,labelfont=bf} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} \hypersetup{ pdftitle={Self-embedding monoids and the existential Thomas conjecture}, pdfauthor={Andr\'as Pongr\'acz} } \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{remark}[theorem]{Remark} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\Emb}{Emb} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\Inj}{Inj} \DeclareMathOperator{\Sym}{Sym} \DeclareMathOperator{\Age}{Age} \newcommand{\Sii}{S_2} \newcommand{\inc}{\mathrel{\parallel}} \newcommand{\distinct}{\operatorname{Dist}} \newcommand{\Crel}[3]{C(#1;#2,#3)} \newcommand{\Rrel}[3]{R(#1;#2,#3)} \newcommand{\Qrel}[4]{Q(#1,#2;#3,#4)} \newcommand{\Prel}[4]{P(#1,#2;#3,#4)} \newcommand{\Delt}{\Delta} \title{Self-embedding monoids and\\the existential Thomas conjecture} \author{Andr\'as Pongr\'acz\\[2pt] \small University of Debrecen, Institute of Mathematics\\ \small 4032 Debrecen, Egyetem t\'er 1, Hungary\\ \small ORCID: \href{https://orcid.org/0000-0002-2771-8974}{0000-0002-2771-8974}} \date{14 November 2026} \begin{document} \maketitle \begin{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 \(C\)-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. \end{abstract} {\small \noindent\textbf{2020 Mathematics Subject Classification.} Primary 03C15; Secondary 20B27, 03C40, 20M20.\par \noindent\textbf{Keywords.} Semilinear order, reduct, self-embedding monoid, existential definability, binary tree, C-relation.\par } \section{Introduction} A \emph{reduct} of a relational structure \(\Delta\) is a structure on the same domain whose basic relations are first-order definable in \(\Delta\) without parameters. For a countable \(\omega\)-categorical structure, classifying reducts up to first-order interdefinability is equivalent to classifying permutation groups containing \(\Aut(\Delta)\) that are closed in the pointwise-convergence topology on the symmetric group of the domain. Thomas conjectured that this interval is finite whenever \(\Delta\) is homogeneous in a finite relational language \cite{Thomas91,Thomas96}. Classical classifications include the rational order \cite{Cameron76}, the random graph and random hypergraphs \cite{Thomas91,Thomas96}, and expansions of the rational order by constants \cite{JunkerZiegler08}. Further classifications cover the random partial order \cite{PPPS14}, the random ordered graph \cite{BPP15}, the random permutation \cite{LinmanPinsker15}, the generic digraph \cite{Agarwal16}, the Henson digraphs \cite{AgarwalKompatscher18}, and Henson graphs expanded by a constant \cite{Pongracz17}. Bodirsky's monograph \cite{Bodirsky21} provides general background on definability, oligomorphic groups and their transformation monoids. Self-embeddings retain more information than automorphisms. An embedding preserves each basic relation and its complement, and an \(\omega\)-categorical structure's self-embedding monoid determines all of its existentially definable relations. Recall that a structure is \emph{model-complete} if every first-order formula is equivalent, modulo its theory, to an existential formula. For a countable \(\omega\)-categorical structure \(\Gamma\) with domain \(D\), the criterion due to Bodirsky and Pinsker, recorded with that attribution by Bodirsky and Junker \cite[Corollary~2.3]{BodirskyJunker10}, states that \(\Gamma\) is model-complete exactly when \(\Emb(\Gamma)=\overline{\Aut(\Gamma)}\). Here the closure is taken in \(D^D\) with the topology of pointwise convergence, with \(D\) discrete. The equality means that every self-embedding agrees with an automorphism on each finite subset of \(D\). A \emph{core} is a structure whose endomorphisms are embeddings. Consequently, writing \(\End(\Gamma)\) for the endomorphism monoid, \(\Gamma\) is a model-complete core exactly when \(\End(\Gamma)=\overline{\Aut(\Gamma)}\); see also \cite[Theorem~18]{Bodirsky07}. Thus for model-complete reducts the automorphism group already determines the self-embedding monoid; for example, all reducts of the random graph are model-complete \cite{BodirskyPinsker14}. The existential strengthening of Thomas' conjecture asks whether a countable homogeneous structure in a finite relational language has only finitely many self-embedding monoids of reducts. The author's earlier manuscript formulated this assertion \emph{with the Ramsey hypothesis} \cite[Conjecture~4.5]{Pongracz20}; the broader formulation is discussed in \cite{Pongracz21}. Its definability formulation requires existential definitions of both basic relations and their complements; Section~\ref{sec:transfer} explains this convention. Our counterexample refutes both formulations. Recall that a structure is \emph{Ramsey} if, for any finite substructures \(A,B\) and integer \(r\geq2\), some finite substructure \(C\) has the property that every \(r\)-colouring of the copies of \(A\) in \(C\) is constant on those contained in some copy of \(B\). It is \emph{finitely bounded} if its age is specified by a finite list of forbidden induced substructures. \begin{theorem}\label{thm:intro-counterexample} There exists a countably infinite homogeneous, finitely bounded Ramsey structure in a finite relational language of maximum arity two which has finitely many reducts up to first-order interdefinability, but admits a sequence of quantifier-free reducts whose self-embedding monoids form a strictly increasing infinite chain. These reducts are all first-order interdefinable with one another, and each has a single basic relation. \end{theorem} The construction starts with an equivalence relation having infinitely many singleton classes and infinitely many infinite classes. Adding a unary predicate for the set of nonsingleton-class points makes the structure homogeneous. Its first-order reducts form a five-element lattice, which we determine explicitly; their finiteness also follows from Bodor's general theorem \cite{Bodor24}. A suitable convex order gives the Ramsey expansion in Theorem~\ref{thm:intro-counterexample}. The infinite chain is constructed in Theorem~\ref{thm:infinite-embeddings}, and Proposition~\ref{prop:ramsey-counterexample} verifies homogeneity, finite boundedness and the Ramsey property. For this ordered expansion, Appendix~\ref{app:ordered-finiteness} proves first-order finiteness, without enumerating its reducts, using Cameron's classification \cite{Cameron76} and Bodor's bounds for finite covers \cite{Bodor26}. The other part of the paper concerns the binary branching semilinear order. Its first-order reducts were classified by Bodirsky, Bradley-Williams, Pinsker and Pongr\'acz \cite{BBWP18}; their analysis also identified an injection into an antichain that preserves and reflects a derived rooted-tree relation, but does not preserve the original order. Thus an automorphism-group classification does not settle the embedding-monoid problem. The five-monoid classification was stated in the author's unpublished 2020 manuscript \cite[Theorem~2.7]{Pongracz20}. Here we give a revised and completed proof, making the reconstruction from homogeneous leaf structures explicit. The five monoids form the lattice in Figure~\ref{fig:lattice}. Three come from the original order, its betweenness relation, and equality. The remaining two preserve the rooted-triple relation \(R\) and the unrooted-quartet relation \(P\) obtained by replacing each marked point by a leaf. These relations will be defined explicitly in Section~\ref{sec:trees}. %All classifications in this paper concern actual self-embedding monoids. We do not identify them with arbitrary closed monoids of injections. The structure and automorphism groups of semilinear orders were studied by Droste \cite{Droste85,Droste87} and by Droste, Holland and Macpherson \cite{DHM89I,DHM89II,DHM91}. Semilinear orders and their associated betweenness relations also occur among the structures in Adeleke and Macpherson's classification of infinite primitive Jordan permutation groups \cite{AdelekeMacpherson96}; Macpherson \cite{Macpherson94} surveys this connection with model theory. For an earlier study of structures described by relations on tree leaves, see Cameron \cite{Cameron87}. Adeleke and Neumann \cite{AdelekeNeumann98} give a systematic treatment of semilinear orders, betweenness relations, and the ternary branching and quaternary separation relations known as \(C\)- and \(D\)-relations. Section~\ref{sec:trees} specifies the conventions for the binary branching relations used here. The proof uses the published classification of reducts of the homogeneous binary branching \(C\)-relation by Bodirsky, Jonsson and Pham \cite{BJP16}. Passing to a maximal antichain gives access to that theorem, but it does not by itself reconstruct the monoid on the whole semilinear order. The missing step concerns maps that preserve every rooted triple on antichains but change a triple containing comparable points. We show that one such map forces the basic relations of the reduct to depend only on equality. The argument proceeds through finite labelled trees: a local change supplied by the map can be inserted into larger configurations, and induction connects all trees on a fixed set of labels. The corresponding unrooted argument is reduced to this rooted argument by fixing an auxiliary leaf. A map is called \emph{flat} if it is injective and its image is an antichain. The initial reduction to such a map is inherited from \cite{BBWP18}; the leaf classification is inherited from \cite{BJP16}. The finite-tree and rerooting techniques have predecessors in \cite[Section~4.2]{BJP16} and \cite[Lemma~4.27]{BBWP18}; the two-sided invariant-relation argument below is what allows us to use them for self-embedding monoids. The counterexample and its first-order reduct analysis are additional to the author's unpublished 2020 manuscript. For general results on homogeneous images of canonical maps and transfer of the Ramsey property, see Mottet and Pinsker \cite{MottetPinsker21}. Structural Ramsey theory enters through the cited classification and flat-map results. Appendix~\ref{app:ramsey} supplies a direct proof of the specific Ramsey input used there, avoiding an invalid general transfer assertion in the original citation chain. The reconstruction arguments require no additional canonisation theorem. These classifications also connect with constraint satisfaction through primitive-positive definability. A \emph{primitive-positive} (pp) formula is an existentially quantified conjunction of atomic formulas. For a structure \(\Gamma\) with a finite relational signature, \(\operatorname{CSP}(\Gamma)\) asks whether an input pp sentence holds in \(\Gamma\). For \(\omega\)-categorical \(\Gamma\), a nonempty relation is pp-definable precisely when it is preserved by every \emph{polymorphism} of \(\Gamma\), that is, every operation of finite positive arity preserving the basic relations coordinatewise, by the preservation theorem of Bodirsky and Ne\v{s}et\v{r}il \cite{BodirskyNesetril06}; see also \cite{Bodirsky21}. Consequently pp-interdefinable finite-signature structures have polynomial-time equivalent CSPs. The relevant invariant is therefore the collection of all polymorphisms, rather than the self-embedding monoid alone. For the random partial order, Kompatscher and Pham build on the first-order classification \cite{PPPS14}, analyse endomorphisms and polymorphisms, and obtain a polynomial-time versus NP-complete dichotomy for every finite-signature reduct \cite[Theorems~1 and~4]{KompatscherPham17}. This establishes the complexity classification without requiring an enumeration of all pp-interdefinability classes. Related dichotomies hold for temporal constraint satisfaction, that is, reducts of the rational order \cite{BodirskyKara10}, and for phylogeny constraint satisfaction, that is, reducts of the homogeneous binary branching \(C\)-relation \cite{BJP17}. In the latter case the existential classification \cite{BJP16}, also used here, supplies a structural input to the complexity analysis. \section{Structures, tree relations and the classification}\label{sec:trees} \subsection{The semilinear order and its finite diagrams} A partial order is \emph{semilinear} if any two elements have a common upper bound and the upper bounds of each element form a chain. We work with the unique countable existentially closed semilinear order \((\Sii;\leq)\). We use the description and homogeneity result of \cite[Proposition~3.4 and Theorem~3.5]{BBWP18}. In particular, the order is dense, unbounded, binary branching, nice, and without joins. Here \(x\inc y\) means that \(x\) and \(y\) are incomparable. Unboundedness means that for every \(x\) there are \(y,z\) with \(yx\) is incomparable with \(y\). \item \emph{Absence of joins:} if \(x,yy\) with \(d\inc x\), and binary branching below \(d\) gives \(wn\). Every \(R_m\)-tuple lies in one infinite source class and is mapped into one infinite target class, so \(f_n\) preserves \(R_m\). To check reflection, an \(R_m\)-tuple in the image cannot lie in \(C_0\), which contains only \(n\) image points. If it lies in \(C_{i+1}\), all of its preimages lie in \(C_i\). Its coordinates have distinct preimages, so these preimages form an \(R_m\)-tuple. Consequently \(f_n\in\Emb(\Gamma_m)\). On the other hand, \((s_0,\ldots,s_{n-1})\) belongs to \(S_n\), while its image does not. Hence \(f_n\notin\Emb(\Gamma_n)\), proving every strict inclusion. The same witness proves the assertion about existential definitions: an embedding preserves an existential formula by transporting its witnesses, since it preserves all quantifier-free formulas, including negated atoms. If \(S_n\) had an existential definition in \(\Gamma_m\), then \(f_n\) would preserve \(S_n\). Finally, \[ E(x,y)\quad\Longleftrightarrow\quad x=y\ \vee\ \exists z_3\cdots z_n\,\neg S_n(x,y,z_3,\ldots,z_n). \] For \(n=2\) the quantifier block is empty. For \(n>2\), two distinct \(E\)-equivalent points lie in an infinite class and can be extended to \(n\) distinct points there. This proves the displayed definition in both directions. Conversely, \(S_n\) is quantifier-free definable from \(E\), so the structures are first-order interdefinable. \end{proof} In particular, all the reducts \(\Gamma_n\) belong to one first-order interdefinability class. Their embedding monoids have the same group of invertible elements, namely \(\Aut(D;E)\). The complement in the definition of \(\Gamma_n\) also makes the existential separation visible on a named relation. This is consistent with the two-sided convention of Section~\ref{sec:transfer}: although \(E\) is existentially definable in each \(\Gamma_n\), its complement is not existentially definable there for \(n\geq3\). Indeed, \(f_2\in\Emb(\Gamma_n)\) sends the non-\(E\)-related pair \((s_0,s_1)\) into \(C_0\). For \(n=2\), both \(E\) and its complement are quantifier-free definable. The theorem proves failure of existential finiteness even without appealing to a preservation theorem. \subsection{The five first-order reducts of the unordered structure} Define two further equivalence relations on \(D\) by \[ F(x,y)\ \Longleftrightarrow\ E(x,y)\vee(x\in S\wedge y\in S),\qquad J(x,y)\ \Longleftrightarrow\ (U(x)\leftrightarrow U(y)). \] The \(F\)-classes are \(S,C_0,C_1,\ldots\), whereas the \(J\)-classes are \(S,U\). \begin{theorem}\label{thm:five-equivalence-reducts} Up to first-order interdefinability, the reducts of \(\Omega\) are exactly \[ (D;E),\qquad (D;F),\qquad (D;U),\qquad (D;J),\qquad(D;=). \] Writing \(G_E,G_F,G_U,G_J\) for their respective automorphism groups, their strict inclusions are precisely the two chains \[ G_E