Entropy Numbers in Weighted Function Spaces and Eigenvalue Distributions of Some Degenerate Pseudodifferential Operators II

This paper is the continuation of [17]. We investigate mapping and spectral properties of pseudodifferential operators of type Ψ with χ χ ? ? and 0 ≤ γ ≤ 1 in the weighted function spaces B (?ⁿ, w(x)) and F (?ⁿ, w(x)) treated in [17]. Furthermore, we study the distribution of eigenvalues and the behaviour of corresponding root spaces for degenerate pseudodifferential operators preferably of type b₂(x) b(x, D) b₁(x), where b₁(x) and b₂(x) are appropriate functions and b(x, D) ? Ψ. Finally, on the basis of the Birman-Schwinger principle, we deal with the “negative spectrum” (bound states) of related symmetric operators in L₂.     

On the chromatic number of the general Kneser-graph

Given integers k, n, 2 < k < n, let us define a graph with vertex set V = {F ?{1, 2, …, n}: ∩F = k}, and (F, F') is an edge if |F ∩ F′| ≤ 1. We show that for n > n₀(k) the chromatic number of this graph is (k - 1)() + rs, where n = (k - 1)s + r, 0 ≤ r < k - 1.     

Tangential Convergence of Temperatures and Harmonic Functions in Besov and in Triebel-Lizorkin Spaces

We study the maximal function Mf(x) = sup |f(x + y, t)| when Ω is a region in the (y,t) Ω upper half space R and f(x, t) is the harmonic extension to R₊^N+1 of a distribution in the Besov space B^α_p,q(R^N) or in the Triebel-Lizorkin space F^α_p,q(R^N). In particular, we prove that when Ω= {|_y|^{N/ (N-αp)} < t < 1} the operator M is bounded from F (R^N) into L^p (R^N). The admissible regions for the spaces B (R^N) with p < q are more complicated.     

Monotone numerical schemes for a Dirichlet problem for elliptic operators in divergence form

We consider a second‐order differential operator A( x )=?∑?_ia_ij( x )?_j+ ∑?_j(b_j( x )·)+c( x ) on ?^d, on a bounded domain D with Dirichlet boundary conditions on ?D, under mild assumptions on the coefficients of the diffusion tensor a_ij. The object is to construct monotone numerical schemes to approximate the solution of the problem A( x )u( x )=µ( x ), x ∈D, where µ is a positive Radon measure. We start by briefly mentioning questions of existence and uniqueness introducing function spaces needed to prove convergence results. Then, we define non‐standard stencils on grid‐knots that lead to extended discretization schemes by matrices possessing compartmental structure. We proceed to discretization of elliptic operators, starting with constant diffusion tensor and ending with operators in divergence form. Finally, we discuss W‐convergence in detail, and mention convergence in C and L₁ spaces. We conclude by a numerical example illustrating the schemes and convergence results. Copyright © 2008 John Wiley & Sons, Ltd.     

Enumeration of graphs by degree sequence

The degree sequence (d₀, d₁, …, d_p-1) of a graph G of order p is defined by d_k = the number of points of G of degree k. Methods of Robinson are extended to produce a generating function F(x₀, x₁, x₂, …) where the coefficient of x…x is the number of graphs of order p having degree sequence (d₀, …, d_p-1).     

The determining number of a Cartesian product

A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted Det(G), is the size of a smallest determining set. This paper begins by proving that if G=G□?□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G)}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Q_n)=?log₂n?+1 which matches the lower bound, and that Det(K)=?log₃(2n+1)?+1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(Hⁿ)=Θ(logn). © 2009 Wiley Periodicals, Inc. J Graph Theory     

The red‐shift effect and radiation decay on black hole spacetimes

We consider solutions to the linear wave equation □_g? = 0 on a (maximally extended) Schwarzschild spacetime with parameter M > 0, evolving from sufficiently regular initial data prescribed on a complete Cauchy surface Σ, where the data are assumed only to decay suitably at spatial infinity. (In particular, the support of ? may contain the bifurcate event horizon.) It is shown that the energy flux F(??) of the solution (as measured by a strictly timelike T? that asymptotically matches the static Killing field) through arbitrary achronal subsets ?? of the black hole exterior region satisfies the bound F(??) ≤ C E(v + u), where v and u denote the infimum of the Eddington‐Finkelstein advanced and retarded time of ??, v₊ denotes max{1, v}, and u₊ denotes max{1, u}, where C is a constant depending only on the parameter M, and E depends on a suitable norm of the solution on the hypersurface t ? u + v = 1. (The bound applies in particular to subsets ?? of the event horizon or null infinity.) It is also shown that ? satisfies the pointwise decay estimate |?| ≤ C Ev in the entire exterior region, and the estimates |r?| ≤ C_R?E(1 + |u|)^?1/2 and |r^1/2?| ≤ C_R?Eu in the region {r ≥ R?} ∩ J⁺(Σ) for any R? > 2M. The estimates near the event horizon exploit an integral energy identity normalized to local observers. This estimate can be thought to quantify the celebrated red‐shift effect. The results in particular give an independent proof of the classical result |?| ≥ C E of Kay and Wald without recourse to the discrete isometries of spacetime. © 2009 Wiley Periodicals, Inc.     

Entropy Numbers in Weighted Function Spaces and Eigenvalue Distributions of Some Degenerate Pseudodifferential Operators I

In this paper we study weighted function spaces of type B(?ⁿ, Q(x)) and F(?ⁿ, Q(x)), where Q(x) is a weight function of at most polynomial growth. Of special interest are the weight functions Q(x) = (1 + |x|²)^α/2 with α ? ?. The main result deals with estimates for the entropy numbers of compact embeddings between spaces of this type.     

Iteratively reweighted least squares minimization for sparse recovery

Under certain conditions (known as the restricted isometry property, or RIP) on the m × N matrix Φ (where m < N), vectors x ∈ ?^N that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from y := Φx even though Φ^?1(y) is typically an (N ? m)—dimensional hyperplane; in addition, x is then equal to the element in Φ^?1(y) of minimal ??₁‐norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining x, as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector w, the element in Φ^?1(y) with smallest ??₂(w)‐norm. If x⁽ⁿ⁾ is the solution at iteration step n, then the new weight w⁽ⁿ⁾ is defined by w := [|x|² + ε]^?1/2, i = 1, …, N, for a decreasing sequence of adaptively defined ε_n; this updated weight is then used to obtain x^{(n + 1)} and the process is repeated. We prove that when Φ satisfies the RIP conditions, the sequence x⁽ⁿ⁾ converges for all y, regardless of whether Φ^?1(y) contains a sparse vector. If there is a sparse vector in Φ^?1(y), then the limit is this sparse vector, and when x⁽ⁿ⁾ is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same algorithm with the “heavier” weight w = [|x|² + ε]^?1+τ/2, i = 1, …, N, where 0 < τ < 1, can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for τ approaching 0. © 2009 Wiley Periodicals, Inc.     

On the rate for uniform strong consistency of empirical distributions of independent nonidentically distributed multivariate random variables

Let X_j = (X_1j ,…, X_pj), j = 1,…, n be n independent random vectors. For x = (x₁ ,…, x_p) in R^p and for α in [0, 1], let F_j${}^1$(x) = αI(X_1j < x₁ ,…, X_pj < x_p) + (1 ? α) I(X_1j ≤ x₁ ,…, X_pj ≤ x_p), where I(A) is the indicator random variable of the event A. Let F_j(x) = E(F_j${}^1$(x)) and D_n = sup_{x, α} max_{1 ≤ N ≤ n} |Σ₀ⁿ(F_j${}^1$(x) ? F_j(x))|. It is shown that P[D_n ≥ L] < 4pL exp{?2(L²n^?1 ? 1)} for each positive integer n and for all L² ≥ n; and, as n → ∞, $\text{D}{}_{\mathrm{n}}\text{= 0((n}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ with probability one.     

Zeros of semilinear systems with applications to nonlinear partial difference equations on graphs†

Let Q be a m × m real matrix and f _j  : ? → ?, j = 1, …, m, be some given functions. If x and f(x) are column vectors whose j-coordinates are x _j and f _j (x _j ), respectively, then we apply the finite dimensional version of the mountain pass theorem to provide conditions for the existence of solutions of the semilinear system Qx = f(x) for Q symmetric and positive semi-definite. The arguments we use are a simple adaptation of the ones used by Neuberger. An application of the above concerns partial difference equations on a finite, connected simple graph. A derivation of a graph 𝒢 is just any linear operator D:C ⁰(𝒢) → C ⁰(𝒢), where C ⁰(𝒢) is the real vector space of real maps defined on the vertex set V of the graph. Given a derivation D and a function F:V × ? → ?, one has associated a partial difference equation Dμ = F(v,μ), and one searches for solutions μ ∈ C ⁰(𝒢). Sufficient conditions in order to have non-trivial solutions of partial difference equations on any finite, connected simple graph for D symmetric and positive semi-definite derivation are provided. A metric (or weighted) graph is a pair (𝒢, d), where 𝒢 is a connected finite degree simple graph and d is a positive function on the set of edges of the graph. The metric d permits to consider some classical derivations, such as the Laplacian operator ?₂. In (Neuberger, Elliptic partial difference equations on graphs, Experiment. Math. 15 (2006), pp. 91–107) was considered the nonlinear elliptic partial difference equations ?₂ u = F(u), for the metric d = 1.     

Subgraphs smaller than the girth

For graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k-node tree T, then for every k-node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.     

Coin flipping from a cosmic source: On error correction of truly random bits

We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1}ⁿ, and k parties, who have noisy version of the source bits yⁱ ∈ {0, 1}ⁿ, when for all i and j, it holds that P [y = x_j] = 1 ? ?, independently for all i and j. That is, each party sees each bit correctly with probability 1 ? ?, and incorrectly (flipped) with probability ?, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions f_i: {0, 1}ⁿ → {0, 1} such that P [f₁(y¹) = … = f_k(y^k)] is maximized. In other words, each party wants to toss a fair coin so that the probability that all parties have the same coin is maximized. The function f_i may be thought of as an error correcting procedure for the source x. When k = 2,3, no error correction is possible, as the optimal protocol is given by f_i(yⁱ) = y. On the other hand, for large values of k, better protocols exist. We study general properties of the optimal protocols and the asymptotic behavior of the problem with respect to k, n, and ?. Our analysis uses tools from probability, discrete Fourier analysis, convexity, and discrete symmetrization. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Longtime behavior for a nonlinear wave equation arising in elasto‐plastic flow

The paper studies the longtime behavior of solutions to the initial boundary value problem (IBVP) for a nonlinear wave equation arising in elasto‐plastic flow u_tt?div{|?u|^m?1?u}?λΔu_t+Δ²u+g(u)=f(x). It proves that under rather mild conditions, the dynamical system associated with above‐mentioned IBVP possesses a global attractor, which is connected and has finite Hausdorff and fractal dimension in the phase spaces X₁=H(Ω) × L²(Ω) and X=(H³(Ω)∩H(Ω)) × H(Ω), respectively. Copyright © 2008 John Wiley & Sons, Ltd.     

Velocity averaging,kinetic formulations,and regularizing effects in quasi‐linear PDEs

We prove in this paper new velocity‐averaging results for second‐order multidimensional equations of the general form ??(?_x, v)f(x, v) = g(x, v) where ??(?_x, v) := a (v) · ?_x ? ? ${}_{\text{x}}^{\text{?}}$ · b (v)?_x. These results quantify the Sobolev regularity of the averages, ∫_v f(x, v)?(v)dv, in terms of the nondegeneracy of the set {v: |??(iξ, v)| ≤ δ} and the mere integrability of the data, (f, g) ∈ (L, L). Velocity averaging is then used to study the regularizing effect in quasi‐linear second‐order equations, ??(?_x, ρ)ρ = S(ρ), which use their underlying kinetic formulations, ??(?_{x, v})χ_ρ = g_S. In particular, we improve previous regularity statements for nonlinear conservation laws, and we derive completely new regularity results for convection‐diffusion and elliptic equations driven by degenerate, nonisotropic diffusion. © 2007 Wiley Periodicals, Inc.     

Compactness methods in the theory of homogenization II: Equations in non-divergence form

We prove C^{0, α}, C^{1, α} and C^{1, 1} a priori estimates for solutions of boundary value problems for elliptic operators with periodic coefficients of the form Σ,^j=1a^{i j}(x/?)δ²/δx_iδx_j. The constants in these estimates are independent of the small parameter ?, and hence our results imply strengthened versions of the classical averaging theorems. These results generalize to a wide class of linear operators in non-divergence form, including equations with lower-order terms and nonuniformly oscillating coefficients, as well as to certain nonlinear problems, which we discuss in the last section.     

Average distance,minimum degree,and spanning trees

The average distance μ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., μ(G) = ()⁻¹ Σ_{x,y}⊂V(G) d_G(x, y), where V(G) denotes the vertex set of G and d_G(x, y) is the distance between x and y. We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most . We give improved bounds for K₃‐free graphs, C₄‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000     

Semilinear wave equation with time dependent potential

We consider the following semilinear wave equation: (1) for (t,x) ∈ ?_t × ?. We prove that if the potential V(t,x) is a measurable function that satisfies the following decay assumption: ∣V(t,x)∣?C(1+t)(1+∣x∣) for a.e. (t,x) ∈ ?_t × ? where C, σ₀>0 are real constants, then for any real number λ that satisfies there exists a real number ρ(f,g,λ)>0 such that the equation has a global solution provided that 0<ρ?ρ(f,g,λ). Copyright © 2004 John Wiley & Sons, Ltd.     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05     

Limit laws for embedded trees: Applications to the integrated superBrownian excursion

We study three families of labeled plane trees. In all these trees, the root is labeled 0 and the labels of two adjacent nodes differ by 0,1, or ?1. One part of the paper is devoted to enumerative results. For each family, and for all j ∈ ?, we obtain closed form expressions for the following three generating functions: the generating function of trees having no label larger than j; the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled j; and finally the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled at least, j. Strangely enough, all these series turn out to be algebraic, but we have no combinatorial intuition for this algebraicity. The other part of the paper is devoted to deriving limit laws from these enumerative results. In each of our families of trees, we endow the trees of size n with the uniform distribution and study the following random variables: M_n, the largest label occurring in a (random) tree; X_n(j), the number of nodes labeled j; and X(j), the number of nodes labeled j or more. We obtain limit laws for scaled versions of these random variables. Finally, we translate the above limit results into statements dealing with the integrated superBrownian excursion. In particular, we describe the law of the supremum of its support (thus recovering some earlier results obtained by Delmas) and the law of its distribution function at a given point. We also conjecture the law of its density (at a given point). © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006