Addition of sequences in general fields

IfX, Y are two finite subsets of a fieldL and the characteristic ofL is either 0 or is sufficiently large compared to the cardinalities ofX andY then there exists az L uniquely representable asx+y,xX,yY.Dedicated to Prof. Dr. E. Hlawka on the occasion of his 60th birthday     

On the average distance property and certain energy integrals

One of our main results is the following: LetX be a compact connected subset of the Euclidean spaceR ⁿ andr(X, d ₂) the rendezvous number ofX, whered ₂ denotes the Euclidean distance inR ⁿ . (The rendezvous numberr(X, d ₂) is the unique positive real number with the property that for each positive integern and for all (not necessarily distinct)x ₁,x ₂,...,x _n inX, there exists somex inX such that .) Then there exists some regular Borel probability measure μ₀ onX such that the value of ∫ _X d ₂(x, y)dμ₀ (y) is independent of the choicex inX, if and only ifr(X, d ₂) = sup_μ ∫ _X ∫ _X d ₂(x, y)dμ(x)dμ(y), where the supremum is taken over all regular Borel probability measures μ onX.     

An estimate for the region of regularity of solutions of certain nonlinear differential inequalities

In the diskx ²+y ²R ² of thex, y-plane we consider the differential inequalityz _xxz_yy–z _xy ² –(1+z _x ^/2 +z _y ^/2 )^k, where the constants >0 andk>1. In the case =1 andk=2 this inequality means that the surfacez(x, y) has Gaussian curvatureK1. Efimov has shown that in this case the radius of the disk has an upper bound. In the present article we establish an analogous upper bound for the radiusR of the disk in which the functionz(x, y) satisfies the differential inequality above.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 19–21.     

Convexity in finite metric spaces

A subsetS of a metric space (X,d) is calledd-convex if for any pair of pointsx,y S each pointz X withd(x,z) +d(z,y) =d(x,y) belongs toS. We give some results and open questions concerning isometric and convexity-preserving embeddings of finite metric spaces into standard spaces and the number ofd-convex sets of a finite metric space.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

Path-Connected Partially Ordered Sets

The graph of a partially ordered set (X, ?) has X as its set of vertices and (x,y) is an edge if and only if x covers y or y covers x. The poset is path-connected if its graph is connected. Two integer-valued metrics, distance and fence, are defined for path-connected posets. Together the values of these metrics determine a path-connected poset to within isomorphism and duality. The result holds for path-connected preordered sets where distance and fence are pseudometrics. The result fails for non-path-connected posets.     

Multifunctions of faces for conditional expectations of selectors and Jensen's inequality

Let (T, , P) be a probability space, a P-complete sub-δ-algebra of and X a Banach space. Let multifunction t → Γ(t), t T, have a (X)-measurable graph and closed convex subsets of X for values. If x(t) ε Γ(t) P-a.e. and y(·) ε E_p x(·), then y(t) ε Γ(t) P-a.e. Conversely, x(t) ε F(Γ(t), y(t)) P-a.e., where F(Γ(t), y(t)) is the face of point y(t) in Γ(t). If X = , then the same holds true if Γ(t) is Borel and convex, only. These results imply, in particular, extensions of Jensen's inequality for conditional expectations of random convex functions and provide a complete characterization of the cases when the equality holds in the extended Jensen inequality.     

Singular Perturbation Theory for a Class of Fredholm Integral Equations Arising in Random Fields Estimation Theory

A basic integral equation of random fields estimation theory by the criterion of minimum of variance of the estimation error is of the form Rh = f, where and R(x, y) is a covariance function.The singular perturbation problem we study consists of finding the asymptotic behavior of the solution to the equation as 0.$$" align="middle" border="0"> The domain D can be an interval or a domain in Rⁿ, n > 1. The class of operators R is defined by the class of their kernels R(x,y) which solve the equation Q(x, D_x)R(x, y) = P(x, D_x)δ(x − y), where Q(x, D_x) and Px, D_x) are elliptic differential operators.     

On the continuation of solutions for elliptic equations in two variables

We consider nonlinear elliptic differential equations of second order in two variables

Full-size image

. Supposing analyticity of F, we prove analyticity of the real solution z=z(x,y) in the open set Ω. Furthermore, we show that z may be continued as a real analytic solution for F=0 across the real analytic boundary arc Γ∂Ω, if z satisfies one of the boundary conditions z= or z_n=ψ(x,y,z,z_t) on Γ with real analytic functions and ψ, respectively (z_n denotes the derivative of z w.r.t. the outer normal n on Γ and z_t its derivative w.r.t. the tangent). The proof is based on ideas of H. Lewy combined with a uniformization method. Studying quasilinear equations, we get somewhat better results concerning the initial regularity of the given solution and a little more insight.     

Domination Graphs with Nontrivial Components

 A tournament is an oriented complete graph. Vertices x and y dominate a tournament T if for all vertices z≠x,y, either (x,z) or (y,z) are arcs in T (possibly both). The domination graph of a tournament T is the graph on the vertex set of T containing edge {x,y} if and only if x and y dominate T. In this paper we determine which graphs containing no isolated vertices are domination graphs of tournaments. Received: May 20, 1998 Final version received: May 26, 1999     

On First Range Times of Linear Diffusions

In this paper we consider first range times (with randomised range level) of a linear diffusion on R. Inspired by the observation that the exponentially randomised range time has the same law as a similarly randomised first exit time from an interval, we study a large family of non-negative 2-dimensional random variables (X,X′) with this property. The defining feature of the family is F^c(x,y)=F^c(x+y,0), ∀ x ≥ 0, y ≥ 0, where F^c(x,y):=P (X > x, X′ > y) We also explain the Markovian structure of the Brownian local time process when stopped at an exponentially randomised first range time. It is seen that squared Bessel processes with drift are serving hereby as a Markovian element.     

Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems

Summary This paper deals with rational functions ø(z) approximating the exponential function exp(z) related to numerical procedures for solving initial value problems. Motivated by positivity and contractivity requirements imposed on these numerical procedures we study the greatest nonnegative numberR, denoted byR(ø), such that ø is absolutely monotonic on (–R, 0]. An algorithm for the computation ofR(ø) is presented. Application of this algorithm yields the valueR(ø) for the well-known Padé approximations to exp(z). For some specific values ofm, n andp we determine the maximum ofR(ø) when ø varies over the class of all rational functions ø with degree of the numerator m, degree of the denominator n and ø(z)=exp(z)+(z ^p+1 ) (forz0).     

Simplex pivots on the set packing polytope

This paper considers the set packing problem max{wx: Ax b, x 0 and integral}, whereA is anm × n 0–1 matrix,w is a 1 ×n weight vector of real numbers andb is anm × 1 vector of ones. In equality form, its linear programming relaxation is max{wx: (x, y) P(A)} whereP(A) = {(x, y):Ax +I _m y =b, x0,y0}. Letx ¹ be any feasible solution to the set packing problem that is not optimal and lety ¹ =b – Ax ¹; then (x ¹,y ¹) is an integral extreme point ofP(A). We show that there exists a sequence of simplex pivots from (x ¹,y ¹) to (x*,y*), wherex* is an optimal solution to the set packing problem andy* =b – Ax*, that satisfies the following properties. Each pivot column has positive reduced weight and each pivot element equals plus one. The number of pivots equals the number of components ofx* that are nonbasic in (x ¹,y ¹).This research was supported by NSF Grants ECS-8005360 and ECS-8307473 to Cornell University.     

An implicit function theorem

Suppose thatF:DR ⁿ×R^mRⁿ, withF(x ⁰,y ⁰)=0. The classical implicit function theorem requires thatF is differentiable with respect tox and moreover that ₁ F(x ⁰,y ⁰) is nonsingular. We strengthen this theorem by removing the nonsingularity and differentiability requirements and by replacing them with a one-to-one condition onF as a function ofx.     

The reverse spelling of an FPrt-universal word in two letters

ForX a set the expression Prt(X) denotes the composition monoid of all functionsf X ×X. Fork a positive integer the letterk denotes also the set of all nonnegative integers less thank. Whenk > 1 the expression r_k denotes the connected injective element {<i, i + 1>i k – 1} in Prt (k). We show for every word w=w(x,y) in a two-letter alphabet that if the equation w(x, y)=r_k has a solution =y) ²Prt(k) then ¯w(x,y)=r_k also has a solution in²Prt(k), where ¯w is the word obtained by spelling the wordw backwards. It is a consequence of this theorem that if for every finite setX and for everyf Prt(X) the equation w(x,y)=f has a solution in²Prt(X) then for every suchX andf the equation ¯w(x, y)=f has a solution in²Prt(X).Presented by J. Mycielski.     

Frobenius-Perron operators and approximation of invariant measures for set-valued dynamical systems

A set-valued dynamical systemF on a Borel spaceX induces a set-valued operatorF onM(X) — the set of probability measures onX. We define arepresentation ofF, each of which induces an explicitly defined selection ofF; and use this to extend the notions of invariant measure and Frobenius-Perron operators to set-valued maps. We also extend a method ofS. Ulam to Markov finite approximations of invariant measures to the set-valued case and show how this leads to the approximation ofT-invariant measures for transformations , whereT corresponds to the closure of the graph of .     

Rational approximations for the cosine function; P-acceptability and order

Properties of order stars corresponding to rational approximations for cos z are derived and are used to prove that the order of accuracy of a P-acceptable approximantR _nm(z ²), with numerator of degreen and denominator of degreem, cannot exceed 2m. It is shown that if the poles ofR _nm(z ²) are restricted to pure-imaginary values ofz the maximum attainable order is 2n+2, whatever the value ofm1. A study of rational approximations for the cosine function produced by symmetric one-step collocation methods, applied to the differential equationy ⁿ =–² y, provides the answer to a question posed by Kramarz [BIT 20 (1980) 215–222]; there are no P-stable methods of that type.     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.     

Tree coloring of distance graphs with a real interval set

Let R be the set of real numbers and D be a subset of the positive real numbers. The distance graph G(R,D) is a graph with the vertex set R and two vertices x and y are adjacent if and only if |x−y|D. In this work, the vertex arboricity (i.e., the minimum number of subsets into which the vertex set V(G) can be partitioned so that each subset induces an acyclic subgraph) of G(R,D) is determined for D being an interval between 1 and δ.