Highly oscillatory multidimensional shocks

We construct geometric optics expansions of high order for oscillatory multidimensional shocks and then show that the expansions are close to exact shock solutions for small wavelengths. Expansions are constructed both for S_ϵ, the oscillatory function defining the shock surface S_ϵ, and for u, the solutions on each side of S_ϵ. The profile equations yield detailed information on the evolution of (u, ψ_ϵ), showing, for example, how new interior oscillations are produced by a variety of shock—interior and interior—interior interactions. A generic small divisor property, L²‐estimates for linearized shock problems with merely Lipschitz coefficients, and a continuation principle based on an unusual Gagliardo‐Nirenberg inequality all play a role in the proofs. © 1999 John Wiley & Sons, Inc.     

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.     

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.     

Stability of Cahn‐Hilliard fronts

We prove stability of the kink solution of the Cahn‐Hilliard equation ∂_tu = ∂( ∂u − u/2 + u³/2), x ∈ ℝ. The proof is based on an inductive renormalization group method, and we obtain detailed asymptotics of the solution as t → ∞. We prove stability of the kink solution of the Cahn‐Hilliard equation ∂_tu = ∂( ∂u − u/2 + u³/2), x ∈ ℝ. The proof is based on an inductive renormalization group method, and we obtain detailed asymptotics of the solution as t → ∞. © 1999 John Wiley & Sons, Inc.     

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

A quantitative compactness estimate for scalar conservation laws

In the case of a scalar conservation law with convex flux in space dimension one, P. D. Lax proved [Comm. Pure and Appl. Math. 7 (1954)] that the semigroup defining the entropy solution is compact in L for each positive time. The present note gives an estimate of the ?‐entropy in L of the set of entropy solutions at time t > 0 whose initial data run through a bounded set in L¹. © 2005 Wiley Periodicals, Inc.     

Topological degree for a mean field equation on Riemann surfaces

We consider the following mean field equations: (0.1) where M is a compact Riemann surface with volume 1, h is a positive continuous function on M, ρ is a real number, (0.2) and where Ω is a bounded smooth domain, h is a C¹ positive function on Ω, and ρ ∈ ?. Based on our previous analytic work [14], we prove, among other things, that the degree‐counting formula for ( 0.1 ) is given by () for ρ ∈ (8mπ, 8(m + 1)π). © 2003 Wiley Periodicals, Inc.     

On the number of interior peak solutions for a singularly perturbed Neumann problem

We consider the following singularly perturbed Neumann problem: where Δ = Σ ?²/?x is the Laplace operator, ? > 0 is a constant, Ω is a bounded, smooth domain in ?^N with its unit outward normal ν, and f is superlinear and subcritical. A typical f is f(u) = u^p where 1 < p < +∞ when N = 2 and 1 < p < (N + 2)/(N ? 2) when N ≥ 3. We show that there exists an ?₀ > 0 such that for 0 < ? < ?₀ and for each integer K bounded by where α_{N, Ω, f} is a constant depending on N, Ω, and f only, there exists a solution with K interior peaks. (An explicit formula for α_{N, Ω, f} is also given.) As a consequence, we obtain that for ? sufficiently small, there exists at least [α_{N, Ωf}/?^N (|ln ?|)^N] number of solutions. Moreover, for each m ∈ (0, N) there exist solutions with energies in the order of ?^N?m. © 2006 Wiley Periodicals, Inc.     

Subelliptic Estimates for a Class of Degenerate Elliptic Integro-Differential Operators

In this paper we prove subelliptic estimates for operators of the form Δ_x + λ² (x)S in ?^N = ? × ?, where the operator S is an elliptic integro - differential operator in ?^N and λ is a nonnegative Lipschitz continuous function.     

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.     

Word maps and spectra of random graph lifts

We study here the spectra of random lifts of graphs. Let G be a finite connected graph, and let the infinite tree T be its universal cover space. If λ₁ and ρ are the spectral radii of G and T respectively, then, as shown by Friedman (Graphs Duke Math J 118 (2003), 19–35), in almost every n‐lift H of G, all “new” eigenvalues of H are ≤ O(λ ρ^1/2). Here we improve this bound to O(λ ρ^2/3). It is conjectured in (Friedman, Graphs Duke Math J 118 (2003) 19–35) that the statement holds with the bound ρ + o(1) which, if true, is tight by (Greenberg, PhD thesis, 1995). For G a bouquet with d/2 loops, our arguments yield a simple proof that almost every d‐regular graph has second eigenvalue O(d^2/3). For the bouquet, Friedman (2008). has famously proved the (nearly?) optimal bound of . Central to our work is a new analysis of formal words. Let w be a formal word in letters g,…,g. The word map associated with w maps the permutations σ₁,…,σ_k ∈ S_n to the permutation obtained by replacing for each i, every occurrence of g_i in w by σ_i. We investigate the random variable X that counts the fixed points in this permutation when the σ_i are selected uniformly at random. The analysis of the expectation ??(X) suggests a categorization of formal words which considerably extends the dichotomy of primitive vs. imprimitive words. A major ingredient of a our work is a second categorization of formal words with the same property. We establish some results and make a few conjectures about the relation between the two categorizations. These conjectures suggest a possible approach to (a slightly weaker version of) Friedman's conjecture. As an aside, we obtain a new conceptual and relatively simple proof of a theorem of A. Nica (Nica, Random Struct Algorithms 5 (1994), 703–730), which determines, for every fixed w, the limit distribution (as n →∞) of X. A surprising aspect of this theorem is that the answer depends only on the largest integer d so that w = u^d for some word u. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

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     

On smallest triangles

Pick n points independently at random in ?², according to a prescribed probability measure μ, and let Δ ≤ Δ ≤ … be the areas of the () triangles thus formed, in nondecreasing order. If μ is absolutely continuous with respect to Lebesgue measure, then, under weak conditions, the set {n³Δ : i ≥ 1} converges as n → ∞ to a Poisson process with a constant intensity κ(μ). This result, and related conclusions, are proved using standard arguments of Poisson approximation, and may be extended to functionals more general than the area of a triangle. It is proved in addition that if μ is the uniform probability measure on the region S, then κ(μ) ≤ 2/|S|, where |S| denotes the area of S. Equality holds in that κ(μ) = 2/|S| if S is convex, and essentially only then. This work generalizes and extends considerably the conclusions of a recent paper of Jiang, Li, and Vitányi. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 206–223, 2003     

Blowup for nonlinear wave equations describing boson stars

We consider the nonlinear wave equation modeling the dynamics of (pseudorelativistic) boson stars. For spherically symmetric initial data, u₀(x) ∈ C (?³), with negative energy, we prove blowup of u(t, x) in the H^1/2‐norm within a finite time. Physically this phenomenon describes the onset of “gravitational collapse” of a boson star. We also study blowup in external, spherically symmetric potentials, and we consider more general Hartree‐type nonlinearities. As an application, we exhibit instability of ground state solitary waves at rest if m = 0. © 2007 Wiley Periodicals, Inc.     

Application of the τ‐function theory of Painlevé equations to random matrices: PV,PIII, the LUE,JUE, and CUE

With 〈·〉 denoting an average with respect to the eigenvalue PDF for the Laguerre unitary ensemble, the object of our study is for I = (0, s) and I = (s, ∞), where χ = 1 for λ_l ∈ I and χ = 0 otherwise. Using Okamoto's development of the theory of the Painlevé V equation, it is shown that ?_N(I; a, μ) is a τ‐function associated with the Hamiltonian therein, and so can be characterized as the solution of a certain second‐order second‐degree differential equation, or in terms of the solution of certain difference equations. The cases μ = 0 and μ = 2 are of particular interest, because they correspond to the cumulative distribution and density function, respectively, for the smallest and largest eigenvalue. In the case I = (s, ∞), ?_N(I; a, μ) is simply related to an average in the Jacobi unitary ensemble, and this in turn is simply related to certain averages over the orthogonal group, the unitary symplectic group, and the circular unitary ensemble. The latter integrals are of interest for their combinatorial content. Also considered are the hard‐edge and soft‐edge scaled limits of ?_N(I; a, μ). In particular, in the hard‐edge scaled limit it is shown that the limiting quantity ?^hard((O, s); a, μ) can be evaluated as a τ‐function associated with the Hamiltonian in Okamoto's theory of the Painlevé III equation. © 2002 Wiley Periodicals, Inc.     

Phase transition for potentials of high‐dimensional wells

For a potential function that attains its global minimum value at two disjoint compact connected submanifolds N^± in , we discuss the asymptotics, as ? → 0, of minimizers u_? of the singular perturbed functional under suitable Dirichlet boundary data . In the expansion of E _? (u_?) with respect to , we identify the first‐order term by the area of the sharp interface between the two phases, an area‐minimizing hypersurface Γ, and the energy c of minimal connecting orbits between N⁺ and N^?, and the zeroth‐order term by the energy of minimizing harmonic maps into N^± both under the Dirichlet boundary condition on ?Ω and a very interesting partially constrained boundary condition on the sharp interface Γ. © 2012 Wiley Periodicals, Inc.     

m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements

It is known that the joint distribution of the number of nodes of each type of an m‐ary search tree is asymptotically multivariate normal when m ≤ 26. When m ≥ 27, we show the following strong asymptotics of the random vector X_n = ^t(X, … , X), where X denotes the number of nodes containing i ? 1 keys after having introduced n ? 1 keys in the tree: There exist (nonrandom) vectors X, C, and S and random variables ρ and φ such that (X_n ? nX)/n ? ρ(C cos(τ₂log n + φ) + S sin(τ₂log n + φ)) →_n→∞ 0 almost surely and in L²; σ₂ and τ₂ denote the real and imaginary parts of one of the eigenvalues of the transition matrix, having the second greatest real part. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Invariant Constructions of Simple and Maximal Sets

The main results of the present paper are the following theorems: 1. There is no e ∈ ω such that for any A, B ? ω, S^A = W is simple in A, and if A′ ?_T B′, then S^A =* S^B. 2 There is an e ∈ ω such that for any A, B ? ω, M^A = W_e is incomplete maximal in A, and if A =* B, then M^A ?_T M^B.     

Lower compactness estimates for scalar balance laws

In this paper, we study the compactness in L of the semigroup (St)_t≥0 of entropy weak solutions to strictly convex scalar conservation laws in one space dimension. The compactness of St for each t > 0 was established by P. D. Lax. Upper estimates for the Kolmogorov e‐entropy of the image of bounded sets in L¹ n L^∞ through S_t were given by C. De Lellis and F. Golse. Here we provide lower estimates on this e‐entropy of the same order as the one established by De Lellis and Golse, thus showing that such an e‐entropy is of size ≈ 1/ε. Moreover, we extend these estimates of compactness to the case of convex balance laws. © 2012 Wiley Periodicals, Inc.     

Strong asymptotics of orthogonal polynomials with respect to exponential weights

We consider asymptotics of orthogonal polynomials with respect to weights w(x)dx = e^−Q(x) dx on the real line, where Q(x) = Σ q_k x^k, q_2m > 0, denotes a polynomial of even order with positive leading coefficient. The orthogonal polynomial problem is formulated as a Riemann‐Hilbert problem following [22, 23]. We employ the steepest‐descent‐type method introduced in [18] and further developed in [17, 19] in order to obtain uniform Plancherel‐Rotach‐type asymptotics in the entire complex plane, as well as asymptotic formulae for the zeros, the leading coefficients, and the recurrence coefficients of the orthogonal polynomials. © 1999 John Wiley & Sons, Inc.