The complexity of detecting fixed-density clusters

We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let γ:N→Q₊ be any density function, i.e., γ is computable in polynomial time and satisfies γ(k)?k-1 for all k∈N. Then γ-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least γ(k). For γ(k)=k-1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for γ(k)=2. We ask for the possible functions γ such that γ-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: γ CLUSTER is NP-complete if γ=2+Ω(1/k^1-ε) for some ε>0 and has a polynomial-time algorithm for γ=2+O(1/k). The algorithm also shows that for γ=2+O(1/k^1-o(1)), γ-CLUSTER is solvable in subexponential time 2^no(1).     

On differential inclusions with prescribed attainable sets

In this article, the inverse problem of the differential inclusion theory is studied. For a given ε>0 and a continuous set valued map t→W(t), t∈[t₀,θ], where W(t)⊂Rⁿ is compact and convex for every t∈[t₀,θ], it is required to define differential inclusion so that the Hausdorff distance between the attainable set of the differential inclusion at the time moment t with initial set (t₀,W(t₀)) and W(t) would be less than ε for every t∈[t₀,θ].     

Preconditioned conjugate gradient method for generalized least squares problems

A variant of the preconditioned conjugate gradient method to solve generalized least squares problems is presented. If the problem is min (Ax − b)^TW⁻¹(Ax − b) with A ∈ R^m×n and W ∈ R^m×m symmetric and positive definite, the method needs only a preconditioner A₁ ∈ R^n×n, but not the inverse of matrix W or of any of its submatrices. Freund's comparison result for regular least squares problems is extended to generalized least squares problems. An error bound is also given.     

Regularity, monotonicity and symmetry of positive solutions of m-Laplace equations

We consider the Dirichlet problem for positive solutions of the equation −Δ_m(u)=f(u) in a bounded smooth domain Ω, with f locally Lipschitz continuous, and prove some regularity results for weak solutions. In particular when f(s)>0 for s>0 we prove summability properties of , and Sobolev's and Poincaré type inequalities in weighted Sobolev spaces with weight |Du|^m−2. The point of view of considering |Du|^m−2 as a weight is particularly useful when studying qualitative properties of a fixed solution. In particular, exploiting these new regularity results we can prove a weak comparison principle for the solutions and, using the well known Alexandrov-Serrin moving plane method, we then prove a general monotonicity (and symmetry) theorem for positive solutions u of the Dirichlet problem in bounded (and symmetric in one direction) domains when f(s)>0 for s>0 and m>2. Previously, results of this type in general bounded (and symmetric) domains had been proved only in the case 1<m<2.     

Bifurcation from stability to instability for a free boundary problem modeling tumor growth by Stokes equation

We consider a free boundary problem modeling tumor growth in fluid-like tissue. The model equations include a diffusion equation for the nutrient concentration, and the Stokes equation with a source which represents the proliferation of tumor cells. The proliferation rate μ and the cell-to-cell adhesiveness γ which keeps the tumor intact are two parameters which characterize the “aggressiveness” of the tumor. For any positive radius R there exists a unique radially symmetric stationary solution with radius r=R. For a sequence μ/γ=Mn(R) there exist symmetry-breaking bifurcation branches of solutions with free boundary r=R+εYn,0(θ)+O(ε²) (n even ?2) for small |ε|, where Yn,0 is the spherical harmonic of mode (n,0). Furthermore, the smallest Mn(R), say Mn_∗(R), is such that n_∗=n_∗(R)→∞ as R→∞. In this paper we prove that the radially symmetric stationary solution with R=RS is linearly stable if μ/γ<N_∗(RS,γ) and linearly unstable if μ/γ>N_∗(RS,γ), where N_∗(RS,γ)?Mn_∗(RS), and we prove that strict inequality holds if γ is small or if γ is large. The biological implications of these results are discussed at the end of the paper.     

Locating the peaks of least-energy solutions to a quasilinear elliptic Neumann problem, Part II

We continue our work (Y. Li, C. Zhao, Locating the peaks of least-energy solutions to a quasilinear elliptic Neumann problem, J. Math. Anal. Appl. 336 (2007) 1368-1383) to study the shape of least-energy solutions to the quasilinear problem ε^mΔ_mu−u^m−1+f(u)=0 with homogeneous Neumann boundary condition. In this paper we focus on the case 1<m<2 as a complement to our previous work on the case m≥2. We use an intrinsic variation method to show that as the case m≥2, when ε→0⁺, the global maximum point P_ε of least-energy solutions goes to a point on the boundary ∂Ω at a rate of o(ε) and this point on the boundary approaches a global maximum point of mean curvature of ∂Ω.     

On the Riesz basis of a family of analytic operators in the sense of Kato and application to the problem of radiation of a vibrating structure in a light fluid

In this paper, we prove that the system formed by some of generalized eigenvectors of the operator T₀+εT₁+ε²T₂+? which are analytic on ε, forms a Riesz basis of the separable Hilbert space H, where ε∈C and T₀,T₁,T₂,… some linear transformations on H which have the same domain D⊆H. After that, we give an application for a problem concerning the radiation of a vibrating structure in a light fluid.     

Homeomorphism with zero Jacobian: Sharp integrability of the derivative

Let N?2. We construct a homeomorphism f∈W1,1(N[0,1],RN) such that Jf=0 almost everywhere and sup0<ε?N−1εN[0,1]_∫|Df|^N−ε<∞. In particular, f∈W1,p(N[0,1],N[0,1]) for all p∈[1,N).     

About a construction and some analysis of time inhomogeneous diffusions on monotonely moving domains

We construct and analyze in a very general way time inhomogeneous (possibly also degenerate or reflected) diffusions in monotonely moving domains E⊂R×R^d, i.e. if E_t?{x∈R^d|(t,x)∈E}, t∈R, then either E_s⊂E_t, ∀s?t, or E_s⊃E_t, ∀s?t, s,t∈R. Our major tool is a further developed L²(E,m)-analysis with well chosen reference measure m. Among few examples of completely different kinds, such as e.g. singular diffusions with reflection on moving Lipschitz domains in R^d, non-conservative and exponential time scale diffusions, degenerate time inhomogeneous diffusions, we present an application to what we name skew Bessel process on γ. Here γ is either a monotonic function or a continuous Sobolev function. These diffusions form a natural generalization of the classical Bessel processes and skew Brownian motions, where the local time refers to the constant function γ≡0.     

A parabolic free boundary problem with double pinning

We study the Cauchy problem for the equation ∂_tu_ε−Δu_ε=−β_ε(u_ε) in (0,∞)×Rⁿ as $\text{ε→0}$, where the nonlinearity β_ε is assumed to converge to a measure concentrated at $\text{0}$. In this paper we allow for sign changes of β_ε and u_ε. The solutions are uniformly Lipschitz continuous in space and Hölder continuous in time. We show that each limit of u_ε is a solution of the free boundary problem ∂_tu−Δu=0 in {u>0}∩(0,∞)×Rⁿ,|∇u⁺|²−|∇u⁻|²=g on (∂{u>0}∪∂{u<0})∩((0,∞)×Rⁿ) in the sense of domain variations. Depending on the structure of the nonlinearity $\text{β}{}_{\mathrm{\epsilon }}\text{,}$ the function g in the condition on the free boundary need not be a constant.     

Existence of global bounded weak solutions to nonsymmetric systems of Keyfitz-Kranzer type

In this paper, we study the global L^∞ solutions for the Cauchy problem of nonsymmetric system (1.1) of Keyfitz-Kranzer type. When n=1, (1.1) is the Aw-Rascle traffic flow model. First, we introduce a new flux approximation to obtain a lower bound ρε,δ?δ>0 for the parabolic system generated by adding “artificial viscosity” to the Aw-Rascle system. Then using the compensated compactness method with the help of L¹ estimate of wε,δx(⋅,t) we prove the pointwise convergence of the viscosity solutions under the general conditions on the function P(ρ), which includes prototype function , where γ∈(−1,0)∪(0,∞), A is a constant. Second, by means of BV estimates on the Riemann invariants and the compensated compactness method, we prove the global existence of bounded entropy weak solutions for the Cauchy problem of general nonsymmetric systems (1.1).     

Existence results of a m-point boundary value problem at resonance

Let ξ_i∈(0,1), a_i∈(0,∞), i=1,…,m−2, be given constants satisfying ∑^m−2_i=1a_i=1 and 0<ξ₁<ξ₂<?<ξ_m−2<1. We show the existence of solutions for the m-point boundary value problem

x″=f(t,x,x′),t∈(0,1),     

Quantum Complexity of Integration

It is known that quantum computers yield a speed-up for certain discrete problems. Here we want to know whether quantum computers are useful for continuous problems. We study the computation of the integral of functions from the classical Hölder classes F^k, α_d on [0, 1]^d and define γ by γ=(k+α)/d. The known optimal orders for the complexity of deterministic and (general) randomized methods are comp(F^k, α_d, ε)≍ε^−1/γ and comp^random(F^k, α_d, ε)≍ε^−2/(1+2γ). For a quantum computer we prove comp^quant_query(F^k, α_d, ε)≍ε^−1/(1+γ) and comp^quant(F^k, α_d, ε)⩽Cε^−1/(1+γ)(log ε⁻¹)^1/(1+γ). For restricted Monte Carlo (only coin tossing instead of general random numbers) we prove comp^coin(F^k, α_d, ε)⩽Cε^−2/(1+2γ)(log ε⁻¹)^1/(1+2γ). To summarize the results one can say that   • there is an exponential speed-up of quantum algorithms over deterministic (classical) algorithms, if γ is small;   • there is a (roughly) quadratic speed-up of quantum algorithms over randomized classical methods, if γ is small.     

Existence and regularity of extremal solutions for a mean-curvature equation

We study a class of mean curvature equations −Mu=H+λup where M denotes the mean curvature operator and for p?1. We show that there exists an extremal parameter λ^∗ such that this equation admits a minimal weak solutions for all λ∈[0,λ^∗], while no weak solutions exists for λ>λ^∗ (weak solutions will be defined as critical points of a suitable functional). In the radially symmetric case, we then show that minimal weak solutions are classical solutions for all λ∈[0,λ^∗] and that another branch of classical solutions exists in a neighborhood (λ_∗−η,λ^∗) of λ^∗.     

Using Lagrangians of hypergraphs to find non-jumping numbers(II)

Let r?2 be an integer. A real number α∈[0,1) is a jump for r if for any ε>0 and any integer m?r, any r-uniform graph with n>n₀(ε,m) vertices and density at least α+ε contains a subgraph with m vertices and density at least α+c, where c=c(α)>0 does not depend on ε and m. A result of Erd?s, Stone and Simonovits implies that every α∈[0,1) is a jump for r=2. Erd?s asked whether the same is true for r?3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumping numbers for every r?3. However, there are a lot of unknowns on determining whether or not a number is a jump for r?3. In this paper, we find two infinite sequences of non-jumping numbers for r=4, and extend one of the results to every r?4. Our approach is still based on the approach developed by Frankl and Rödl.     

Generating non-jumping numbers recursively

Let r?2 be an integer. A real number α∈[0,1) is a jump for r if there is a constant c>0 such that for any ε>0 and any integer m where m?r, there exists an integer n₀ such that any r-uniform graph with n>n₀ vertices and density ?α+ε contains a subgraph with m vertices and density ?α+c. It follows from a fundamental theorem of Erd?s and Stone that every α∈[0,1) is a jump for r=2. Erd?s asked whether the same is true for r?3. Frankl and Rödl gave a negative answer by showing some non-jumping numbers for every r?3. In this paper, we provide a recursive formula to generate more non-jumping numbers for every r?3 based on the current known non-jumping numbers.     

On an eigenvalue problem involving variable exponent growth conditions

We study the problem in Ω, u=0 on ∂Ω, where Ω is a bounded domain in R^N, is a continuous function and λ and ε are two positive constants. We prove that for any ε>0 each λ∈(0,λ₁) is an eigenvalue of the above problem, where λ₁ is the principal eigenvalue of the Laplace operator on Ω. Moreover, for each eigenvalue λ∈(0,λ₁) it corresponds a unique eigenfunction. The proofs will be based on the Banach fixed point theorem combined with adequate variational techniques.     

On a property of plane curves

Let γ:[0,1]→²[0,1] be a continuous curve such that γ(0)=(0,0), γ(1)=(1,1), and γ(t)∈²(0,1) for all t∈(0,1). We prove that, for each n∈N, there exists a sequence of points Ai, 0?i?n+1, on γ such that A₀=(0,0), An+1=(1,1), and the sequences and , 0?i?n, are positive and the same up to order, where π₁, π₂ are projections on the axes.     

Global solutions of the fast diffusion equation with gradient absorption terms

We investigate the existence of nonnegative weak solutions to the problem ut=Δ(um)−p|∇u| in Rn×(0,∞) with ⁺(1−2/n)<m<1. It will be proved that: (i) When 1<p<2, if the initial datum u₀∈D(Rn) then there exists a solution; (ii) When 1<p<(2+mn)/(n+1), if the initial datum u₀(x) is a bounded and nonnegative measure then the solution exists; (iii) When (2+mn)/(n+1)?p<2, if the initial datum is a Dirac mass then the solution does not exist. We also study the large time behavior of the L¹-norm of solutions for 1<p?(2+mn)/(n+1), and the large time behavior of t1/β‖u(⋅,t)−Ec(⋅,t)L^∞_‖ for (2+mn)/(n+1)<p<2.     

Internal Lifshits tails for random magnetic Schrödinger operators

This paper is devoted to the study of Lifshits tails for weak random magnetic perturbations of periodic Schrödinger operators acting on L²(Rd) of the form Hλ,w=(−i∇−λ_∑γ∈ZdwγA²(⋅−γ))+V, where V is a Zd-periodic potential, λ is positive coupling constants, (wγ)_γ∈Zd are i.i.d and bounded random variables and is the single site vector magnetic potential. We prove that, for λ small, at an open band edge, a true Lifshits tail for the random magnetic Schrödinger operator occurs if a certain set of conditions on H₀=−Δ+V and on A holds.