Binary homomorphisms and natural dualities

We investigate ways in which certain binary homomorphisms of a finite algebra can guarantee its dualisability. Of particular interest are those binary homomorphisms which are lattice, flat-semilattice or group operations. We prove that a finite algebra which has a pair of lattice operations amongst its binary homomorphisms is dualisable. As an application of this result, we find that every finite unary algebra can be embedded into a dualisable algebra. We develop some general tools which we use to prove the dualisability of a large number of unary algebras. For example, we show that the endomorphisms of a finite cyclic group are the operations of a dualisable unary algebra.     

Homomorphisms of algebras

A construction of all homomorphisms of an algebra with a finite number of operations into an algebra of the same type is presented that consists in replacing algebras by suitable mono-unary algebras (possibly with some nullary operations) and their homomorphisms by suitable homomorphisms of the corresponding mono-unary algebras. Since a construction of all homomorphisms between two mono-unary algebras is known (see, e.g., [6], [7], [8]), a construction of all homomorphisms of an arbitrary algebra with a finite number of operations into an algebra of the same type can be described.     

Intersections of graphs

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed image graph H. We introduce our techniques by proving that the lex graph has the largest number of homomorphisms into K₂ with one looped vertex (or equivalently, the largest number of independent sets) among graphs with fixed number of vertices and edges. Our main result is the solution to the extremal problem for the number of homomorphisms into P, the completely looped path of length 2 (known as the Widom–Rowlinson model in statistical physics). We show that there are extremal graphs that are threshold, give explicitly a list of five threshold graphs from which any threshold extremal graph must come, and show that each of these “potentially extremal” threshold graphs is in fact extremal for some number of edges. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 261–284, 2011     

Inner Homomorphisms and Positive-Conditional Terms

We establish the criterion for two finite or uniformly locally finite algebras of a finite signature to be positive-conditionally rational equivalent (in terms of semigroups of inner homomorphisms of these algebras) and the criterion for two finite algebras to be strongly similar (in terms of expanded semigroups of inner homomorphisms of those algebras).     

The Theory of Finite Models without Equal Sign

In this paper, it is the first time ever to suggest that we study the model theory of all finite structures and to put the equal sign in the same situtation as the other relations. Using formulas of infinite lengths we obtain new theorems for the preservation of model extensions, submodels, model homomorphisms and inverse homomorphisms. These kinds of theorems were discussed in Chang and Keisler＇s Model Theory, systematically for general models, but Gurevich obtained some different theorems in this direction for finite models. In our paper the old theorems manage to survive in the finite model theory. There are some differences between into homomorphisms and onto homomorphisms in preservation theorems too. We also study reduced models and minimum models. The characterization sentence of a model is given, which derives a general result for any theory T to be equivalent to a set of existential-universal sentences. Some results about completeness and model completeness are also given.     

Walkwise and admissible mappings between digraphs

We define two classes of mappings, between digraphs, which are closely related to homomorphisms and pathwise homomorphisms of finite automata. We show that the cycle rank cannot increase under mappings of these types, derive various decomposition properties, and then relate these mappings to homomorphisms of digraphs.     

The wonderland of reflections

A fundamental fact for the algebraic theory of constraint satisfaction problems (CSPs) over a fixed template is that pp-interpretations between at most countable ω-categorical relational structures have two algebraic counterparts for their polymorphism clones: a semantic one via the standard algebraic operators H, S, P, and a syntactic one via clone homomorphisms (capturing identities). We provide a similar characterization which incorporates all relational constructions relevant for CSPs, that is, homomorphic equivalence and adding singletons to cores in addition to ppinterpretations. For the semantic part we introduce a new construction, called reflection, and for the syntactic part we find an appropriate weakening of clone homomorphisms, called h1 clone homomorphisms (capturing identities of height 1).As a consequence, the complexity of the CSP of an at most countable ω-categorical structure depends only on the identities of height 1 satisfied in its polymorphism clone as well as the natural uniformity thereon. This allows us in turn to formulate a new elegant dichotomy conjecture for the CSPs of reducts of finitely bounded homogeneous structures.Finally, we reveal a close connection between h1 clone homomorphisms and the notion of compatibility with projections used in the study of the lattice of interpretability types of varieties.     

Semiglobal models of extensions of two-dimensional local fields

This paper consider a special class of finite homomorphisms of complete two-dimensional regular local rings-the so-called “model homomorphi sms.” We show that studying the ramification of morphisms of formal curves induced by these homomorphisms helps identifying the ramification in extensions of two-dimensional local fields. Some basic properties of model homomorphisms are established.     

Uniformly finite-to-one and onto extensions of homomorphisms between strongly connected graphs

For a homomorphism between directed graphs G₁ and G₂, its extension is the mapping of the set of all paths in G₁ into the set of all paths in G₂ obtained by naturally extending it. We investigate the properties of uniformly finite-to-one and onto extensions of homomorphisms of directed graphs, essentially the properties of uniformly finite-to-one and onto extensions of homomorphisms between strongly connected directed graphs. We also describe applications of our results on homomorphisms of directed graphs to the theory of a class of symbolic flows called subshifts of finite type.     

A Combinatorial Interpretation of a General Case of a Fine Identity

We introduce a combinatorial map which leads to general forms and finite versions of an elegant q-series identity. It is with these results that we present many new identities analogous to the first. We close with a discussion of the path taken and future possibilities.     

Prefix-primitivity-preserving homomorphisms

This paper aims to investigate homomorphisms which preserve p-primitive languages. A characterization of p-primitivity-preserving homomorphisms can be detected within finite steps. Also the set of square-freeness-preserving homomorphisms is shown to be a proper subfamily of the set of p-primitivity-preserving homomorphisms. For homomorphisms over an alphabet X with |X|=2, it is also shown that the set of p-primitivity-preserving homomorphisms is a proper subfamily of the set of primitivity-preserving homomorphisms. But it is conjectured to also hold for homomorphisms over an alphabet with more than two letters.     

Lower complete intersection dimension over local homomorphisms

We introduce and study a theory of lower complete intersection dimension over local homomorphisms which encompasses the theory of lower complete intersection dimension for finite modules over local rings introduced by Gerko. In particular, we show that the lower complete intersection dimension over local homomorphisms reflects the complete intersection property of base rings as expected. As an application, we prove that the converse of a theorem of Sather-Wagstaff is also true.     

Ring Homomorphisms and Finite Gorenstein Dimension

The local structure of homomorphisms of commutative noetherianrings is investigated from the point of view of dualizing complexes.A concept of finite Gorenstein dimension, which substantiallyweakens the notion of finite flat dimension, is introduced forhomomorphisms. It is shown to impose structural constraints,due to a remarkable equivalence of subcategories of the derivedcategory of all modules. An essential part of this study is the development of relativenotions of dualizing complexes and Bass numbers. It is provedthat the Bass numbers of local homomorphisms are rigid, extendinga known result for local rings. Quasi-Gorenstein homomorphismsare introduced as local homomorphisms that base-change a dualizingcomplex for the source ring into one for the target. They areshown to have the stability properties of the Gorenstein homomorphismthat they generalize. 1991 Mathematics Subject Classification:primary 13H10, 13D23, 14E40; secondary 13C15.     

Jordan Superhomomorphisms of Superalgebras

The aim of this article is to investigate Jordan superhomomorphisms of superalgebras (with and without superinvolution), using the theory of functional identities in superalgebras. As a consequence we slightly improve a result on Jordan homomorphisms of rings with involution.     

An algorithm for the number of path homomorphisms

A homomorphism of a graph G₁=(V₁,E₁) to a graph G₂=(V₂,E₂) is a mapping from the vertex set V₁ of G₁ to the vertex set V₂ of G₂ which preserves edges. In this paper we provide an algorithm to determine the number of homomorphisms from an arbitrary finite undirected path to another arbitrary finite undirected path.     

List-Compactness of Infinite Directed Graphs

A digraph H is homomorphically compact if the digraphs G which admit homomorphisms to H are exactly the digraphs whose finite subdigraphs all admit homomorphisms to H. In this paper we define a similar notion of compactness for list-homomorphisms. We begin by showing that it is essentially only finite digraphs that are compact with respect to list-homomorphisms. We then explore the effects of restricting the types of list-assignments which are permitted, and obtain some richer characterizations. Received: May 16, 1997 Final version received: January 16, 1998     

Homogeneous groups

We investigate the structure of homogeneous torsion-free a-belian groups of finite rank in terms of their hyper-types and the existence of homomorphisms between two such groups.     

Descent of the complete intersection property by homomorphisms of finite virtual projective dimension

We prove a descent theorem for the complete intersection property by homomorphisms of finite (Avramov's) virtual projective dimension. This result suggests a (slight) modification of Avramov's definition of virtual projective dimension.     

The identities of the free product of two trivial semigroups

We exhibit an example of a finitely presented semigroup S with a minimum number of relations such that the identities of S have a finite basis while the monoid obtained by adjoining 1 to S admits no finite basis for its identities. Our example is the free product of two trivial semigroups.