A Fan Type Condition For Heavy Cycles in Weighted Graphs

 A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree d ^w (v) of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. max{d ^w (x),d ^w (y)∣d(x,y)=2}≥c/2; 2. w(x z)=w(y z) for every vertex z∈N(x)∩N(y) with d(x,y)=2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least c. This generalizes a theorem of Fan on the existence of long cycles in unweighted graphs to weighted graphs. We also show we cannot omit Condition 2 or 3 in the above result. Received: February 7, 2000 Final version received: June 5, 2001     

Sparse Approximation of Singularity Functions

We are concerned with the sparse approximation of functions on the d-dimensional unit cube [0,1]^d, which contain powers of distance functions to lower-dimensional k-faces (corners, edges, etc.). These functions arise, e.g., from corners, edges, etc., of domains in solutions to elliptic PDEs. Usually, they deteriorate the rate of convergence of numerical algorithms to approximate these solutions. We show that functions of this type can be approximated with respect to the H¹ norm by sparse grid wavelet spaces V_L, (V_L) = N_L, of biorthogonal spline wavelets of degree p essentially at the rate p: \[ \|u - P_Lu\|_{H^1([0,1]^d)} \leq CN_L^{-p}\,(\log_2 N_L)^s \|u\|, \qquad s = s(p,d), \] where || · || is a weighted Sobolev norm and P_Lu \in V_L.     

Compact Sobolev embedding theorems involving symmetry and its application

Given a bounded regular domain with cylindrical symmetry, functions having such symmetry and belonging to W ^1,p can be embedded compactly into some weighted L ^q spaces, with q superior to the critical Sobolev exponent. A similar result is also obtained for variable exponent Sobolev space W ^1,p(x). Furthermore, we give a simple application to the p(x)-Laplacian problem.     

Comparison theorem and estimates for transition probability densities of diffusion processes

We establish several comparison theorems for the transition probability density p _b (x,t,y) of Brownian motion with drift b, and deduce explicit, sharp lower and upper bounds for p _b (x,t,y) in terms of the norms of the vector field b. The main results are obtained through carefully estimating the mixed moments of Bessel processes. All constants are explicit in our lower and upper bounds, which is different from most of the previous estimates, and is important in many applications for example in statistical inferences for diffusion processes.Research partially supported by N.S.F. Grants DMS-0203823, and by Doctoral Program Fundation of the Ministry of Education of China, Grant No. 20020269015. Mathematics Subject Classification (2000):Primary: 60H10, 60H30; Secondary: 35K05     

Asymptotically extremal polynomials with respect to varying weights and application to Sobolev orthogonality

We study the asymptotic behavior of the zeros of a sequence of polynomials whose weighted norms, with respect to a sequence of weight functions, have the same nth root asymptotic behavior as the weighted norms of certain extremal polynomials. This result is applied to obtain the (contracted) weak zero distribution for orthogonal polynomials with respect to a Sobolev inner product with exponential weights of the form e−φ(x), giving a unified treatment for the so-called Freud (i.e., when φ has polynomial growth at infinity) and Erdös (when φ grows faster than any polynomial at infinity) cases. In addition, we provide a new proof for the bound of the distance of the zeros to the convex hull of the support for these Sobolev orthogonal polynomials.     

A weighted estimate for the square function on the unit ball in ℂ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

We show that the Luzin area integral or the square function on the unit ball of ℂ ⁿ , regarded as an operator in the weighted space L ²(w) has a linear bound in terms of the invariant A ₂ characteristic of the weight. We show a dimension-free estimate for the “area-integral” associated with the weighted L ²(w) norm of the square function. We prove the equivalence of the classical and the invariant A ₂ classes.     

Weighted inequalities and a.e. convergence for Poisson integrals in light-cones

We show that the Poisson maximal operator for the tube over the light-cone, P ^*, is bounded in the weighted space L ^p (w) if and only if the weight w(x) belongs to the Muckenhoupt class A _p . We also characterize with a geometric condition related to the intrinsic geometry of the cone the weights v(x) for which P ^* is bounded from L ^p (v) into L ^p (u), for some other weight u(x) > 0. Some applications to a.e. restricted convergence of Poisson integrals are given.     

Circular colorings of weighted graphs

Suppose that G is a finite simple graph and w is a weight function which assigns to each vertex of G a nonnegative real number. Let C be a circle of length t. A t-circular coloring of (G, w) is a mapping Δ of the vertices of G to arcs of C such that Δ(x)∩Δ(y) = 0 if (x, y) ∈ E(G) and Δ(x) has length w(x). The circular-chromatic number of (G, w) is the least t for which there is a t-circular coloring of (G, w). This paper discusses basic properties of circular chromatic number of a weighted graph and relations between this parameter and other graph parameters. We are particularly interested in graphs G for which the circular-chromatic number of (G, w) is equal to the fractional clique weight of (G, w) for arbitrary weight function w. We call such graphs star-superperfect. We prove that odd cycles and their complements are star-superperfect. We then prove a theorem about the circular chromatic number of lexicographic product of graphs which provides a tool of constructing new star-superperfect graphs from old ones. © 1996 John Wiley & Sons, Inc.     

A note on adaptive approximation in Sobolev spaces

In this article, we consider the adaptive approximation in Sobolev spaces. After establishing some norm equivalences and inequalities in Besov spaces, we are able to prove that the best N terms approximation with wavelet‐like basis in Sobolev spaces exhibits the proper approximation order in terms of N^?1. This indicates that the computational load in adaptive approximation is proportional to the approximation accuracy. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Boundedness and Fredholmness of Pseudodifferential Operators in Variable Exponent Spaces

We prove a statement on the boundedness of a certain class of singular type operators in the weighted spaces with variable exponent p(x) and a power type weight w, from which we derive the boundedness of pseudodifferential operators of H?rmander class S ⁰ _1,0 in such spaces. This gives us a possibility to obtain a necessary and sufficient condition for pseudodifferential operators of the class OPS ^m _1,0 with symbols slowly oscillating at infinity, to be Fredholm within the frameworks of weighted Sobolev spaces with constant smoothness s, variable p(·)-exponent, and exponential weights w. Supported by CONACYT Project No.43432 (Mexico), the Project HAOTA of CEMAT at Instituto Superior Técnico, Lisbon (Portugal) and the INTAS Project “Variable Exponent Analysis” Nr.06-1000017-8792.     

Characterization of Sobolev spaces of arbitrary smoothness using nonstationary tight wavelet frames

In this paper we shall characterize Sobolev spaces of an arbitrary order of smoothness using nonstationary tight wavelet frames for L ₂(ℝ). In particular, we show that a Sobolev space of an arbitrary fixed order of smoothness can be characterized in terms of the weighted ℓ₂-norm of the analysis wavelet coefficient sequences using a fixed compactly supported nonstationary tight wavelet frame in L ₂(ℝ) derived from masks of pseudosplines in [15]. This implies that any compactly supported nonstationary tight wavelet frame of L ₂(ℝ) in [15] can be properly normalized into a pair of dual frames in the corresponding pair of dual Sobolev spaces of an arbitrary fixed order of smoothness. Research supported in part by NSERC Canada under Grant RGP 228051. Research supported in part by Grant R-146-000-060-112 at the National University of Singapore.     

Claw Conditions for Heavy Cycles in Weighted Graphs

A graph is called a weighted graph when each edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident with v. For a subgraph H of a weighted graph G, the weight of H is the sum of the weights of the edges belonging to H. In this paper, we give a new sufficient condition for a weighted graph to have a heavy cycle. A 2-connected weighted graph G contains either a Hamilton cycle or a cycle of weight at least c, if G satisfies the following conditions: In every induced claw or induced modified claw F of G, (1) max{d^w(x),d^w(y)} c/2 for each non-adjacent pair of vertices x and y in F, and (2) all edges of F have the same weight.     

Approximation of singularly perturbed parabolic equations in unbounded domains subject to piecewise smooth boundary conditions in the case of solutions that grow at infinity

The initial-boundary value problem in a domain on a straight line that is unbounded in x is considered for a singularly perturbed reaction-diffusion parabolic equation. The higher order derivative in the equation is multiplied by a parameter ɛ², where ɛ ∈ (0, 1]. The right-hand side of the equation and the initial function grow unboundedly as x → ∞ at a rate of O(x ²). This causes the unbounded growth of the solution at infinity at a rate of O(Ψ(x)), where Ψ(x) = x ² + 1. The initialboundary function is piecewise smooth. When ɛ is small, a boundary and interior layers appear, respectively, in a neighborhood of the lateral part of the boundary and in a neighborhood of the characteristics of the reduced equation passing through the discontinuity points of the initial function. In the problem under examination, the error of the grid solution grows unboundedly in the maximum norm as x → ∞ even for smooth solutions when ɛ is fixed. In this paper, the proximity of solutions of the initial-boundary value problem and its grid approximations is considered in the weighted maximum norm ∥·∥ ^w with the weighting function Ψ⁻¹(x); in this norm, the solution of the initial-boundary value problem is ɛ-uniformly bounded. Using the method of special grids that condense in a neighborhood of the boundary layer or in neighborhoods of the boundary and interior layers, special finite difference schemes are constructed and studied that converge ɛ-uniformly in the weighted norm. It is shown that the convergence rate considerably depends on the type of nonsmoothness in the initial-boundary conditions. Grid approximations of the Cauchy problem with the right-hand side and the initial function growing as O(Ψ(x)) that converge ɛ-uniformly in the weighted norm are also considered.     

Best approximation with wavelets in weighted Orlicz spaces

Democracy functions of wavelet admissible bases are computed for weighted Orlicz Spaces L ^??(w) in terms of the fundamental function of L ^??(w). In particular, we prove that these bases are greedy in L ^??(w) if and only if L ^??(w) =?L ^p (w), 1?<?p?<???. Also, sharp embeddings for the approximation spaces are given in terms of weighted discrete Lorentz spaces. For L ^p (w) the approximation spaces are identified with weighted Besov spaces.     

Entropy numbers of embeddings of weighted Besov spaces III. Weights of logarithmic type

We determine the exact asymptotic order of the entropy numbers of compact embeddings of weighted Besov spaces in the case where the ratio of the weights w(x) = w ₁(x)/w ₂(x) is of logarithmic type. This complements the known results for weights of polynomial type. The estimates are given in terms of the number 1/p = 1/p ₁ − 1/p ₂ and the function w(x). We find an interesting new effect: if the growth rate at infinity of w(x) is below a certain critical bound, then the entropy numbers depend only on w(x) and no longer on the parameters of the two Besov spaces. All results remain valid for Triebel–Lizorkin spaces as well.     

On an optimal quadrature formula in the sense of Sard

In this paper we construct an optimal quadrature formula in the sense of Sard in the Hilbert space K ₂(P ₂). Using S.L. Sobolev’s method we obtain new optimal quadrature formula of such type and give explicit expressions for the corresponding optimal coefficients. Furthermore, we investigate order of the convergence of the optimal formula and prove an asymptotic optimality of such a formula in the Sobolev space L₂⁽²⁾(0,1)L_2^{(2)}(0,1). The obtained optimal quadrature formula is exact for the trigonometric functions sinx and cosx. Also, we include a few numerical examples in order to illustrate the application of the obtained optimal quadrature formula.     

Reconstructing the past from imprecise knowledge of the present: Effective non‐uniqueness in solving parabolic equations backward in time

Identifying sources of ground water pollution and deblurring astronomical galaxy images are two important applications generating growing interest in the numerical computation of parabolic equations backward in time. However, while backward uniqueness typically prevails in parabolic equations, the precise data needed for the existence of a particular backward solution is seldom available. This paper discusses previously unexplored non‐uniqueness issues, originating from trying to reconstruct a particular solution from imprecise data. Explicit 1D examples of linear and nonlinear parabolic equations are presented, in which there is strong computational evidence for the existence of distinct solutions w^red(x,t) and w^green(x,t), on 0 ≤ t ≤ 1. These solutions have the property that the traces w^red(x,1) and w^green(x,1) at time t = 1 are close enough to be visually indistinguishable, while the corresponding initial values w^red(x,0) and w^green(x,0) are vastly different, well‐behaved, physically plausible functions, with comparable L² norms. This implies effective non‐uniqueness in the recovery of w^red(x,0) from approximate data for w^red(x,1). In all these examples, the Van Cittert iterative procedure is used as a tool to discover unsuspected, valid, additional solutions w^green(x,0). This methodology can generate numerous other examples and indicates that multidimensional problems are likely to be a rich source of striking non‐uniqueness phenomena. Published 2012. This article is a US Government work and is in the public domain in the USA.     

On the gowers norms of certain functions

We consider functions f(x, y) whose smallness condition for the rectangular norm implies the smallness of the rectangular norm for f(x, x + y). We also study families of functions with a similar property for the higher Gowers norms. The method of proof is based on a transfer principle for sums between special systems of linear equations.     

Weighted Bounds for Variational Walsh–Fourier Series

For 1<p<?? and a weight w??A _p and a function in L ^p ([0,1],w) we show that variational sums with sufficiently large exponents of its Walsh?CFourier series are bounded in L ^p (w). This strengthens a result of Hunt?CYoung and is a weighted extension of a variation norm Carleson theorem of Oberlin?CSeeger?CTao?CThiele?CWright. The proof uses phase plane analysis and a weighted extension of a variational inequality of Lépingle.     

Cycles in weighted graphs

A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4].