Rate of convergence in a class of singular perturbations

Let V_?, W_?, W and X be Hilbert spaces (0 < ? ? 1) with V_? ? W_? ? W ? X algebraically and topologically, each space being dense in the one that follows it. For each t? [0, T] let a_?(t; u, v), b_?(t; u, v) and b(t; u, v) be continuous sesqui-linear forms on V_?, W_? and W, respectively, which satisfy certain ellipticity conditions. Consider the two equations a_?(t; u_?, v) + b_?(t; u_?, v) = 〈f_?, v〉 (v?V_?) and (u′, v)_x + b(t; u, v) = 〈f, v〉 (v?W). Estimates are obtained on the rate of convergence of u_? to u, assuming a_?(t; u, v) → (u, v)_x and b_?(t; u, v) → b(t; u, v) in an appropriate sense. These results are then applied to singular perturbation of a class of parabolic boundary value problems.     

Minimal prime ideals of skew polynomial rings and near pseudo-valuation rings

Let R be a ring. We recall that R is called a near pseudo-valuation ring if every minimal prime ideal of R is strongly prime. Let now σ be an automorphism of R and δ a σ-derivation of R. Then R is said to be an almost δ-divided ring if every minimal prime ideal of R is δ-divided. Let R be a Noetherian ring which is also an algebra over ? (? is the field of rational numbers). Let σ be an automorphism of R such that R is a σ(*)-ring and δ a σ-derivation of R such that σ(δ(a)) = δ(σ(a)) for all a ∈ R. Further, if for any strongly prime ideal U of R with σ(U) = U and δ(U) ? δ, U[x; σ, δ] is a strongly prime ideal of R[x; σ, δ], then we prove the following:

1. R is a near pseudo valuation ring if and only if the Ore extension R[x; σ, δ] is a near pseudo valuation ring.
2. R is an almost δ-divided ring if and only if R[x; σ, δ] is an almost δ-divided ring.

     

The fractional chromatic number, the Hall ratio, and the lexicographic product

Let χ_f denote the fractional chromatic number and ρ the Hall ratio, and let the lexicographic product of G and H be denoted GlexH. Main results: (i) ρ(GlexH)≤χ_f(G)ρ(H); (ii) if ρ(G)=χ_f(G) then ρ(GlexH)=ρ(G)ρ(H) for all H; (iii) χ_f−ρ is unbounded. In addition, the question of how big χ_f/ρ can be is discussed.     

Some permutation problems

Put Z_n = {1, 2,…, n} and let π denote an arbitrary permutation of Z_n. Problem I. Let π = (π(1), π(2), …, π(n)). π has an up, down, or fixed point at a according as a < π(a), a > π(a), or a = π(a). Let $\text{A}\text{(r, s, t)}$ be the number of π ∈ Z_n with r ups, s downs, and t fixed points. Problem II. Consider the triple π^?1(a), a, π(a). Let R denote an up and F a down of π and let B(n, r, s) denote the number of π ∈ Z_n with r occurrences of π^?1(a)RaRπ(a) and s occurrences of π^?1(a)FaFπ(a). Generating functions are obtained for each enumerant as well as for a refinement of the second. In each case use is made of the cycle structure of permutations.     

On the computation of the hull number of a graph

Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted I_h[S], is the smallest convex set containing S. A set S is a hull set of G if I_h[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.     

Some representations of solutions of elliptic equations

The Dirichlet problem for the region of the plane inside closed smooth curve C for second-order elliptic equations is considered. It is shown that under certain circumstances the solution u can be written uniquely in the form u(P) = ∝_cF(P, Q) g(Q) ds_Q, where F(P, Q) is the fundamental solution of the elliptic equation, and g?L² if the boundary value function f is absolutely continuous with square integrable derivative (f?W); and u(P) = p(F(P, ·)) where p is a unique bounded linear functional on W if f?L². These representations are valid in the exterior of C also. As special cases with slight modifications, the exterior Dirichlet problems for the Helmholtz and Laplace equations are mentioned.It is shown also that if kernel F(P′, Q), with P′ and Q on C, has a complete set of eigenfunctions {ψ_k(P′)} then u(P) can be expanded in a series of their extensions {ψ_k(P)}, where ψ_k(P) = λ_k ∝_cF(P, Q) ψ_k(Q) ds_Q.     

A note on k-potence preserving maps

Let M_n be the algebra of all n×n complex matrices and Γ_n the set of all k-potent matrices in M_n. Suppose ?:M_n→M_n is a map satisfying A-λB∈Γ_n implies ?(A)-λ?(B)∈Γ_n, where A, B∈M_n, λ∈C. Then either ? is of the form ?(A)=cTAT^-1, A∈M_n, or ? is of the form ?(A)=cTA^tT^-1, A∈M_n, where T∈M_n is an invertible matrix, c∈C satisfies c^k=c.     

The Connected Monophonic Number of a Graph

For a connected graph G = (V, E) of order at least two, a chord of a path P is an edge joining two non-adjacent vertices of P. A path P is called a monophonic path if it is a chordless path. A set S of vertices of G is a monophonic set of G if each vertex v of G lies on an x ? y monophonic path for some elements x and y in S. The minimum cardinality of a monophonic set of G is defined as the monophonic number of G, denoted by m(G). A connected monophonic set of G is a monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected monophonic set of G is the connected monophonic number of G and is denoted by m _c (G). We determine bounds for it and characterize graphs which realize these bounds. For any two vertices u and v in G, the monophonic distance d _m (u, v) from u to v is defined as the length of a longest u ? v monophonic path in G. The monophonic eccentricity e _m (v) of a vertex v in G is the maximum monophonic distance from v to a vertex of G. The monophonic radius rad _m G of G is the minimum monophonic eccentricity among the vertices of G, while the monophonic diameter diam _m G of G is the maximum monophonic eccentricity among the vertices of G. It is shown that for positive integers r, d and n ≥ 5 with r <  d, there exists a connected graph G with rad _m G =  r, diam _m G =  d and m _c (G) =  n. Also, if a,b and p are positive integers such that 2 ≤  a <  b ≤  p, then there exists a connected graph G of order p, m(G) =  a and m _c (G) =  b.     

[r,s,t]-Coloring of K n,n

Let G=(V(G),E(G)) be a simple graph. Given non-negative integers r,s, and t, an [r,s,t]-coloring of G is a mapping c from V(G)∪E(G) to the color set {0,1,…,k?1} such that |c(v _i )?c(v _j )|≥r for every two adjacent vertices v _i ,v _j , |c(e _i )?c(e _j )|≥s for every two adjacent edges e _i ,e _j , and |c(v _i )?c(e _j )|≥t for all pairs of incident vertices and edges, respectively. The [r,s,t]-chromatic number χ _r,s,t (G) of G is defined to be the minimum k such that G admits an [r,s,t]-coloring. We determine χ _r,s,t (K _n,n ) in all cases.     

Weak solution of (r, (x, u(x)) u′(x))′ = (Fu)′(x) with r(0, u(0))u′(0) = ku(0), r(L, u(L))u′ (L) = hu(L) and k, h are suitable elements of [0, ∞]

We consider weak solutions to the nonlinear boundary value problem (r, (x, u(x)) u′(x))′ = (Fu)′(x) with r(0, u(0)) u′(0) = ku(0), r(L, u(L)) u′(L) = hu(L) and k, h are suitable elements of [0, ∞]. In addition to studying some new boundary conditions, we also relax the constraints on r(x, u) and (Fu)(x). r(x, u) > 0 may have a countable set of jump discontinuities in u and r(x, u)^?1?L_q((0, L) × (0, p)). F is an operator from a suitable set of functions to a subset of L_p(0, L) which have nonnegative values. F includes, among others, examples of the form (Fu)(x) = (1 ? H(x ? x₀)) u(x₀), (Fu)(x) = ∫_x^Lf(y, u(y)) dy where f(y, u) may have a countable set of jump discontinuities in u or F may be chosen so that (Fu)′(x) = ? g(x, u(x)) u′(x) ? q(x) u(x) ? f(x, u(x)) where q is a distributional derivative of an L₂(0, L) function.     

Mrówka maximal almost disjoint families for uncountable cardinals

We consider generalizations of a well-known class of spaces, called by S. Mrówka, N∪R, where R is an infinite maximal almost disjoint family (MADF) of countable subsets of the natural numbers N. We denote these generalizations by ψ=ψ(κ,R) for κ?ω. Mrówka proved the interesting theorem that there exists an R such that |βψ(ω,R)?ψ(ω,R)|=1. In other words there is a unique free z-ultrafilter p₀ on the space ψ. We extend this result of Mrówka to uncountable cardinals. We show that for κ?c, Mrówka's MADF R can be used to produce a MADF M⊂ω[κ] such that |βψ(κ,M)?ψ(κ,M)|=1. For κ>c, and every M⊂ω[κ], it is always the case that |βψ(κ,M)?ψ(κ,M)|≠1, yet there exists a special free z-ultrafilter p on ψ(κ,M) retaining some of the properties of p₀. In particular both p and p₀ have a clopen local base in βψ (although βψ(κ,M) need not be zero-dimensional). A result for κ>c, that does not apply to p₀, is that for certain κ>c, p is a P-point in βψ.     

Higher rank numerical ranges and low rank perturbations of quantum channels

For a positive integer k, the rank-k numerical range Λk(A) of an operator A acting on a Hilbert space H of dimension at least k is the set of scalars λ such that PAP=λP for some rank k orthogonal projection P. In this paper, a close connection between low rank perturbation of an operator A and Λk(A) is established. In particular, for 1?r<k it is shown that Λk(A)⊆Λk−r(A+F) for any operator F with rank(F)?r. In quantum computing, this result implies that a quantum channel with a k-dimensional error correcting code under a perturbation of rank at most r will still have a (k−r)-dimensional error correcting code. Moreover, it is shown that if A is normal or if the dimension of A is finite, then Λk(A) can be obtained as the intersection of Λk−r(A+F) for a collection of rank r operators F. Examples are given to show that the result fails if A is a general operator. The closure and the interior of the convex set Λk(A) are completely determined. Analogous results are obtained for Λ_∞(A) defined as the set of scalars λ such that PAP=λP for an infinite rank orthogonal projection P. It is shown that Λ_∞(A) is the intersection of all Λk(A) for k=1,2,…. If A−μI is not compact for all μ∈C, then the closure and the interior of Λ_∞(A) coincide with those of the essential numerical range of A. The situation for the special case when A−μI is compact for some μ∈C is also studied.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Diameter-girth sufficient conditions for optimal extraconnectivity in graphs

For a connected graph G, the rth extraconnectivity κ_r(G) is defined as the minimum cardinality of a cutset X such that all remaining components after the deletion of the vertices of X have at least r+1 vertices. The standard connectivity and superconnectivity correspond to κ₀(G) and κ₁(G), respectively. The minimum r-tree degree of G, denoted by ξ_r(G), is the minimum cardinality of N(T) taken over all trees T⊆G of order |V(T)|=r+1, N(T) being the set of vertices not in T that are neighbors of some vertex of T. When r=1, any such considered tree is just an edge of G. Then, ξ₁(G) is equal to the so-called minimum edge-degree of G, defined as ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, where d(u) stands for the degree of vertex u. A graph G is said to be optimally r-extraconnected, for short κ_r-optimal, if κ_r(G)?ξ_r(G). In this paper, we present some sufficient conditions that guarantee κ_r(G)?ξ_r(G) for r?2. These results improve some previous related ones, and can be seen as a complement of some others which were obtained by the authors for r=1.     

Coincidences of projections and linear n-valued maps of tori

We prove that the Nielsen fixed point number N(φ) of an n-valued map φ:X?X of a compact connected triangulated orientable q-manifold without boundary is equal to the Nielsen coincidence number of the projections of the graph of φ, a subset of X×X, to the two factors. For certain q×q integer matrices A, there exist “linear” n-valued maps Φn,A,σ:Tq?Tq of q-tori that generalize the single-valued maps fA:Tq→Tq induced by the linear transformations TA:Rq→Rq defined by TA(v)=Av. By calculating the Nielsen coincidence number of the projections of its graph, we calculate N(Φn,A,σ) for a large class of linear n-valued maps.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

On the spanning connectivity of graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if it contains all vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. The spanning connectivity of G, κ^*(G), is defined to be the largest integer k such that G is w^*-connected for all 1?w?k if G is a 1^*-connected graph. In this paper, we prove that κ^*(G)?2δ(G)-n(G)+2 if (n(G)/2)+1?δ(G)?n(G)-2. Furthermore, we prove that κ^*(G-T)?2δ(G)-n(G)+2-|T| if T is a vertex subset with |T|?2δ(G)-n(G)-1.     

Galois Groups of Generalized Iterates of Generic Vectorial Polynomials

Let q=p^u>1 be a power of a prime p, and let k_q be an overfield of GF(q). Let m>0 be an integer, let J^* be a subset of {1,…,m}, and let E^*_{m, q}(Y)=Y^qm+∑_j∈J^*X_jY^qm−j where the X_j are indeterminates. Let J³ be the set of all m−ν where ν is either 0 or a divisor of m different from m. Let s(T)=∑_0≤i≤ns_iTⁱ be an irreducible polynomial of degree n>0 in T with coefficients s_i in GF(q). Let E^*[s]_{m, q}(Y) be the generalized sth iterate of E^*_{m, q}(Y); i.e., E^*[s]_{m, q}(Y)=∑_0≤i≤ns_iE^*[i]_{m, q}(Y), where E^*[i]_{m, q}(Y), is the ordinary ith iterate. We prove that if J³⊂J^*, m is square-free, and GCD(m,n)=1=GCD(mnu,2p), then Gal(E^*[s]_{m, q},k_q({X_j:j∈j^*})=GL(m, qⁿ). The proof is based on CT (=the Classification Theorem of Finite Simple Groups) in its incarnation as CPT (=the Classification of Projectively Transitive Permutation Groups, i.e., subgroups of GL acting transitively on nonzero vectors).     

Generalized vector-valued paranormed sequence space using modulus function

In this paper we introduce a generalized vector-valued paranormed sequence space N_p(E_k,Δ^m,f,s) using modulus function f, where p=(p_k) is a bounded sequence of positive real numbers such that inf_kp_k>0,(E_k,q_k) is a sequence of seminormed spaces with E_k+1⊆E_k for each k ∈ N and s?0. We have also studied sequence space N_p(E_k,Δ^m,f^r,s), where f^r=f°f°f°,…,f (r-times composition of f with itself) and r∈N={1,2,3,…}. Results regarding completeness, K-space, normality, inclusion relations etc. are derived. Further, a study of multiplier of the set N_p(E_k,f,s) is also made by choosing (E_k,‖·‖_k) as sequence of normed algebras.     

A closure concept in factor-critical graphs

A graph G is called n-factor-critical if the removal of every set of n vertices results in a~graph with a~1-factor. We prove the following theorem: Let G be a~graph and let x be a~locally n-connected vertex. Let {u,v} be a~pair of vertices in V(G)−{x} such that uv∉E(G), x∈N_G(u)∩N_G(v), and N_G(x)⊂N_G(u)∪N_G(v)∪{u,v}. Then G is n-factor-critical if and only if G+uv is n-factor-critical.