Disjoint matchings of graphs

In this paper, we prove a generalization of the familiar marriage theorem. One way of stating the marriage theorem is: Let G be a bipartite graph, with parts S₁ and S₂. If A ? S₁ and F(A) ? S₂ is the set of neighbors of points in A, then a matching of G exists if and only if Σ_x∈S2 min(1, | F^?1(x) ∩ A |) ≥ | A | for each A ? S₁. Our theorem is that k disjoint matchings of G exist if and only Σ_x∈S2 min (k, | F^?1(x) ∩ A |) ≥ k | A | for each A ? S₁.     

Sums and products with smooth numbers

We estimate the sizes of the sumset A+A and the productset A⋅A in the special case that A=S(x,y), the set of positive integers n?x free of prime factors exceeding y.     

Common best proximity points: global minimal solutions

Let us suppose that A and B are nonempty subsets of a metric space. Let S:A?B and T:A?B be nonself-mappings. Considering the fact S and T are nonself-mappings, it is feasible that the equations Sx=x and Tx=x have no common solution, designated as a common fixed point of the mappings S and T. Eventually, when the equations have no common solution, one contemplates to figure out an element x that is in close proximity to Sx and Tx in the sense that d(x,Sx) and d(x,Tx) are minimum. In fact, common best proximity point theorems scrutinize the existence of such optimal approximate solutions, known as common best proximity points, to the equations Sx=x and Tx=x in the event that the equations have no common solution. Further, one can perceive that the real-valued functions x?d(x,Sx) and x?d(x,Tx) estimate the magnitude of the error involved for any common approximate solution of the equations Sx=x and Tx=x. In light of the fact that the distance between x and Sx, and the distance between x and Tx are at least the distance between A and B for all x in A, a common best proximity point theorem ascertains global minimum of both functions x?d(x,Sx) and x?d(x,Tx) by limiting a common approximate solution of the equations Sx=x and Tx=x to fulfil the requirement that d(x,Sx)=d(A,B) and d(x,Tx)=d(A,B). This article discusses a common best proximity point theorem for a pair of nonself-mappings, one of which dominates the other proximally, thereby yielding common optimal approximate solutions of some fixed point equations when there is no common solution.     

Strong commutativity preserving maps in prime rings with involution

Let A be a prime ring of characteristic not 2, with center Z(A) and with involution *. Let S be the set of symmetric elements of A. Suppose that f:S→A is an additive map such that [f(x),f(y)]=[x,y] for all x,y∈S. Then unless A is an order in a 4-dimensional central simple algebra, there exists an additive map μ:S→Z(A) such that f(x)=x+μ(x) for all x∈S or f(x)=-x+μ(x) for all x∈S.     

On the nonsingular symmetric factors of a real matrix

For a given real square matrix A this paper describes the following matrices: (¹) all nonsingular real symmetric (r.s.) matrices S such that A = S^?1T for some symmetric matrix T.All the signatures (defined as the absolute value of the difference of the number of positive eigenvalues and the number of negative eigenvalues) possible for feasible S in (¹) can be derived from the real Jordan normal form of A. In particular, for any A there is always a nonsingular r.s. matrix S with signature S ? 1 such that A = S^?1T.     

Inheriting independence and chi-squaredness under certain matrix orderings

Let x ～ N(μ, Z), and let S = (Σ:μ). It is shown that if x′A₁x is independent of x′Bx (x′A₁x is distributed as a chi-square variable), then this property is inherited by every x′A₂x for which S′A₂S precedes S′A₁S with respect to the range preordering (with respect to the rank subtractivity partial ordering).     

Robust interpolation of random fields homogeneous in time and isotropic on a sphere,which are observed with noise

We study the problem of optimal linear estimation of the functional $$A_N \xi = \sum\limits_{k = 0}^{\rm N} {\int\limits_{S_n } {a(k,x)\xi (k,x)m_n (dx),} }$$ , which depends on unknown values of a random field ξ(k, x),k?Z,x?S _n homogeneous in time and isotropic on a sphereS _n, by observations of the field ξ(k,x)+η(k,x) with k? Z{0, 1, ...,N},x?S_n (here, η (k, x) is a random field uncorrelated with ξ(k, x), homogeneous in time, and isotropic on a sphere S_n). We obtain formulas for calculation of the mean square error and spectral characteristic of the optimal estimate of the functionalA _Nξ. The least favorable spectral densities and minimax (robust) spectral characteristics are found for optimal estimates of the functionalA _Nξ.     

Asymptotics for the logarithm of the number of (k, l)-sum-free sets in groups of prime order

The subset A of a group G is (k, l)-sum-free if x ₁ + ?? + x _k ? x _{k + 1} ? ?? ? x _k+l?1 does not belong to the set A for any x ₁, ??, x _k+l?1 ?? A. Asymptotics for the logarithm of the number of sets (k, l)-sum-free in groups of prime order is obtained.     

An algorithm for computing the hull of the solution set of interval linear equations

Described is a not-a-priori-exponential algorithm which for each n×n interval matrix A and for each interval n-vector in a finite number of steps either computes the interval hull of the solution set of the system of interval linear equations Ax=b, or finds a singular matrix S∈A.     

Independence for partition regular equations

A matrix A is said to be partition regular (PR) over a subset S of the positive integers if whenever S is finitely coloured, there exists a vector x, with all elements in the same colour class in S, which satisfies Ax=0. We also say that S is PR for A. Many of the classical theorems of Ramsey Theory, such as van der Waerden's theorem and Schur's theorem, may naturally be interpreted as statements about partition regularity. Those matrices which are partition regular over the positive integers were completely characterised by Rado in 1933.Given matrices A and B, we say that A Rado-dominates B if any set which is PR for A is also PR for B. One trivial way for this to happen is if every solution to Ax=0 actually contains a solution to By=0. Bergelson, Hindman and Leader conjectured that this is the only way in which one matrix can Rado-dominate another. In this paper, we prove this conjecture for the first interesting case, namely for 1×3 matrices. We also show that, surprisingly, the conjecture is not true in general.     

Generalized euler-type partition identities

Let A and S be subsets of the natural numbers. Let A′(n) be the number of partitions of n where each part appears exactly m times for some m?A. Let S(n) be the number of partitions of n into parts which are elements of S.     

Attainable sets for linear stochastic control systems

Let x_t^u(w) be the solution process of the n-dimensional stochastic differential equation dx_t^u = [A(t)x_t^u + B(t) u(t)] dt + C(t) dW_t, where A(t), B(t), C(t) are matrix functions, W_t is a n-dimensional Brownian motion and u is an admissable control function. For fixed ? ? 0 and 1 ? δ ? 0, we say that x?Rⁿ is (?, δ) attainable if there exists an admissable control u such that P{x_t^u?S_?(x)} ? δ, where S_?(x) is the closed ?-ball in Rⁿ centered at x. The set of all (?, δ) attainable points is denoted by $\text{A}$(t). In this paper, we derive various properties of $\text{A}$(t) in terms of K(t), the attainable set of the deterministic control system $\text{x}\text{?}\text{= A(t)x + B(t)u}$. As well a stochastic bang-bang principle is established and three examples presented.     

Tensor products and preservation of limits, for acts over monoids

In 1971, Stenström published one of the first papers devoted to the problem of when, for a monoid S and a right S -act A _S , the functor A? (from the category of left acts over S into the category of sets) has certain limit preservation properties. Attention at first focused on when this functor preserves pullbacks and equalizers but, since that time, a large number of related articles have appeared, most having to do with when this functor preserves monomorphisms of various kinds. All of these properties are often referred to as flatness properties of acts . Surprisingly, little attention has so far been paid to the obvious questions of when A _S ? preserves all limits, all finite limits, all products, or all finite products. The present article addresses these matters.     

The operator-valued Feynman-Kac formula with noncommutative operators

Let X(t) be a right-continuous Markov process with state space E whose expectation semigroup S(t), given by S(t) φ(x) = E_x[φ(X(t))] for functions φ mapping E into a Banach space L, has the infinitesimal generator A. For each x?E, let V(x) generate a strongly continuous semigroup T_x(t) on L. An operator-valued Feynman-Kac formula is developed and solutions of the initial value problem $\text{?u}\text{?t}\text{= Au + V(x)u, u(0) = φ}$ are obtained. Fewer conditions are assumed than in known results; in particular, the semigroups {T_x(t)} need not commute, nor must they be contractions. Evolution equation theory is used to develop a multiplicative operative functional and the corresponding expectation semigroup has the infinitesimal generator A + V(x) on a restriction of the domain of A.     

Necessary and sufficient conditions for stability of effectivity functions

An effectivity functionE assigns to every coalitionS of players a familyE (S) of subsetsB of an outcome setA such thatS can force the outcome to belong to any of the setsB inE (S). The effectivity functionE is stable if for every preference profile there is an outcomex with the property that there is no coalitionS and subsetB ofA such thatB εE (S) and each player inS prefers everyy εB tox. The paper gives a necessary and sufficient condition for an effectivity function to be stable.     

A rank characterization of the number of final classes of a nonnegative matrix

Let A be a nonnegative square matrix, and let D be a diagonal matrix whose iith element is $\text{(Ax)}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}$, where x is a (fixed) positive vector. It is shown that the number of final classes of A equals n?rank(A?D). We also show that null(A?D) = null(A?D)², and that this subspace is spanned by a set of nonnegative elements. Our proof uses a characterization of nonnegative matrices having a positive eigenvector corresponding to their spectral radius.     

On a problem of Katona on minimal separating systems

Let S be an n-element set. In this paper, we determine the smallest number f(n) for which there exists a family of subsets of S{A₁,A₂,…,A_f(n)} with the following property: Given any two elements x, y ∈ S (x ≠ y), there exist k, l such that A_k ∩ A_l= ?, and x ∈ A_k, y ∈ A_l. In particular it is shown that f(n)= 3 log₃n when n is a power of 3.     

Viscosity approximation methods for nonexpansive mappings and inverse-strongly monotone mappings in Hilbert spaces

Let C be a closed convex subset of a Hilbert space H. Let f is a contraction on C. Let S be a nonexpansive mapping of C into itself and A be an α-inverse-strongly monotone mapping of C into H. Assuming that F(S)∩VI(C,A)≠φ, and x ₀=x∈C, in this paper we introduce the iterative process x _n+1=α _n f(x _n )+β _n x _n +γ _n (μ Sx _n +(1?μ)(P _C (I?λ _n A)y _n )), where y _n =P _C (I?λ _n A)x _n . We prove that {x _n } and {y _n } converge strongly to the same point z∈F(S)∩VI(C,A). As its application, we give a strong convergence theorem for nonexpansive mapping and strictly pseudo-contractive mapping in a Hilbert space.     

A condition for the strong regularity of matrices in the minimax algebra

Columns of a matrix A in the minimax algebra are called strongly linearly independent if for some b the system of equations A?x = b is uniquely solvable (cf. [3]). This paper presents a condition which is necessary and sufficient for the strong linear independence of columns of a given matrix in the minimax algebra based on a dense linearly ordered commutative group. In the case of square matrices an O(n³) method for checking this property as well as for finding at least one b such that A?x = b is uniquely solvable is derived. A connection with the classical assignment problem is formulated.     

Overdetermined linear systems satisfying nonnegativity constraints

Let A be a nonnegative m × n matrix, and let b be a nonnegative vector of dimension m. Also, let S be a subspace of $\text{R}$ⁿ such that if P_S is the orthogonal projector onto S, then P_S ? 0. A necessary condition is given for the matrix A to satisfy the following property: For all b ? 0, if min[boxV]b ? Ax[boxV] is attained at x = x₀, then x₀ ? 0 and x₀ ? S. It is also shown that if a nonnegative matrix A has a nonnegative generalized inverse, then any submatrix of A also possesses a nonnegative generalized inverse.