Representation of Reproducing Kernels and the Lebesgue Constants on the Ball

For the weight function (1−x²)^μ−1/2 on the unit ball, a closed formula of the reproducing kernel is modified to include the case −1/2<μ<0. The new formula is used to study the orthogonal projection of the weighted L² space onto the space of polynomials of degree at most n, and it is proved that the uniform norm of the projection operator has the growth rate of n^(d−1)/2 for μ<0, which is the smallest possible growth rate among all projections, while the rate for μ0 is n^μ+(d−1)/2.     

On the structure of semi-invariant polynomials in Ore extensions

Let D be an X-outer S-derivation of a prime ring R, where S is an automorphism of R. The following is proved among other things: The degree of the minimal semi-invariant polynomial of the Ore extension R[X;S,D] is ν if charR=0, and is p^kν for some k0 if charR=p2, where ν is the least integer ν1 such that S^νDS^−ν−D is X-inner. A similar result holds for cv-polynomials. These are done by introducing the new notion of k-basic polynomials for each integer k0, which enable us to analyze semi-invariant polynomials inductively.     

Existence of nonstationary bubbles in higher dimensions

We are interested in the existence of travelling-waves for the nonlinear Schrödinger equation in R^N with “ψ³−ψ⁵”-type nonlinearity. First, we prove an abstract result in critical point theory (a local variant of the classical saddle-point theorem). Using this result, we get the existence of travelling-waves moving with sufficiently small velocity in space dimension N4.     

Variations on a theme of Jost and Pais

We explore the extent to which a variant of a celebrated formula due to Jost and Pais, which reduces the Fredholm perturbation determinant associated with the Schrödinger operator on a half-line to a simple Wronski determinant of appropriate distributional solutions of the underlying Schrödinger equation, generalizes to higher dimensions. In this multi-dimensional extension the half-line is replaced by an open set , , n2, where Ω has a compact, nonempty boundary ∂Ω satisfying certain regularity conditions. Our variant involves ratios of perturbation determinants corresponding to Dirichlet and Neumann boundary conditions on ∂Ω and invokes the corresponding Dirichlet-to-Neumann map. As a result, we succeed in reducing a certain ratio of modified Fredholm perturbation determinants associated with operators in L²(Ω;dⁿx), , to modified Fredholm determinants associated with operators in L²(∂Ω;dⁿ⁻¹σ), n2. Applications involving the Birman–Schwinger principle and eigenvalue counting functions are discussed.     

Best Harmonic and Superharmonic L-Approximants in Strips

Let Ω denote the open strip (−1, 1)× ⁿ⁻¹, where n2. We completely solve the problem of characterizing a best harmonic L¹-approximant to a subharmonic function s on Ω (all functions are assumed to be continuous and integrable on Ω). This characterization was previously known only under highly restrictive hypotheses on s. The approach of this paper is based, in part, on ideas used recently to solve the corresponding problem for the unit ball. However, the unboundedness of Ω presents difficulties which require the use of new techniques and recent results from other branches of harmonic approximation theory. Superharmonic L¹-approximation of subharmonic functions is also treated.     

A Nonsymmetric Correlation Inequality for Gaussian Measure

Letμbe a Gaussian measure (say, onRⁿ) and letK,LRⁿbe such thatKis convex,Lis a “layer” (i.e.,L={x: ax, ub} for somea, bRanduRⁿ), and the centers of mass (with respect toμ) ofKandLcoincide. Thenμ(K∩L)μ(K)·μ(L). This is motivated by the well-known “positive correlation conjecture” for symmetric sets and a related inequality of Sidak concerning confidence regions for means of multivariate normal distributions. The proof uses the estimateΦ(x)> 1−((8/π)^1/2/(3x+(x²+8)^1/2))e^−x2/2,x>−1, for the (standard) Gaussian cumulative distribution function, which is sharper than the classical inequality of Komatsu.     

Existence of HSOLSSOMs of type

In this paper we investigate the existence of holey self-orthogonal Latin squares with a symmetric orthogonal mate of type 2ⁿu¹ (HSOLSSOM(2ⁿu¹)). For u2, necessary conditions for existence of such an HSOLSSOM are that u must be even and n3u/2+1. Xu Yunqing and Hu Yuwang have shown that these HSOLSSOMs exist whenever either (1) n9 and n3u/2+1 or (2) n263 and n2(u-2). In this paper we show that in (1) the condition n9 can be extended to n30 and that in (2), the condition n263 can be improved to n4, except possibly for 19 pairs (n,u), the largest of which is (53,28).     

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.We present a complete solution to this problem: For every bin size b1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.     

Asymptotic behavior of solutions of semilinear elliptic equations near an isolated singularity

We consider the semilinear elliptic equation Δu=h(u) in Ω{0}, where Ω is an open subset of (N2) containing the origin and h is locally Lipschitz continuous on [0,∞), positive in (0,∞). We give a complete classification of isolated singularities of positive solutions when h varies regularly at infinity of index q(1,C_N) (that is, lim_u→∞h(λu)/h(u)=λ^q, for every λ>0), where C_N denotes either N/(N−2) if N3 or ∞ if N=2. Our result extends a well-known theorem of Véron for the case h(u)=u^q.     

Primitive normal polynomials with a prescribed coefficient

In this paper, we established the existence of a primitive normal polynomial over any finite field with any specified coefficient arbitrarily prescribed. Let n15 be a positive integer and q a prime power. We prove that for any aF_q and any 1m<n, there exists a primitive normal polynomial f(x)=xⁿ−σ₁xⁿ⁻¹++(−1)ⁿ⁻¹σ_n−1x+(−1)ⁿσ_n such that σ_m=a, with the only exceptions σ₁≠0. The theory can be extended to polynomials of smaller degree too.     

The maximum spectral radius of -free graphs of given order and size

Suppose that G is a graph with n vertices and m edges, and let μ be the spectral radius of its adjacency matrix.Recently we showed that if G has no 4-cycle, then μ²-μn-1, with equality if and only if G is the friendship graph.Here we prove that if m9 and G has no 4-cycle, then μ²m, with equality if G is a star. For 4m8 this assertion fails.     

Refined blowup criteria and nonsymmetric blowup of an aggregation equation

We consider an aggregation equation in , d2, with fractional dissipation: u_t+(uK*u)=−νΛ^γu, where ν0, 0<γ<1, and K(x)=e^−|x|. We prove a refined blowup criteria by which the global existence of solutions is controlled by its norm, for any . We prove the finite time blowup of solutions for a general class of nonsymmetric initial data. The argument presented works for both the inviscid case ν=0 and the supercritical case ν>0 and 0<γ<1. Additionally, we present new proofs of blowup which does not use free energy arguments.     

Multifractal formalism for self-similar measures with weak separation condition

For any self-similar measure μ on satisfying the weak separation condition, we show that there exists an open ball U₀ with μ(U₀)>0 such that the distribution of μ, restricted on U₀, is controlled by the products of a family of non-negative matrices, and hence μ|_U0 satisfies a kind of quasi-product property. Furthermore, the multifractal formalism for μ|_U0 is valid on the whole range of dimension spectrum, regardless of whether there are phase transitions. Moreover the dimension spectra of μ and μ|_U0 coincide for q0. This result unifies and improves many of the recent works on the multifractal structure of self-similar measures with overlaps.     

Algorithms for graphs of bounded treewidth via orthogonal range searching

We show that, for any fixed constant k3, the sum of the distances between all pairs of vertices of an abstract graph with n vertices and treewidth at most k can be computed in O(nlog^k−1n) time.We also show that, for any fixed constant k2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(nlog^k+1n) expected time. The dilation (or stretch-factor) of a geometric graph is defined as the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance.The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.     

Rational Approximation with Varying Weights III

Approximation by weighted rationals of the form wⁿr_n, where r_n=p_n/q_n, p_n and q_n are polynomials of degree at most [αn] and [βn], respectively, and w is an admissible weight, is investigated on compact subsets of the real line for a general class of weights and given α0, β0, with α+β>0. Conditions that characterize the largest sets on which such approximation is possible are given. We apply the general theorems to Laguerre and Freud weights.     

Uniqueness and stability of regional blow-up in a porous-medium equation

We study the blow-up phenomenon for the porous-medium equation in R^N, N1, u_t=Δu^m+u^m, m>1, for nonnegative, compactly supported initial data. A solution u(x,t) to this problem blows-up at a finite time . Our main result asserts that there is a finite number of points x₁,…,x_kR^N, with |x_i−x_j|2R^* for i≠j, such that Here w_*(|x|) is the unique nontrivial, nonnegative compactly supported, radially symmetric solution of the equation in R^N and R^* is the radius of its support. Moreover u(x,t) remains uniformly bounded up to its blow-up time on compact subsets of . The question becomes reduced to that of proving that the ω-limit set in the problem consists of a single point when its initial condition is nonnegative and compactly supported.     

Large deviations from a macroscopic scaling limit for particle systems with Kac interaction and random potential

We consider a lattice gas in a periodic d-dimensional lattice of width γ⁻¹, γ>0, interacting via a Kac's type interaction, with range and strength γ^d, and under the influence of a random one body potential given by independent, bounded, random variables with translational invariant distribution. The system evolves through a conservative dynamics, i.e. particles jump to nearest neighbor empty sites, with rates satisfying detailed balance with respect to the equilibrium measures. In [M. Mourragui, E. Orlandi, E. Saada, Macroscopic evolution of particles systems with random field Kac interactions, Nonlinearity 16 (2003) 2123–2147] it has been shown that rescaling space as γ⁻¹ and time as γ⁻², in the limit γ→0, for dimensions d3, the macroscopic density profile ρ satisfies, a.s. with respect to the random field, a non-linear integral partial differential equation, having the diffusion matrix determined by the statistical properties of the external random field. Here we show an almost sure (with respect to the random field) large deviations principle for the empirical measures of such a process. The rate function, which depends on the statistical properties of the external random field, is lower semicontinuous and has compact level sets.     

On shredders and vertex connectivity augmentation

We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordán computes an augmenting edge set with at most (k−1)/2 edges over the optimum. CV(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G−C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p3) is less than 2n/(2p−3), and that this bound is asymptotically tight.     

Positive solutions for logistic type quasilinear elliptic equations on R

In this paper, we consider positive solutions of the logistic type p-Laplacian equation −Δ_pu=a(x)|u|^p−2u−b(x)|u|^q−1u, xR^N (N2). We show that under rather general conditions on a(x) and b(x) for large |x|, the behavior of the positive solutions for large |x| can be determined. This is then used to show that there is a unique positive solution. Our results improve the corresponding ones in J. London Math. Soc. (2) 64 (2001) 107–124 and J. Anal. Math., in press.     

Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems

The paper concerns a new variant of the hierarchical facility location problem on metric powers (HFL_β[h]), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set F of locations that may open a facility, subsets D₁,D₂,…,D_h−1 of locations that may open an intermediate transmission station and a set D_h of locations of clients. Each client in D_h must be serviced by an open transmission station in D_h−1 and every open transmission station in D_l must be serviced by an open transmission station on the next lower level, D_l−1. An open transmission station on the first level, D₁ must be serviced by an open facility. The cost of assigning a station j on level l1 to a station i on level l−1 is c_ij. For iF, the cost of opening a facility at location i is f_i0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the bounded depth Steiner tree problem and the bounded hop strong-connectivity range assignment problem.