Discrete Mathematics & Theoretical Computer Science |
A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. We show that on the algebra of binary trees whose leaves are labeled by letters of an alphabet containing at least three letters, a function is congruence preserving if and only if it is polynomial.
We assign a relational structure to any finite algebra in a canonical way, using solution sets of equations, and we prove that this relational structure is polymorphism-homogeneous if and only if the algebra itself is polymorphism-homogeneous. We show that polymorphism-homogeneity is also equivalent to the property that algebraic sets (i.e., solution sets of systems of equations) are exactly those sets of tuples that are closed under the centralizer clone of the algebra. Furthermore, we prove that the aforementioned properties hold if and only if the algebra is injective in the category of its finite subpowers. We also consider two additional conditions: a stronger variant for polymorphism-homogeneity and for injectivity, and we describe explicitly the finite semilattices, lattices, Abelian groups and monounary algebras satisfying any one of these three conditions.
The age $\mathcal{A}(G)$ of a graph $G$ (undirected and without loops) is the collection of finite induced subgraphs of $G$, considered up to isomorphy and ordered by embeddability. It is well-quasi-ordered (wqo) for this order if it contains no infinite antichain. A graph is \emph{path-minimal} if it contains finite induced paths of unbounded length and every induced subgraph $G'$ with this property embeds $G$. We construct $2^{\aleph_0}$ path-minimal graphs whose ages are pairwise incomparable with set inclusion and which are wqo. Our construction is based on uniformly recurrent sequences and lexicographical sums of labelled graphs.
The finite models of a universal sentence $\Phi$ in a finite relational signature are the age of a structure if and only if $\Phi$ has the joint embedding property. We prove that the computational problem whether a given universal sentence $\Phi$ has the joint embedding property is undecidable, even if $\Phi$ is additionally Horn and the signature of $\Phi$ only contains relation symbols of arity at most two.
We present the Boolean dimension of a graph, we relate it with the notions of inner, geometric and symplectic dimensions, and with the rank and minrank of a graph. We obtain an exact formula for the Boolean dimension of a tree in terms of a certain star decomposition. We relate the Boolean dimension with the inversion index of a tournament.
The ternary relation B(x,y,z) of betweenness states that an element y is between the elements x and z, in some sense depending on the considered structure. In a partially ordered set (N,≤), B(x,y,z):⇔x<y<z∨z<y<x, and the corresponding betweenness structure is (N,B). The class of betweenness structures of linear orders is first-order definable. That of partial orders is monadic second-order definable. An order-theoretic tree is a partial order such that the set of elements larger that any element is linearly ordered and any two elements have an upper-bound. Finite or infinite rooted trees ordered by the ancestor relation are order-theoretic trees. In an order-theoretic tree, B(x,y,z) means that x<y<z or z<y<x or x<y≤x⊔z or z<y≤x⊔z, where x⊔z is the least upper-bound of incomparable elements x and z. In a previous article, we established that the corresponding class of betweenness structures is monadic second-order definable.We prove here that the induced substructures of the betweenness structures of the countable order-theoretic trees form a monadic second-order definable class, denoted by IBO. The proof uses a variant of cographs, the partitioned probe cographs, and their known six finite minimal excluded induced subgraphs called the bounds of the class. This proof links two apparently unrelated topics: cographs and order-theoretic trees.However, the class IBO has finitely many bounds, i.e., minimal excluded finite induced […]