Independence and graph homomorphisms graph homomorphisms

A graph with n vertices that contains no triangle and no 5-cycle and minimum degree exceeding n/4 contains an independent set with at least (3n)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7-cycle and invoking the No Homomorphism Lemma. For k ≥ 4, a graph with n vertices, odd girth 2k+1, and minimum degree exceeding n/(k+1) contains an independent set with at least kn/(2k+1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.     

Square-free-preserving and primitive-preserving homomorphisms

The aim of this paper is to investigate homomorphisms which reserve square-free languages or primitive languages. A characterization of square-free-preserving homomorphisms is presented. We show that every square-free-preserving homomorphism is primitive-preserving. Strongly cube-free-preserving homomorphisms are also studied.     

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.     

Fully idempotent homomorphisms

For arbitrary modules A and B we introduce and study the notion of a fully idempotent Hom (A, B). As a corollary we obtain some well-known properties of fully idempotent rings and modules.     

Equivalence of metric homomorphisms

Suppose K is an algebra with involution overk and A, B are K-modules on which are defined -Hermitian K-invariant forms with values ink. Metric homomorphisms of the module A into the module are called equivalent in the broad sense if one can be obtained from the other by multiplying by automorphisms of both modules, and equivalent in the narrow sense if one can be obtained from the other by multiplying by an automorphism of B. Necessary and sufficient conditions are given for the broad and narrow equivalence of two metric homomorphisms of one semisimple module of finite length into another. As a consequence, a classification of representations of one quadratic form by means of another is obtained.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 114, pp. 205–210, 1982.In conclusion, the author would like to express her sincere gratitude to A. V. Yakovlev, under whose guidance this paper was written, for many valuable discussions and for his useful advice.     

Complexes of graph homomorphisms

Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that Hom(K _m, K_n) is homotopy equivalent to a wedge of (n−m)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ ₁ ^k (Hom(K _m, G))≠0, thenχ(G)≥k+m; here ℤ₂-action is induced by the swapping of two vertices inK _m, and ϖ₁ is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K _n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K _n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.     

Flat bundles and holonomy homomorphisms

Using the natural equivalence relation in the set of flat Banach principal fibre bundles with group G and connected base B, we obtain a bisection between the corresponding equivalence classes and classes of similar homomorphisms of ₁(B) into G.     

Graph homomorphisms and nodal domains

In this paper, we derive some necessary spectral conditions for the existence of graph homomorphisms in which we also consider some parameters related to the corresponding eigenspaces such as nodal domains. In this approach, we consider the combinatorial Laplacian and co-Laplacian as well as the adjacency matrix. Also, we present some applications in graph decompositions where we prove a general version of Fisher’s inequality for G-designs.     

Commuting elements and spaces of homomorphisms

This article records basic topological, as well as homological properties of the space of homomorphisms Hom(π,G) where π is a finitely generated discrete group, and G is a Lie group, possibly non-compact. If π is a free abelian group of rank equal to n, then Hom(π, G) is the space of ordered n–tuples of commuting elements in G. If G = SU(2), a complete calculation of the cohomology of these spaces is given for n = 2, 3. An explicit stable splitting of these spaces is also obtained, as a special case of a more general splitting. Alejandro Adem was partially supported by the NSF and NSERC. Frederick R. Cohen was partially supported by the NSF, grant number 0340575.     

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.