Properties of the limit shape for some last-passage growth models in random environments

We study directed last-passage percolation on the planar square lattice whose weights have general distributions, or equivalently, queues in series with general service distributions. Each row of the last-passage model has its own randomly chosen weight distribution. We investigate the limiting time constant close to the boundary of the quadrant. Close to the y-axis, where the number of random distributions averaged over stays large, the limiting time constant takes the same universal form as in the homogeneous model. But close to the x-axis we see the effect of the tail of the distribution of the random environment.     

The central configurations of four masses x, −x, y, −y

The configuration of a homothetic motion in the N-body problem is called a central configuration. In this paper, we prove that there are exactly three planar non-collinear central configurations for masses x, −x, y, −y with x≠y (a parallelogram and two trapezoids) and two planar non-collinear central configurations for masses x, −x, x, −x (two diamonds). Except the case studied here, the only known case where the four-body central configurations with non-vanishing masses can be listed is the case with equal masses (A. Albouy, 1995-1996), which requires the use of a symbolic computation program. Thanks to a lemma used in the proof of our result, we also show that a co-circular four-body central configuration has non-vanishing total mass or vanishing multiplier.     

Latin square and intersection of surface

A technique is developed here to estimate an unknown curve joining two points in a three dimensional Euclidean space. A special application presented here is a computer procedure to determine the intersection of two arbitrary given smooth surfaces. The method used is to assume that y is a function of x and the set (x,y(x)) lies on the projection of the intersection of two surfaces. The function y is determined by least square curve fitting on a Latin square of experimental values. The procedure is written in APL (A Programming Language). A set of preliminary results is presented. The results indicate that this is a successful procedure for some simple surfaces, including some conic surfaces.     

On numerical representations of semiorders

Conditions on a semiorder, 〈X,≻〉 (where X is a subset of Euclidean space), are presented under which the semiorder can be represented by a continuous, real-valued function, u, along with a strictly positive scalar, δ. That is, for x,yϵX, x≻y if and only if u(x)>u(y)+δ. The results are related to existing results for numerical representations of interval orders.     

The condition on the stability of stationary lines in a curvature flow in the whole plane

The long time behavior of a curve in the whole plane moving by a curvature flow is studied. Studying the Cauchy problem, we deal with moving curves represented by entire graphs on the x-axis. Here the initial curves are given by bounded functions on the x-axis. It is proved that the solution converges uniformly to the solution of the Cauchy problem of the heat equation with the same initial value. The difference is of order O(t−1/2) as time goes to infinity. The proof is based on the decay estimates for the derivatives of the solution. By virtue of the stability results for the heat equation, our result gives the sufficient and necessary condition on the stability of constant solutions that represent stationary lines of the curvature flow in the whole plane.     

Clique or hole in claw-free graphs

Given a claw-free graph and two non-adjacent vertices x and y without common neighbours we prove that there exists a hole through x and y unless the graph contains the obvious obstruction, namely a clique separating x and y. We derive two applications: We give a necessary and sufficient condition for the existence of an induced x-z path through y, where x,y,z are prescribed vertices in a claw-free graph; and we prove an induced version of Menger?s theorem between four terminal vertices. Finally, we improve the running time for detecting a hole through x and y and for the Three-in-a-Tree problem, if the input graph is claw-free.     

The stochastic web on a spherical surface generated by simple, 3-dimensional rotational transformations

It is shown that the stochastic web (or chaotic web) on the surface of a sphere can be generated by a simple, 3-dimentional rotational map, constructed by three rotational angles about each coordinate axis: x-axis, y-axis and z-axis. It is remarkable that the rotational angles in our model do not need to be complicated functions of the coordinates. As a matter of fact, the stochastic web is found when our map only consists of one simple functional rotational angle and two constant rotational angles, under certain resonance conditions. The trajectories are computed and the 3-dimentional plots of the stochastic web on the spherical surface are also presented.     

On Gilmore-Gomory's open question for the bottleneck TSP

Consider the traveling salesman problem where the distance between two cities A and B is an integrable function of the y-coordinate of A and the x-coordinate of B. This problem finds important applications in operations management and combinatorial optimization. Gilmore and Gomory (Oper. Res. 12 (1964) 655) gave a polynomial time algorithm for this problem. In the bottleneck variant of this problem (BP), we seek a tour that minimizes the maximum distance between any two consecutive cities. For BP, Gilmore and Gomory state that they “do not yet know how to solve the problem for general integrable functions”. We show that BP is strongly NP-complete. Also, we use this reduction to provide a method for proving NP-completeness of other combinatorial problems.     

Dimension Reduction by Random Hyperplane Tessellations

Given a subset K of the unit Euclidean sphere, we estimate the minimal number m=m(K) of hyperplanes that generate a uniform tessellation of K, in the sense that the fraction of the hyperplanes separating any pair x,y∈K is nearly proportional to the Euclidean distance between x and y. Random hyperplanes prove to be almost ideal for this problem; they achieve the almost optimal bound m=O(w(K)²) where w(K) is the Gaussian mean width of K. Using the map that sends x∈K to the sign vector with respect to the hyperplanes, we conclude that every bounded subset K of $\mathbb{R}^{n}$ embeds into the Hamming cube {?1,1} ^m with a small distortion in the Gromov–Haussdorff metric. Since for many sets K one has m=m(K)?n, this yields a new discrete mechanism of dimension reduction for sets in Euclidean spaces.     

An inverse problem for computing a leading coefficient in the Sturm-Liouville operator by using the boundary data

We consider an inverse problem for identifying a leading coefficient α(x) in −(α(x)y′(x))′ + q(x)y(x) = H(x), which is known as an inverse coefficient problem for the Sturm-Liouville operator. We transform y(x) to u(x, t) =  (1 + t)y(x) and derive a parabolic type PDE in a fictitious time domain of t. Then we develop a Lie-group adaptive method (LGAM) to find the coefficient function α(x). When α(x) is a continuous function of x, we can identify it very well, by giving boundary data of y, y′ and α. The efficiency of LGAM is confirmed by comparing the numerical results with exact solutions. Although the data used in the identification are limited, we can provide a rather accurate solution of α(x).     

The diophantine equation x3 + 3y3 = 2n

It is proved that the equation of the title has a finite number of integral solutions (x, y, n) and necessary conditions are given for (x, y, n) in order that it can be a solution (Theorem 2). It is also proved that for a given odd x₀ there is at most one integral solution (y, n), n ≥ 3, to x₀³ + 3y³ = 2ⁿ and for a given odd y₀ there is at most one integral solution (x, n), n ≥ 3, to x³ + 3y₀³ = 2ⁿ.     

The complete solution in integers of x3 + 3y3 = 2n

Some general remarks are made concerning the equation f(x, y) = qⁿ in the integral unknowns x, y, n, where f is an integral form and q > 1 is a given integer. It is proved that the only integral triads (x, y, n) satisfying x³ + 3y³ = 2ⁿ are (x, y, n) = (?1, 1, 1), (1, 1, 2), (?7, 5, 5,), (5, 1, 7).     

On solvability of two-dimensional Lp-Minkowski problem

Given p≠0 and a positive continuous function g, with g(x+T)=g(x), for some 0<T<1 and all real x, it is shown that for suitable choice of a constant C>0 the functional has a minimizer in the class of positive functions u∈C¹(R) for which u(x+T)=u(x) for all x∈R. This minimizer is used to prove the existence of a positive periodic solution y∈C²(R) of two-dimensional L_p-Minkowski problem y^1−p(x)(y″(x)+y(x))=g(x), where p∉{0,2}.     

Exact number of local extreme points of curvature function of solutions of second-order linear differential equations

We study local properties of the curvature ?? _y (x) of every nontrivial solution y=y(x) of the second-order linear differential equation?(P): (p(x)y??)??+q(x)y=0, x??(a,b)=I, where p(x) and q(x) are smooth enough functions. It especially includes the Euler, Bessel and other important types of second-order linear differential equations. Some sufficient conditions on the coefficients p(x) and q(x) are given such that the curvature ?? _y (x) of every nontrivial solution y of (P) has exactly one extreme point between each two its consecutive simple zeros. The problem of three local extreme points of ?? _y (x) is also considered but only as an open problem. It seems it is the first paper dealing with this kind of problems. Finally in Appendix, we pay attention to an application of the main results to a study of non-regular points (the cusps) of the ??-parallels of graph ??(y) of?y (the offset curves of???(y)).     

Analysis of a singular functional differential equation that arises from stochastic modeling of population growth

The singular functional differential equation x(1 ? x)A(x)y′(x) + by(h(x)) ? by(x) = ?bg(x), x in (0, 1), is studied for initial data y = 0 on x ? a, y continuous on (a, 1) and y(1?) bounded. The singularity at x = 0+ is removable for a certain class of delayed arguments, h(x). The final end point at x = 1? is the most important singularity because it results in a genuine singular boundary value problem. A formal solution is constructed and is shown to be unique and bounded when g(x) is bounded. A singular decomposition transforms the problem into two nonsingular initial value problems. Singular FDEs of this type arise in the study of the persistence of populations undergoing large random fluctuations when modeled by compound Poisson processes superimposed on logistic-type growth.     

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.     

Periodic solutions to one-dimensional wave equation with x-dependent coefficients

In this paper, we study the nonlinear one-dimensional periodic wave equation with x-dependent coefficients u(x)ytt−(ux(x)yx)+g(x,t,y)=f(x,t) on (0,π)×R under the boundary conditions a₁y(0,t)+b₁yx(0,t)=0, a₂y(π,t)+b₂yx(π,t)=0 ( for i=1,2) and the periodic conditions y(x,t+T)=y(x,t), yt(x,t+T)=yt(x,t). Such a model arises from the forced vibrations of a nonhomogeneous string and the propagation of seismic waves in nonisotropic media. A main concept is the notion “weak solution” to be given in Section 2. For T is the rational multiple of π, we prove some important properties of the weak solution operator. Based on these properties, the existence and regularity of weak solutions are obtained.     

An optimal filtering method for stable analytic continuation

In this paper, we consider the problem of numerical analytic continuation of an analytic function f(z)=f(x+iy) on a strip domain Ω⁺={z=x+iy∈C∣x∈R,0<y<y₀}, where the data is given approximately only on the real axis y=0. This problem is severely ill-posed: the solution does not depend continuously on the given data. A novel method (filtering) is used to solve this problem and an optimal error estimate with Hölder type is proved. Numerical examples show that this method works effectively.     

Generalized stability of the Cauchy and the Jensen functional equations on spheres

We study a generalized stability problem for Cauchy and Jensen functional equations satisfied for all pairs of vectors x,y from a linear space such that γ(x)=γ(y) or γ(x+y)=γ(x−y) with a given function γ.     

A note on the time series which is the product of two stationary time series

The time series […,x_-1y_-1,x₀y₀,x₁y₁,…]> which is the product of two stationary time series x_t and y_t is studied. Such sequences arise in the study of nonlinear time series, censored time series, amplitude modulated time series, time series with random parameters, and time series with missing observations. The mean and autocovariance function of the product sequence are derived.