On the complexity of paths avoiding forbidden pairs

Given a graph G=(V,E), two fixed vertices s,t∈V and a set F of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs is to find a path from s to t that contains at most one vertex from each pair in F. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs.We write x?y if and only if there exists a path from x to y and we assume, without loss of generality, that for every forbidden pair (x,y)∈F we have x?y. The forbidden pairs have a halving structure if no two pairs (u,v),(x,y)∈F satisfy v?x or v=x and they have a hierarchical structure if no two pairs (u,v),(x,y)∈F satisfy u?x?v?y. We show that the PAFP problem is NP-hard even if the forbidden pairs have the halving structure and we provide a surprisingly simple and efficient algorithm for the PAFP problem with the hierarchical structure.     

Nil-Armendariz Rings Relative to a Monoid

For a monoid M, we introduce nil-Armendariz rings relative to M, which are a generalization of nil-Armendariz and M-Armendariz rings, and investigate their properties. First we show that semicommutative rings are nil-Armendariz relative to every unique product monoid M. Also it is shown that for a strictly totally ordered monoid M and an ideal I of R, if I is a semicommutative subrng of R and R/I nil-Armendariz relative to M, then R is nil-Armendariz relative to M. Then we show that if R is a semicommutative ring and nil-Armendariz relative to M, then R is nil-Armendariz relative to M × N, where N is a unique product monoid. As corollaries we obtain some results of [2] and [10].     

Edge-switching homomorphisms of edge-coloured graphs

An edge-coloured graph G is a vertex set V(G) together with m edge sets distinguished by m colours. Let π be a permutation on {1,2,…,m}. We define a switching operation consisting of π acting on the edge colours similar to Seidel switching, to switching classes as studied by Babai and Cameron, and to the pushing operation studied by Klostermeyer and MacGillivray. An edge-coloured graph G is π-permutably homomorphic (respectively π-permutably isomorphic) to an edge-coloured graph H if some sequence of switches on G produces an edge-coloured graph homomorphic (respectively isomorphic) to H. We study the π-homomorphism and π-isomorphism operations, relating them to homomorphisms and isomorphisms of a constructed edge-coloured graph that we introduce called a colour switching graph. Finally, we identify those edge-coloured graphs H with the property that G is homomorphic to H if and only if any switch of G is homomorphic to H. It turns out that such an H is precisely a colour switching graph. As a corollary to our work, we settle an open problem of Klostermeyer and MacGillivray.     

Strong approximation of quadrics and representations of quadratic forms

Let V be an indefinite quadratic space over a number field F and U be a nondegenerate subspace of V. Suppose that M is a lattice on V, and that N is a lattice on U which is represented by M locally everywhere. The main result of this paper is a necessary and sufficient condition for which there exists a representation of N by M that approximates a given family of local representations. This is applied to determine when the variety of representations of U by V has strong approximation with respect to a finite set of primes of F that contains all the archimedean primes.     

C(α) preserving operators on separable Banach spaces

Let T be a bounded linear operator from a separable Banach space X to a Banach space Y. A necessary and sufficient condition on T for the existence of a subspace Z of X such that Z is isomorphic to C(α) and the restriction of T to Z is an isomorphism is given. The special case where X is the disc algebra is then considered and results similar to those previously obtained by the author for C(K) spaces are obtained for the disc algebra. Finally some additional results of the same type are proved for subspaces of C(K) with small annihilator.     

Approximation algorithms for constructing some required structures in digraphs

We consider a new problem of constructing some required structures in digraphs, where all arcs installed in such required structures are supposed to be cut from some pieces of a specific material of length L. Formally, we consider the model: a digraph D = (V, A; w), a structure S and a specific material of length L, where w: A → R⁺, we are asked to construct a subdigraph D′ from D, having the structure S, such that each arc in D′ is constructed by a part of a piece or/and some whole pieces of such a specific material, the objective is to minimize the number of pieces of such a specific material to construct all arcs in D′.     

Inverses of Boolean matrices

For a Boolean matrix A, a g-inverse of A is a Boolean matrix G satisfying AGA=A, and a Vagner inverse is a g-inverse which in addition satisfies GAG=G. We give algorithms for finding all g-inverses, all Vagner inverses, and all of several other types of inverses including Moore-Penrose inverses. We give a criterion for a Boolean matrix to be regular, and criteria for the various types of inverse to exist. We count the numbers of Boolean matrices having Moore-Penrose and related types of inverses.     

Injectivity relative to closed submodules

Let R be a ring. An R-module X is called c-injective if, for every closed submodule L of every R-module M, every homomorphism from L to X lifts to M. It is proved that if R is a Dedekind domain then an R-module X is c-injective if and only if X is isomorphic to a direct product of homogeneous semisimple R-modules and injective R-modules. It is also proved that a commutative Noetherian domain R is Dedekind if and only if every simple R-module is c-injective.     

Time-varying minimum cost flow problems

In this paper, we study a minimum cost flow problem on a time-varying network. Let N(V,A,l,b,c_r,c_w) be a network with an arc set A and a vertex set V. Each a∈A is associated with three integer parameters: a positive transit time b(a,t), an arbitrary transit cost c_r(a,t), and a positive capacity limit l(a,t). Each x∈V is associated with two integer parameters: a waiting cost c_w(x,t) and a vertex capacity l(x,t). All these parameters are functions of the discrete time t=0,1,2,… The objective is to find an optimal schedule to send a flow from the origin (the source vertex) to its destination (the sink vertex) with the minimum cost, subject to the constraint that the flow must arrive at the destination before a deadline T. Three versions of the problem are examined, which are classified depending on whether waiting at the intermediate vertices of the network is strictly prohibited, arbitrarily allowed, or bounded. Three algorithms with pseudopolynomial time complexity are proposed, which can find optimal solutions to the three versions of the problem, respectively.     

Morita theory for coring extensions and cleft bicomodules

A Morita context is constructed for any comodule of a coring and, more generally, for an L-C bicomodule Σ for a coring extension (D:L) of (C:A). It is related to a 2-object subcategory of the category of k-linear functors MC→MD. Strictness of the Morita context is shown to imply the Galois property of Σ as a C-comodule and a Weak Structure Theorem. Sufficient conditions are found also for a Strong Structure Theorem to hold.Cleft property of an L-C bicomodule Σ—implying strictness of the associated Morita context—is introduced. It is shown to be equivalent to being a GaloisC-comodule and isomorphic to EndC(Σ)L_⊗D, in the category of left modules for the ring EndC(Σ) and right comodules for the coring D, i.e. satisfying the normal basis property.Algebra extensions, that are cleft extensions by a Hopf algebra, a coalgebra or a Hopf algebroid, as well as cleft entwining structures (over commutative or non-commutative base rings) and cleft weak entwining structures, are shown to provide examples of cleft bicomodules.     

Chords and disjoint paths in matroids

A chord of a circuit C of a matroid M on E is a cell e ? S\C such that C spans e. Menger's theorem gives necessary and sufficient conditions for a cell of a graphic matroid to be a chord of some circuit. We extend this result to a large class of matroids and find all minimal counterexamples. The theorem is used to obtain results on disjoint paths and to characterize a class of matroid sums.     

Direct iterative methods for least-squares solutions to singular operator equations

Least-squares consistency and convergence of iterative schemes are investigated for singular operator equations (1) Tx = f, where T is a bounded linear operator from a Banach space to a Hilbert space. A direct splitting of T into T = M ? N is then used to obtain the iterative formula (2) x^(k+1) = M^?Nx^(k) + M^?f, where M^? is a least-squares generalized inverse of M. Cone monotonicity is used to investigate convergence of (2) to a least-squares solutions to (1), extending results given for the matrix case given by Berman and Plemmons.     

Which trees are link graphs?

The link of a vertex v of a graph G is the subgraph induced by all vertices adjacent to v. If all the links of G are isomorphic to L, then G has constant link and L is called a link graph. We investigate the trees of order p≤9 to see which are link graphs. Group theoretic methods are used to obtain constructions of graphs G with constant link L for certain trees L. Necessary conditions are derived for the existence of a graph having a given graph L as its constant link. These conditions show that many trees are not link graphs. An example is given to show that a connected graph with constant link need not be point symmetric.     

Primes in the semigroup of Boolean matrices

Let A, B, C be n×n matrices of zeros and ones. Using Boolean addition and multiplication, we say that A is prime if it is not a permutation matrix and if A=BC implies that B or C must be a permutation matrix. Conditions sufficient for a matrix to be prime are provided, and a characterization of primes in terms of a nation of rank is given. Finally, an order property of primes is used to obtain a result on prime factors.     

An asymmetric Ellis theorem

In 1957 Robert Ellis proved that a group with a locally compact Hausdorff topology T making all translations continuous also has jointly continuous multiplication and continuous inversion, and is thus a topological group. The theorem does not apply to locally compact asymmetric spaces such as the reals with addition and the topology of upper open rays. We first show a bitopological Ellis theorem, and then introduce a generalization of locally compact Hausdorff, called locally skew compact, and a topological dual, Tk, to obtain the following asymmetric Ellis theorem which applies to the example above:Whenever (X,⋅,T) is a group with a locally skew compact topology making all translations continuous, then multiplication is jointly continuous in both (X,⋅,T) and (X,⋅,Tk), and inversion is a homeomorphism between (X,T) and (X,Tk).This generalizes the classical Ellis theorem, because T=Tk when (X,T) is locally compact Hausdorff.     

Groups of quasi-invariance and the Pontryagin duality

A Polish group G is called a group of quasi-invariance or a QI-group, if there exist a locally compact group X and a probability measure μ on X such that (1) there exists a continuous monomorphism ? from G into X with dense image, and (2) for each g∈X either g∈?(G) and the shift μg is equivalent to μ or g∉?(G) and μg is orthogonal to μ. It is proved that ?(G) is a σ-compact subset of X. We show that there exists a Polish non-locally quasi-convex (and hence nonreflexive) QI-group such that its bidual is not a QI-group. It is proved also that the bidual group of a QI-group may be not a saturated subgroup of X. It is constructed a reflexive non-discrete group topology on the integers.     

Extending equivariant maps into spaces with convex structure

We prove that if G is a compact Lie group, Y a G-space equipped with a topological local convex structure compatible with the action of G, then Y is a G-ANE for metrizable G-spaces. If, in addition, Y has a G-fixed point and admits a global convex structure compatible with the action of G, then Y is a G-AE. This is applied to show that certain hyperspaces related to the Banach–Mazur compacta are equivariant absolute extensors.     

Compatible extensions of nearrings

If R is a zero-symmetric nearring with 1 and G is a faithful R-module, a compatible extension of R is a subnearring S of M ₀(G) containing R such that G is a compatible S-module and the R-ideals and S-ideals of G coincide. The set of these compatible extensions forms a complete lattice and we shall study this lattice. We also will obtain results involving the least element of this lattice related to centralizers and the largest element of this lattice related to uniqueness of minimal factors with an application to 1-affine completeness of the R-module G.     

On realizations of point determining graphs, and obstructions to full homomorphisms

A graph is point determining if distinct vertices have distinct neighbourhoods. A realization of a point determining graph H is a point determining graph G such that each vertex-removed subgraph G-x which is point determining, is isomorphic to H. We study the fine structure of point determining graphs, and conclude that every point determining graph has at most two realizations.A full homomorphism of a graph G to a graph H is a vertex mapping f such that for distinct vertices u and v of G, we have uv an edge of G if and only if f(u)f(v) is an edge of H. For a fixed graph H, a full H-colouring of G is a full homomorphism of G to H. A minimal H-obstruction is a graph G which does not admit a full H-colouring, such that each proper induced subgraph of G admits a full H-colouring. We analyse minimal H-obstructions using our results on point determining graphs. We connect the two problems by proving that if H has k vertices, then a graph with k+1 vertices is a minimal H-obstruction if and only if it is a realization of H. We conclude that every minimal H-obstruction has at most k+1 vertices, and there are at most two minimal H-obstructions with k+1 vertices.We also consider full homomorphisms to graphs H in which loops are allowed. If H has ? loops and k vertices without loops, then every minimal H-obstruction has at most (k+1)(?+1) vertices, and, when both k and ? are positive, there is at most one minimal H-obstruction with (k+1)(?+1) vertices.In particular, this yields a finite forbidden subgraph characterization of full H-colourability, for any graph H with loops allowed.     

Nonarchimedean theta functions and the Néron symbol

Let k be a field complete with respect to a discrete valuation ν and G be the k-holomorphic space associated to a k-split algebraic torus. Let Γ be a discrete subgroup of maximal rank of the group of k-rational points of G; in case $\text{T =}\text{G}\text{Γ}$ is algebraizable, Cartier divisors on T are determined by k-meromorphic theta functions on G. Let E be a k-rational divisor on T, algebraically equivalent to zero, and a be a zero cycle on T such that all the components of a are k-rational. It is shown that the Néron local intersection symbol (E, a) can be calculated from the values of a k-meromorphic theta function associated to E.