On finite reflexive homomorphism-homogeneous binary relational systems

A structure is called homogeneous if every isomorphism between finitely induced substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešet?il introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finitely induced substructures of the structure extends to an endomorphism of the structure.In this paper, we consider finite homomorphism-homogeneous relational systems with one reflexive binary relation. We show that for a large part of such relational systems (bidirectionally connected digraphs; a digraph is bidirectionally connected if each of its connected components can be traversed by ?-paths) the problem of deciding whether the system is homomorphism-homogeneous is coNP-complete. Consequently, for this class of relational systems there is no polynomially computable characterization (unless P=NP). On the other hand, in case of bidirectionally disconnected digraphs we present the full characterization. Our main result states that if a digraph is bidirectionally disconnected, then it is homomorphism-homogeneous if and only if it is either a finite homomorphism-homogeneous quasiorder, or an inflation of a homomorphism-homogeneous digraph with involution (a specific class of digraphs introduced later in the paper), or an inflation of a digraph whose only connected components are and .     

Natural dualities for three classes of relational structures

Motivated by the work of Hofmann [14] and Davey [7] on dualities for structures, we will construct natural dualities for the classes of quasi-ordered sets, equivalence-relationed sets, and reflexive (undirected) graphs. We describe the dual structures by giving finite sets of quasi-equations that axiomatise the dual categories. We also show that there is a natural connection between the duality we construct for finite quasi-ordered sets and Birkhoff’s representation theorem for finite ordered sets [2], and between the dualities constructed for quasi-ordered sets and equivalence-relationed sets.     

Deciding absorption in relational structures

We prove that for finite, finitely related algebras, the concepts of an absorbing subuniverse and a J´onsson absorbing subuniverse coincide. Consequently, it is decidable whether a given subset is an absorbing subuniverse of the polymorphism algebra of a given relational structure.     

The number of finite relational structures

An elementary proof is presented of an asymptotic estimate for the number (up to isomorphism) of finite relational structures, under a quite general definition of “relational structure”.     

Representation of ideals of relational structures

The age of a relational structure A of signature μ is the set age(A) of its finite induced substructures, considered up to isomorphism. This is an ideal in the poset Ω_μ consisting of finite structures of signature μ and ordered by embeddability. We shall show that if the structures have infinitely many relations and if, among those, infinitely many are at least binary then there are ideals which do not come from an age. We provide many examples. We particularly look at metric spaces and offer several problems. We also answer a question due to Cusin and Pabion [R. Cusin, J.F. Pabion, Une généralisation de l’âge des relations, C. R. Acad. Sci. Paris, Sér. A-B 270 (1970) A17-A20]: there is an ideal I of isomorphism types of at most countable structures whose signature consists of a single ternary relation symbol such that I does not come from the set of isomorphism types of substructures of A induced on the members of an ideal I of sets.     

Constraints, MMSNP and expander relational structures

We give a poly-time construction for a combinatorial classic known as Sparse Incomparability Lemma, studied by Erd?s, Lovász, Ne?et?il, Rödl and others: We show that every Constraint Satisfaction Problem is poly-time equivalent to its restriction to structures with large girth. This implies that the complexity classes CSP and Monotone Monadic Strict NP introduced by Feder and Vardi are computationally equivalent. The technical novelty of the paper is a concept of expander relations and a new type of product for relational structures: a generalization of the zig-zag product, the twisted product.     

Concrete categories and monoids of relational structures

Concrete categories of relational structures with bounded rank can be characterized by a condition that is intimately related to several known concepts.     

Stable structures homogeneous for a finite binary language

LetL be a finite relational language andH(L) denote the class of all countable stableL-structuresM for which Th(M) admits elimination of quantifiers. ForM ∈H(L) define the rank ofM to be the maximum value of CR(p, 2), wherep is a complete 1-type over Ø and CR(p, 2) is Shelah’s complete rank. IfL has only unary and binary relation symbols there is a uniform finite bound for the rank ofM ∈H(L). This theorem confirms part of a conjecture of the first author. Intuitively it says that for eachL there is a finite bound on the complexity of the structures inH(L).     

A discrete homotopy theory for binary reflexive structures

We present a simple combinatorial construction of a sequence of functors σ_k from the category of pointed binary reflexive structures to the category of groups. We prove that if the relational structure is a poset P then the groups are (naturally) isomorphic to the homotopy groups of P when viewed as a topological space with the topology of ideals, or equivalently, to the homotopy groups of the simplicial complex associated to P. We deduce that the group σ_k(X,x₀) of the pointed structure (X,x₀) is (naturally) isomorphic to the kth homotopy group of the simplicial complex of simplices of X, i.e. those subsets of X which are the homomorphic image of a finite totally ordered set.     

Ultracritical and hypercritical binary structures

A binary structure is an arc-coloured complete digraph, without loops, and with exactly two coloured arcs (u,v) and (v,u) between distinct vertices u and v. Graphs, digraphs and partial orders are all examples of binary structures. Let B be a binary structure. With each subset W of the vertex set V(B) of B we associate the binary substructure B[W] of B induced by W. A subset C of V(B) is a clan of B if for any c,d∈C and v∈V(B)?C, the arcs (c,v) and (d,v) share the same colour and similarly for (v,c) and (v,d). For instance, the vertex set V(B), the empty set and any singleton subset of V(B) are clans of B. They are called the trivial clans of B. A binary structure is primitive if all its clans are trivial.With a primitive and infinite binary structure B we associate a criticality digraph (in the sense of [11]) defined on V(B) as follows. Given v≠w∈V(B), (v,w) is an arc of the criticality digraph of B if v belongs to a non-trivial clan of B[V(B)?{w}]. A primitive and infinite binary structure B is finitely critical if B[V(B)?F] is not primitive for each finite and non-empty subset F of V(B). A finitely critical binary structure B is hypercritical if for every v∈V(B), B[V(B)?{v}] admits a non-trivial clan C such that |V(B)?C|≥3 which contains every non-trivial clan of B[V(B)?{v}]. A hypercritical binary structure is ultracritical whenever its criticality digraph is connected.The ultracritical binary structures are studied from their criticality digraphs. Then a characterization of the non-ultracritical but hypercritical binary structures is obtained, using the generalized quotient construction originally introduced in [1].     

Obstades to duality between classes of relational structures

Algebra universalis - We prove an algebraic result concerning inverse limits of copowers in anS-class of relational structures of the same (finitary or infinitary) type. Among several applications...     

On the symmetric conservative form of a binary reacting mixture

Summary We consider the system governing a non equilibrium gas flow with a chemical reaction, neglecting, as usual for detonation phenomena, transport effects. It is shown that it is possible to put the system in symmetric and conservative form. Moreover we write the generating shock function and discuss it in the case of a polytropic mixture.

---

Sommario Si considéra il sistema di equazioni che governano un gas in cui avviene una reazione chimica trascurando, com'é usuale per i fenomeni di detonazione, gli effetti di trasporto. Si fa vedere che é possibile mettere il sistema in forma simmetrica e conservativa. Inoltre viene scritta la funzione génératrice degli urti che viene discussa nel caso di una miscela di gas politropici.

     

On countable stable structures which are homogeneous for a finite relational language

LetL be a finite relational language andH(L) denote the class of all countable structures which are stable and homogeneous forL in the sense of Fraissé. By convention countable includes finite and any finite structure is stable. A rank functionr :H(L) →ω is introduced and also a notion of dimension for structures inH(L). A canonical way of shrinking structures is defined which reduces their dimensions. The main result of the paper is that anyM ∈H(L) can be shrunk toM′ ∈H(L),M′ ⊆M, such that |M′| is bounded in terms ofr(M), and the isomorphism type ofM overM′ is uniquely determined by the dimensions ofM. Forr<ω we deduce thatH(L, r), the class of allM ∈H(L) withr(M)≦r, is the union of a finite number of classes within each of which the isomorphism type of a structure is completely determined by its dimensions. Dedicated to the memory of Abraham Robinson on the tenth anniversary of his death