On Bernstein–Markov-type inequalities for multivariate polynomials in -norm

Bernstein–Markov-type inequalities provide estimates for the norms of derivatives of algebraic and trigonometric polynomials. They play an important role in Approximation Theory since they are widely used for verifying inverse theorems of approximation. In the past decades these inequalities were extended to the multivariate setting, but the main emphasis so far was on the uniform norm. It is considerably harder to derive Bernstein–Markov-type inequalities in the L_q-norm, and it requires introduction of new methods. In this paper we verify certain Bernstein–Markov-type inequalities in L_q-norm on convex and star-like domains. Special attention is given to the question of how the geometry of the domain affects the corresponding estimates.     

On a signless Laplacian spectral characterization of -shape trees

Let M be an associated matrix of a graph G (the adjacency, Laplacian and signless Laplacian matrix). Two graphs are said to be cospectral with respect to M if they have the same M spectrum. A graph is said to be determined by M spectrum if there is no other non-isomorphic graph with the same spectrum with respect to M. It is shown that T-shape trees are determined by their Laplacian spectra. Moreover among them those are determined by their adjacency spectra are characterized. In this paper, we identify graphs which are cospectral to a given T-shape tree with respect to the signless Laplacian matrix. Subsequently, T-shape trees which are determined by their signless Laplacian spectra are identified.     

An iterative algorithm based on -proximal mappings for a system of generalized implicit variational inclusions in Banach spaces

In this paper, we give the notion of M-proximal mapping, an extension of P-proximal mapping given in [X.P. Ding, F.Q. Xia, A new class of completely generalized quasi-variational inclusions in Banach spaces, J. Comput. Appl. Math. 147 (2002) 369–383], for a nonconvex, proper, lower semicontinuous and subdifferentiable functional on Banach space and prove its existence and Lipschitz continuity. Further, we consider a system of generalized implicit variational inclusions in Banach spaces and show its equivalence with a system of implicit Wiener–Hopf equations using the concept of M-proximal mappings. Using this equivalence, we propose a new iterative algorithm for the system of generalized implicit variational inclusions. Furthermore, we prove the existence of solution of the system of generalized implicit variational inclusions and discuss the convergence and stability analysis of the iterative algorithm.     

Robust stabilization for uncertain switched impulsive control systems with state delay: An LMI approach

This paper deals with the problem of robust H_∞ state feedback stabilization for uncertain switched linear systems with state delay. The system under consideration involves time delay in the state, parameter uncertainties and nonlinear uncertainties. The parameter uncertainties are norm-bounded time-varying uncertainties which enter all the state matrices. The nonlinear uncertainties meet with the linear growth condition. In addition, the impulsive behavior is introduced into the given switched system, which results a novel class of hybrid and switched systems called switched impulsive control systems. Using the switched Lyapunov function approach, some sufficient conditions are developed to ensure the globally robust asymptotic stability and robust H_∞ disturbance attenuation performance in terms of certain linear matrix inequalities (LMIs). Not only the robustly stabilizing state feedback H_∞ controller and impulsive controller, but also the stabilizing switching law can be constructed by using the corresponding feasible solution to the LMIs. Finally, the effectiveness of the algorithms is illustrated with an example.     

Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size

Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an “almost uniform” partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph; the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l,u)-partition with a fixed number p of components. All these problems are NP-complete or NP-hard, respectively, even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u⁴n) and the p-partition problem can be solved in time O(p²u⁴n) for any series-parallel graph with n vertices. The algorithms can be extended for partial k-trees, that is, graphs with bounded tree-width.     

The binding number of a graph and its cliques

We consider the binding numbers of K_r-free graphs, and improve the upper bounds on the binding number which force a graph to contain a clique of order r. For the case r=4, we provide a construction for K₄-free graphs which have a larger binding number than the previously known constructions. This leads to a counterexample to a conjecture by Caro regarding the neighborhoods of independent sets.     

Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, W₄, bull}-free, both superclasses of triangle-free graphs.     

On Rockafellar’s theorem using proximal point algorithm involving -maximal monotonicity framework

On the basis of the general framework of H-maximal monotonicity (also referred to as H-monotonicity in the literature), a generalization to Rockafellar’s theorem in the context of solving a general inclusion problem involving a set-valued maximal monotone operator using the proximal point algorithm in a Hilbert space setting is explored. As a matter of fact, this class of inclusion problems reduces to a class of variational inequalities as well as to a class of complementarity problems. This proximal point algorithm turns out to be of interest in the sense that it plays a significant role in certain computational methods of multipliers in nonlinear programming. The notion of H-maximal monotonicity generalizes the general theory of set-valued maximal monotone mappings to a new level. Furthermore, some results on general firm nonexpansiveness and resolvent mapping corresponding to H-monotonicity are also given.     

Optimality and invexity in optimization problems in Banach algebras (spaces)

In this paper we introduce into nonsmooth optimization theory in Banach algebras a new class of mathematical programming problems, which generalizes the notion of smooth KT-(p,r)-invexity. In fact, this paper focuses on the optimality conditions for optimization problems in Banach algebras, regarding the generalized KT-(p,r)-invexity notion and Kuhn–Tucker points.     

Linear information versus function evaluations for -approximation

We study algorithms for the approximation of functions, the error is measured in an L₂ norm. We consider the worst case setting for a general reproducing kernel Hilbert space of functions. We analyze algorithms that use standard information consisting in n function values and we are interested in the optimal order of convergence. This is the maximal exponent b for which the worst case error of such an algorithm is of order n^-b.Let p be the optimal order of convergence of all algorithms that may use arbitrary linear functionals, in contrast to function values only. So far it was not known whether p>b is possible, i.e., whether the approximation numbers or linear widths can be essentially smaller than the sampling numbers. This is (implicitly) posed as an open problem in the recent paper [F.Y. Kuo, G.W. Wasilowski, H. Woźniakowski, On the power of standard information for multivariate approximation in the worst case setting, J. Approx. Theory, to appear] where the authors prove that implies . Here we prove that the case and b=0 is possible, hence general linear information can be exponentially better than function evaluation. Since the case is quite different, it is still open whether b=p always holds in that case.     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.     

The behavior of best -approximations as . A counterexample of convergence

In the space of summable sequences we give an example of a one-dimensional affine subspace C such that the best L_p-approximations of 0 from C fail to converge as p↓1. We thus give an answer to this problem of convergence in infinite measure spaces.     

Strongly indexable graphs and applications

In 1990, Acharya and Hegde introduced the concept of strongly k-indexable graphs: A (p,q)-graph G=(V,E) is said to be strongly k-indexable if its vertices can be assigned distinct numbers 0,1,2,…,p−1 so that the values of the edges, obtained as the sums of the numbers assigned to their end vertices form an arithmetic progression k,k+1,k+2,…,k+(q−1). When k=1, a strongly k-indexable graph is simply called a strongly indexable graph. In this paper, we report some results on strongly k-indexable graphs and give an application of strongly k-indexable graphs to plane geometry, viz; construction of polygons of same internal angles and sides of distinct lengths.     

Application of continuous-time programming problems to a class of variational-type inequalities

In this paper, we establish sufficiency criteria under generalized ρ−(η,θ)-invexity conditions for general continuous-time programming problems with nonlinear equality/inequality constraints. Using this we establish some existence criteria for solutions of a class of variational-type inequalities.     

Infinitely many non-negative solutions for a Dirichlet problem involving -Laplacian

In this paper, we consider a Dirichlet problem involving the p(x)-Laplacian of the type

We prove the existence of infinitely many non-negative solutions of the problem by applying a general variational principle due to B. Ricceri and the theory of the variable exponent Sobolev spaces.     

Algorithm for solving a new class of general mixed variational inequalities in Banach spaces

In this paper, a new concept of η-proximal mapping for a proper subdifferentiable functional (which may not be convex) on a Banach space is introduced. An existence and Lipschitz continuity of the η-proximal mapping are proved. By using properties of the η-proximal mapping, a new class of general mixed variational inequalities is introduced and studied in Banach spaces. An existence theorem of solutions is established and a new iterative algorithm for solving the general mixed variational inequality is suggested. A convergence criteria of the iterative sequence generated by the new algorithm is also given.     

-adic refinable functions and MRA-based wavelets

The main goal of this paper is the development of the MRA theory in . We described a wide class of p-adic refinement equations generating p-adic multiresolution analyses. A method for the construction of p-adic orthogonal wavelet bases within the framework of the MRA theory is suggested. A realization of this method is illustrated by an example which gives a new 3-adic wavelet basis. Another realization leads to the p-adic Haar bases which were known before.     

Three solutions for a differential inclusion problem involving the -Laplacian

In this paper we consider differential inclusion problem involving the p(x)-Laplacian of the type

Applying a version of the non-smooth three-critical-points theorem we obtain the existence of three solutions of the problem in .     

Existence of periodic solutions for a fourth-order -Laplacian equation with a deviating argument

In this paper, we study the existence of periodic solutions for a fourth-order p-Laplacian differential equation with a deviating argument as follows:

[φ_p(u^″(t))]^″+f(u^″(t))+g(u(t−τ(t)))=e(t).