Injective tests of low complexity in the plane

We study injective versions of the characterization of sets potentially in a Wadge class of Borel sets, for the first Borel and Lavrentieff classes. We also study the case of oriented graphs in terms of continuous homomorphisms, injective or not.     

Injective colorings of planar graphs with few colors

An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.     

Higher index theory for certain expanders and Gromov monster groups,I

In this paper, the first of a series of two, we continue the study of higher index theory for expanders. We prove that if a sequence of graphs is an expander and the girth of the graphs tends to infinity, then the coarse Baum–Connes assembly map is injective, but not surjective, for the associated metric space X.Expanders with this girth property are a necessary ingredient in the construction of the so-called ‘Gromov monster’ groups that (coarsely) contain expanders in their Cayley graphs. We use this connection to show that the Baum–Connes assembly map with certain coefficients is injective but not surjective for these groups. Using the results of the second paper in this series, we also show that the maximal Baum–Connes assembly map with these coefficients is an isomorphism.     

域上三角矩阵空间保幂等与立方幂等的加法单映射

本文刻划了特征不为2的域上三角矩阵空间保幂等加法单映射，并由此获得了特征不为2及3的域上三角矩阵空间保立方幂等加法单映射的形式．     

Simplicial embeddings between pants graphs

We prove that, except in some low-complexity cases, every locally injective simplicial map between pants graphs is induced by a π ₁-injective embedding between the corresponding surfaces.     

子立方无爪图的单射边色数至多为6

设$G$是一个图. 图$G$的一个单射边染色是指图$G$的一个边染色, 使得距离为$2$的两条边或者在同一个三角形中的两条边染不同的颜色. 图$G$的单射边色数是指图$G$的任意单射边染色所需要的最少颜色数. 关于单射边色数有一个猜想: 任意一个子立方图的单射边色数都不超过$6$. 在本文中, 我们证明了这个猜想对子立方无爪图是成立的, 并且给出图例说明上界$6$是紧的. 同时, 我们的证明隐含了求解这类图不超过$6$种颜色的单射边染色方案的一个线性时间算法.     

Manhattan orbifolds

We investigate a class of metrics for 2-manifolds in which, except for a discrete set of singular points, the metric is locally isometric to an L₁ (or equivalently L_∞) metric, and show that with certain additional conditions such metrics are injective. We use this construction to find the tight span of squaregraphs and related graphs, and we find an injective metric that approximates the distances in the hyperbolic plane analogously to the way the rectilinear metrics approximate the Euclidean distance.     

Weakly Regular and Self-Injective Leavitt Path Algebras Over Arbitrary Graphs

We characterize the Leavitt path algebras over arbitrary graphs which are weakly regular rings as well as those which are self-injective. In order to reach our goals we extend and prove several results on projective, injective and flat modules over Leavitt path algebras and, more generally, over (not necessarily unital) rings with local units.     

On the hyperbolic order

We define the hyperbolic order of any locally injective holomorphic function between arbitrary hyperbolic domains of the complex plane and study the relation between the hyperbolic order and the Schwarzian derivative for locally injective holomorphic functions from the unit disk into itself.     

The Conditions for Some Linear Partial Differential Equations to Be Solvable in G

Using Bargmann's transformation and some basic results of theory of analytic functions with several complex variables, we have disscussed two classes of LPDOs in this paper. We prove that each operator of one class of them is surjective both from G to G and from L² to L², but not injective, and each operator of another class is injective from G to G but not surjective. And in the letter case, the necessary and suffcient conditions for the corresponding equations to be solvable in G are given.     

The tensor product of function semimodules

Given two domains of functions with values in a field, the canonical map from the algebraic tensor product of the vector spaces of functions on the two domains to the vector space of functions on the product of the two domains is well known to be injective, but not generally surjective. By constructing explicit examples, we show that the corresponding map for semimodules of semiring-valued functions is in general not even injective. This impacts the formulation of topological quantum field theories over semirings. We also confirm the failure of surjectivity for functions with values in complete, additively idempotent semirings by describing a large family of functions that do not lie in the image.     

Additivity of the crossing number of graphs with connectivity 2

We prove that the crossing number of graphs with connectivity 2 has in certain cases an additive property analogous to that of crossing number of graphs with connectivity ≤1.     

On the computational complexity of partial covers of Theta graphs

By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths.     

Detour‐saturated graphs

A graph is said to be detour‐saturated if the addition of any edge results in an increased greatest path length. In this paper, we add to the relatively small amount that is known about detour‐saturated graphs. Our main result is a determination of all connected detour‐saturated graphs with exactly one cycle. (The family of detour‐saturated trees was found by Kászonyi and Tuza 7 .) We also show that the smallest detour‐saturated graph of girth 5 is the graph obtainable from the Petersen graph by splitting one of its vertices into three, each of degree 1. © 2005 Wiley Periodicals, Inc. J Graph Theory     

The algebra of set functions I: The product theorem and duality

We give a comprehensive introduction to the algebra of set functions and its generating functions. This algebraic tool allows us to formulate and prove a product theorem for the enumeration of functions of many different kinds, in particular injective functions, surjective functions, matchings and colourings of the vertices of a hypergraph. Moreover, we develop a general duality theory for counting functions.     

The Krull-Schmidt Theorem in the Case Two

We study what happens if, in the Krull-Schmidt Theorem, instead of considering modules whose endomorphism rings have one maximal ideal, we consider modules whose endomorphism rings have two maximal ideals. If a ring has exactly two maximal right ideals, then the two maximal right ideals are necessarily two-sided. We call such a ring of type 2. The behavior of direct sums of finitely many modules whose endomorphism rings have type 2 is completely described by a graph whose connected components are either complete graphs or complete bipartite graphs. The vertices of the graphs are ideals in a suitable full subcategory of Mod-R. The edges are isomorphism classes of modules. The complete bipartite graphs give rise to a behavior described by a Weak Krull-Schmidt Theorem. Such a behavior had been previously studied for the classes of uniserial modules, biuniform modules, cyclically presented modules over a local ring, kernels of morphisms between indecomposable injective modules, and couniformly presented modules. All these modules have endomorphism rings that are either local or of type 2. Here we present a general theory that includes all these cases.     

Gorenstein injective envelopes and covers over two sided noetherian rings

We prove that the class of Gorenstein injective modules is both enveloping and covering over a two sided noetherian ring such that the character modules of Gorenstein injective modules are Gorenstein flat. In the second part of the paper we consider the connection between the Gorenstein injective modules and the strongly cotorsion modules. We prove that when the ring R is commutative noetherian of finite Krull dimension, the class of Gorenstein injective modules coincides with that of strongly cotorsion modules if and only if the ring R is in fact Gorenstein.     

Colorings of plane graphs: A survey

After a brief historical account, a few simple structural theorems about plane graphs useful for coloring are stated, and two simple applications of discharging are given. Afterwards, the following types of proper colorings of plane graphs are discussed, both in their classical and choosability (list coloring) versions: simultaneous colorings of vertices, edges, and faces (in all possible combinations, including total coloring), edge-coloring, cyclic coloring (all vertices in any small face have different colors), 3-coloring, acyclic coloring (no 2-colored cycles), oriented coloring (homomorphism of directed graphs to small tournaments), a special case of circular coloring (the colors are points of a small cycle, and the colors of any two adjacent vertices must be nearly opposite on this cycle), 2-distance coloring (no 2-colored paths on three vertices), and star coloring (no 2-colored paths on four vertices). The only improper coloring discussed is injective coloring (any two vertices having a common neighbor should have distinct colors).     

Axiomatizability of the class of weakly injective <Emphasis Type="Italic">S</Emphasis>-acts

The concepts of weakly injective, fg-weakly injective, and p-weakly injective S-acts generalize that of injective S-act. We study the monoids S over which the classes of weakly injective, fg-weakly injective, and p-weakly injective S-acts are axiomatizable. We prove that the class of p-weakly injective S-acts over a regular monoid is axiomatizable.