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.     

An implicit function theorem: Comment

In Ref. 1, Jittorntrum proposed an implicit function theorem for a continuous mappingF:R ⁿ ×R ^m R ⁿ, withF(x ⁰,y ⁰)=0, that requires neither differentiability ofF nor nonsingularity of _x F(x ⁰,y ⁰). In the proof, the local one-to-one condition forF(·,y):A R ⁿ R ⁿ for ally B is consciously or unconsciously treated as implying thatF(·,y) mapsA one-to-one ontoF(A, y) for ally B, and the proof is not perfect. A proof can be given directly, and the theorem is shown to be the strongest, in the sense that the condition is truly if and only if.     

On functions with the cauchy difference bounded by a functional. III

We are going to discuss special cases of a conditional functional inequality

Asymptotic behavior of solutions for a class of retarded difference equations

Consider the retarded difference equationx _n −x _n−1 =F(−f(x _n )+g(x _n−k )), wherek is a positive integer,F,f,g:R→R are continuous,F andf are increasing onR, anduF(u)>0 for allu≠0. We show that whenf(y)≥g(y) (resp. f(y)≤g(y)) fory∈R, every solution of (*) tends to either a constant or −∞ (resp. ∞) asn→∞. Furthermore, iff(y)≡g(y) fory∈R, then every solution of (*) tends to a constant asn→∞. Project supported by NNSF (19601016) of China and NSF (97-37-42) of Hunan     

Multiplicative symmetry and related functional equations

Summary Let (G, *) be a commutative monoid. Following J. G. Dhombres, we shall say that a functionf: G G is multiplicative symmetric on (G, *) if it satisfies the functional equationf(x * f(y)) = f(y * f(x)) for allx, y inG. (1)Equivalently, iff: G G satisfies a functional equation of the following type:f(x * f(y)) = F(x, y) (x, y G), whereF: G × G G is a symmetric function (possibly depending onf), thenf is multiplicative symmetric on (G, *).In Section I, we recall the results obtained for various monoidsG by J. G. Dhombres and others concerning the functional equation (1) and some functional equations of the formf(x * f(y)) = F(x, y) (x, y G), (E) whereF: G × G G may depend onf. We complete these results, in particular in the case whereG is the field of complex numbers, and we generalize also some results by considering more general functionsF. In Section II, we consider some functional equations of the formf(x * f(y)) + f(y * f(x)) = 2F(x, y) (x, y K), where (K, +, ·) is a commutative field of characteristic zero, * is either + or · andF: K × K K is some symmetric function which has already been considered in Section I for the functional equation (E). We investigate here the following problem: which conditions guarantee that all solutionsf: K K of such equations are multiplicative symmetric either on (K, +) or on (K, ·)? Under such conditions, these equations are equivalent to some functional equations of the form (E) for which the solutions have been given in Section I. This is a partial answer to a question asked by J. G. Dhombres in 1973.     

Maximal plurisubharmonic functions and the polynomial hull of a completely circled fibration

LetX(-ϱB ^m ×C ⁿ be a compact set over the unit sphere ϱB ^m such that for eachz∈ϱB ^m the fiberX _z ={ω∈C ⁿ ;(z, ω)∈X} is the closure of a completely circled pseudoconvex domain inC ⁿ . The polynomial hull ofX is described in terms of the Perron-Bremermann function for the homogeneous defining function ofX. Moreover, for each point (z ₀,w ₀)∈Int there exists a smooth up to the boundary analytic discF:Δ→B ^m ×C ⁿ with the boundary inX such thatF(0)=(z ₀,w ₀). This work was supported in part by a grant from the Ministry of Science of the Republic of Slovenia.     

On the Cauchy difference on normed spaces

LetX be a real linear normed space, (G, +) be a topological group, andK be a discrete normal subgroup ofG. We prove that if a continuous at a point or measurable (in the sense specified later) functionf:X →G fulfils the condition:f(x +y) -f(x) -f(y) ∈K whenever ‖x‖ = ‖y‖, then, under some additional assumptions onG,K, andX, there esists a continuous additive functionA :X →G such thatf(x) -A(x) ∈K.     

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

If G is a connected graph of order n ⩾ 1, then by a hamiltonian coloring of G we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ⩾ n − 1 − D _G (x, y) (where D _G (x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ V (G). Let G be a connected graph. By the hamiltonian chromatic number of G we mean

Orthogonality and additivity modulo a subgroup

Summary LetE be a real inner product space of dimension at least 2,F a topological Abelian group, andK a discrete subgroup ofF. Assume also thatF is continuously divisible by 2 (that is, the functionu 2u is a homeomorphism ofF ontoF). Iff: E F fulfils the conditionf(x + y) – f(x) – f(y) K for all orthogonalx, y E and is continuous at the origin then there exist continuous additive functionsa: R F andA: E F such thatf(x) – a(x ²)– A(x) K for everyx E. Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

Functional characterization of Vasil’ev invariants

A cover of a manifold X is called an r-cover if any r points of X belong to a set in the cover. Let X and Y be two smooth manifolds, let Emb(X, Y) be the family of smooth embeddings X → Y, let M be an Abelian group, and let F: Emb(X, Y) → M be a functional. One says that the degree of F does not exceed r if for each finite open r-cover {U _i } _i∈I ; of X there exist functionals F _i : Emb(U _i , Y) → M, i ∈ I, such that for each a ∈ Emb(X, Y) one has

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.     

A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph

Let G be a graph and S ⊂ V(G). We denote by α(S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V(G), the local connectivity κ(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define . In this paper, we show that if κ(S) ≥ 3 and for every independent set {x ₁, x ₂, x ₃, x ₄} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian.     

On a generalization of the Cauchy functional equation

Summary While looking for solutions of some functional equations and systems of functional equations introduced by S. Midura and their generalizations, we came across the problem of solving the equationg(ax + by) = Ag(x) + Bg(y) + L(x, y) (1) in the class of functions mapping a non-empty subsetP of a linear spaceX over a commutative fieldK, satisfying the conditionaP + bP P, into a linear spaceY over a commutative fieldF, whereL: X × X Y is biadditive,a, b K\{0}, andA, B F\{0}. Theorem.Suppose that K is either R or C, F is of characteristic zero, there exist A ₁,A ₂,B ₁,B ₂, F\ {0}with L(ax, y) = A ₁ L(x, y), L(x, ay) = A ₂ L(x, y), L(bx, y) = B ₁ L(x, y), and L(x, by) = B ₂ L(x, y) for x, y X, and P has a non-empty convex and algebraically open subset. Then the functional equation (1)has a solution in the class of functions g: P Y iff the following two conditions hold: L(x, y) = L(y, x) for x, y X, (2)if L 0, then A ₁ =A ₂,B ₁ =B ₂,A = A ₁ ² ,and B = B ₁ ² . (3) Furthermore, if conditions (2)and (3)are valid, then a function g: P Y satisfies the equation (1)iff there exist a y ₀ Y and an additive function h: X Y such that if A + B 1, then y ₀ = 0;h(ax) = Ah(x), h(bx) =Bh(x) for x X; g(x) = h(x) + y ₀ + 1/2A ₁ ^-1 B ₁ ^-1 L(x, x)for x P.     

Partial Parity (g,f )-Factors and Subgraphs Covering Given Vertex Subsets

 Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg _F (x)≤f(x) for all x∈V(G) and deg _F (y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property. Received: June 14, 1999?Final version received: August 21, 2000     

Diameter and diametrical pairs of points in ultrametric spaces

Let F(X) be the set of finite nonempty subsets of a set X. We have found the necessary and sufficient conditions under which for a given function τ: F(X) → ℝ there is an ultrametric on X such that τ(A) = diamA for every A ∈ F(X). For finite nondegenerate ultrametric spaces (X, d) it is shown that X together with the subset of diametrical pairs of points of X forms a complete k-partite graph, k ⩾ 2, and, conversely, every finite complete k-partite graph with k ⩾ 2 can be obtained by this way. We use this result to characterize the finite ultrametric spaces (X, d) having the minimal card{(x, y): d(x, y) = diamX, x, y ∈ X} for given card X.     

Lipschitz selections of set-valued mappings and Helly’s theorem

We prove a Helly-type theorem for the family of all m-dimensional convex compact subsets of a Banach space X. The result is formulated in terms of Lipschitz selections of set-valued mappings from a metric space (M, ρ) into this family. Let M be finite and let F be such a mapping satisfying the following condition: for every subset M′ ⊂ M consisting of at most 2^m+1 points, the restriction F|_M′ of F to M′ has a selection f_M′ (i. e., f_M′(x) ∈ F(x) for all x ∈ M′) satisfying the Lipschitz condition ‖ƒ_M′(x) − ƒ_M′(y)‖_X ≤ ρ(x, y), x, y ∈ M′. Then F has a Lipschitz selection ƒ: M → X such that ‖ƒ(x) − ƒ(y)‖_X ≤ γρ(x,y), x, y ∈ M where γ is a constant depending only on m and the cardinality of M. We prove that in general, the upper bound of the number of points in M′, 2^m+1, is sharp. If dim X = 2, then the result is true for arbitrary (not necessarily finite) metric space. We apply this result to Whitney’s extension problem for spaces of smooth functions. In particular, we obtain a constructive necessary and sufficient condition for a function defined on a closed subset of R ² to be the restriction of a function from the Sobolev space W _∞ ² (R ²).A similar result is proved for the space of functions on R ² satisfying the Zygmund condition.     

Multigraphs with Δ ≥ 3 are Totally-(2Δ−1)-Choosable

The total graph T(G) of a multigraph G has as its vertices the set of edges and vertices of G and has an edge between two vertices if their corresponding elements are either adjacent or incident in G. We show that if G has maximum degree Δ(G), then T(G) is (2Δ(G) − 1)-choosable. We give a linear-time algorithm that produces such a coloring. The best previous general upper bound for Δ(G) > 3 was , by Borodin et al. When Δ(G) = 4, our algorithm gives a better upper bound. When Δ(G)∈{3,5,6}, our algorithm matches the best known bound. However, because our algorithm is significantly simpler, it runs in linear time (unlike the algorithm of Borodin et al.).