Stability of a simple Levi–Civitá functional equation on non-unital commutative semigroups

In this paper, we study the Hyers–Ulam stability of a simple Levi–Civitá functional equation f(x+y)=f(x)h(y)+f(y) and its pexiderization f(x+y)= g(x) h(y)+k(y) on non-unital commutative semigroups by investigating the functional inequalities |f(x+y)?f(x)h(y)?f(y)|≤?? and |f(x+y)?g(x)h(y)?k(y)|≤??, respectively. We also study the bounded solutions of the simple Levi–Civitá functional inequality.     

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 γ.     

Hamming distance for conjugates

Let x,y be strings of equal length. The Hamming distanceh(x,y) between x and y is the number of positions in which x and y differ. If x is a cyclic shift of y, we say x and y are conjugates. We consider f(x,y), the Hamming distance between the conjugates xy and yx. Over a binary alphabet f(x,y) is always even, and must satisfy a further technical condition. By contrast, over an alphabet of size 3 or greater, f(x,y) can take any value between 0 and |x|+|y|, except 1; furthermore, we can always assume that the smaller string has only one type of letter.     

Repetition-free longest common subsequence

We study the following problem. Given two sequences x and y over a finite alphabet, find a repetition-free longest common subsequence of x and y. We show several algorithmic results, a computational complexity result, and we describe a preliminary experimental study based on the proposed algorithms. We also show that this problem is APX-hard.     

On the two-dimensional stationary Schrödinger equation with a singular potential

We study the equation

−△u(x,y)+ν(x,y)u(x,y)=0     

Nonexistence of Isochronous Centers in Planar Polynomial Hamiltonian Systems of Degree Four

In this paper we study centers of planar polynomial Hamiltonian systems and we are interested in the isochronous ones. We prove that every center of a polynomial Hamiltonian system of degree four (that is, with its homogeneous part of degree four not identically zero) is nonisochronous. The proof uses the geometric properties of the period annulus and it requires the study of the Hamiltonian systems associated to a Hamiltonian function of the form H(x, y)=A(x)+B(x) y+C(x) y²+D(x) y³.     

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)).     

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.     

Generalized Jordan algebras

We study commutative algebras which are generalizations of Jordan algebras. The associator is defined as usual by (x, y, z) = (x y)z − x(y z). The Jordan identity is (x², y, x) = 0. In the three generalizations given below, t, β, and γare scalars. ((x x)y)x + t((x x)x)y = 0, ((x x)x)(y x) − (((x x)x)y)x = 0, β((x x)y)x + γ((x x)x)y − (β + γ)((y x)x)x = 0. We show that with the exception of a few values of the parameters, the first implies both the second and the third. The first is equivalent to the combination of ((x x)x)x = 0 and the third. We give examples to show that our results are in some reasonable sense, the best possible.     

Variations on the Drygas equation and its stability

We study the stability of the Drygas functional equation:

g(xy)+g(xy⁻¹)=2g(x)+g(y)+g(y⁻¹)     

Applications of utility functions defined on quasi-metric spaces

A quasi-metric space (X,d) is called sup-separable if (X,d^s) is a separable metric space, where d^s(x,y)=max{d(x,y),d(y,x)} for all x,y∈X. We characterize those preferences, defined on a sup-separable quasi-metric space, for which there is a semi-Lipschitz utility function. We deduce from our results that several interesting examples of quasi-metric spaces which appear in different fields of theoretical computer science admit semi-Lipschitz utility functions. We also apply our methods to the study of certain kinds of dynamical systems defined on quasi-metric spaces.     

The Sprague-Grundy function of the game Euclid

We show that the Sprague-Grundy function of the game Euclid is given by g(x,y)=⌊|y/x-x/y|⌋ for x,y≥1.     

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.     

Analytic invariant curves for a planar map

In this paper, we study the existence of analytic invariant curves for two-dimensional maps of the form F(x,y) = (x + y, y + G(x) + H(x + y)).     

Score vectors of tournaments

A tournament T on any set X is a dyadic relation such that for any x, y ∈ X (a) (x, x) ? T and (b) if x ≠ y then (x, y) ∈ T iff (y, x) ? T. The score vector of T is the cardinal valued function defined by R(x) = |{y ∈ X : (x, y) ∈ T}|. We present theorems for infinite tournaments analogous to Landau's necessary and sufficient conditions that a vector be the score vector for some finite tournament. Included also is a new proof of Landau's theorem based on a simple application of the “marriage” theorem.     

On the Obstruction to Linearizability of Second-Order Ordinary Differential Equations

In this paper, we investigate the action of the pseudogroup of all point transformations on the bundle of equations y″=u ⁰(x,y)+u ¹(x,y)y′+u ²(x,y)(y′)²+u ³(x,y)(y′)³. We calculate the 1st nontrivial differential invariant of this action. It is a horizontal differential 2-form with values in some algebra, it is defined on the bundle of 2-jets of sections of the bundle under consideration. We prove that this form is a unique obstruction to linearizability of these equations by point transformations.     

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).     

Ideals and free Pairs in the semigroup β ℤ

We prove that the equations ξ+x=mξ+y, x+ξ=y+mξ have no solutions in the semigroup β ? for every free ultrafilter ξ and every integer m∈0, 1. We study semigroups generated by the ultrafilters ξ, mξ. For left maximal idempotents, we prove a reduced hypothesis about elements of finite order in β ?.     

Stability of the preservation of the equality of distance

We study the stability problem for mappings satisfying the equation

‖f(x−y)‖=‖f(x)−f(y)‖.     

A study of 3-arc graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v,u,x,y) of vertices such that both (v,u,x) and (u,x,y) are paths of length two. The 3-arc graph of a graph G is defined to have the arcs of G as vertices such that two arcs uv,xy are adjacent if and only if (v,u,x,y) is a 3-arc of G. In this paper, we study the independence, domination and chromatic numbers of 3-arc graphs and obtain sharp lower and upper bounds for them. We introduce a new notion of arc-coloring of a graph in studying vertex-colorings of 3-arc graphs.