Regular families of forests, antichains and duality pairs of relational structures (Q681598): Difference between revisions

Given a relational type \(\sigma = \{ R_1, \ldots, R_m \}\), and a \(\sigma\)-structure \(\mathbb A = \langle A;\) \(R_1(\mathbb A), \ldots,\) \(R_m(\mathbb A) \rangle\), where \(R_i(\mathbb A) \subseteq A^{r_i}\) for each \(i\), the \textit{incidence graph} Inc(\(\mathbb A\)) is the bipartite graph of vertices \(A \cup C\) (where \(C = \{ (R_i, x_1, \ldots, x_{r_i}) : R_i(\mathbb A)(x_1, \ldots, x_{r_i}) \}\)) and edges \(\{x_j, (R_i, x_1, \ldots, x_{r_i})\}\) for each \(i\), \(j\) and \((R_i, x_1,\) \(\ldots, x_{r_i}) \in C\). This article concerns those \(\mathbb A\) for which Inc(\(\mathbb A\)) is acyclic: fixing \(\sigma\), let \(\mathbb F\) be the set of \(\sigma\)-structures for which the incidence graph is a forest, and call the structures in \(\mathbb F\) \textit{\(\sigma\)-forests}. For two \(\sigma\)-forests \(\mathbb A\) and \(\mathbb B\), write ``\(\mathbb A \to \mathbb B\)'' if there is a homomorphism from \(\mathbb A\) to \(\mathbb B\). Notice that \(\to\) is a preorder, i.e., a reflexive and transitive relation. Much of this article concerns the family of \(\sigma\)-forests and homomorphisms, although there is little explicit category theory (and this article is relatively self-contained). For example, a \textit{core} of a \(\sigma\)-forest \(\mathbb A\) is a \(\sigma\)-forest \(\mathbb B\) of minimum cardinality such that \(\mathbb A \leftrightarrow \mathbb B\); a core of a \(\sigma\)-forest is unique up to isomorphism. Much of this paper is devoted to ``duality pairs'': we call \((\mathcal O, \mathcal D)\) a \textit{duality pair} if, for any \(\sigma\)-forest \(\mathbb A\), \(\mathbb A \to \mathbb D\) for some \(\mathbb D \in \mathcal D\) if and only if for all \(\mathbb T \in \mathcal O\), \(\mathbb T \not \to \mathbb A\). We are interested in ``regular'' families \(\mathcal O \subseteq \mathbb F\). For any \(\sigma\)-structure \(\mathbb A\) and any \(a \in A\), we obtain a ``rooted structure'' \((\mathbb A, a)\), and given any two rooted structures \((\mathbb A, a)\) and \((\mathbb B, b)\), we may ``add'' them by identifying their roots, obtaining \([(\mathbb A, a) + (\mathbb B, b)]\). Notice that if both \(\mathbb A\) and \(\mathbb B\) were \(\sigma\)-forests, then so is their sum. Let \[ {\mathcal O} - (\mathbb A, a) = \{(\mathbb B, b) : [(\mathbb A, a) + (\mathbb B, b)] \in \mathcal O \}. \] Write \((\mathbb A, a) \; {\sim}_{\mathcal O} \; (\mathbb A', a')\) if \({\mathcal O} - (\mathbb A, a) = {\mathcal O} - (\mathbb A', a')\). Then ``in the spirit of the Myhill-Nerode theorem,'' we may define \(\mathcal O\) to be \textit{regular} if \({\sim}_{\mathcal O}\) has finitely many equivalence classes. Much machinery (much of it using duality pairs) is assembled in the first half of the article, and having assembled the machinery, the second half of the article is devoted to the following result. If \(\mathcal O\) is a regular set of \(\sigma\)-forests, then the set of cores of the \(\to\)-minimal elements of \(\mathcal O\) is also regular. The motivation is provided by the Constraint Satisfaction Problem, but the machinery may also be of interest to algebraists.