A note on two source location problems

We consider Source Location ($\mathsf{SL}$) problems: given a capacitated network $G=(V,E)$, cost $c(v)$ and a demand $d(v)$ for every $v\in V$, choose a min-cost $S\subseteq V$ so that $\lambda (v,S)⩾d(v)$ holds for every $v\in V$, where $\lambda (v,S)$ is the maximum flow value from v to S. In the directed variant, we have demands $d^{\mathit{in}}(v)$ and $d^{\mathit{out}}(v)$ and we require $\lambda (S,v)⩾d^{\mathit{in}}(v)$ and $\lambda (v,S)⩾d^{\mathit{out}}(v)$. Undirected $\mathsf{SL}$ is (weakly) NP-hard on stars with $r(v)=0$ for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected $\mathsf{SL}$ admit a $(\ln D+1)$-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected $\mathsf{SL}$ on trees with running time $O(|V|{\Delta }^3)$, where $\Delta ={\max }_{v\in V}d(v)$. This algorithm is used to derive a linear time algorithm for undirected $\mathsf{SL}$ with $\Delta ⩽3$. We also consider the Single Assignment Source Location ($\mathsf{SASL}$) where every $v\in V$ should be assigned to a single node $s(v)\in S$. While the undirected $\mathsf{SASL}$ is in P, we give a $(\ln |V|+1)$-approximation algorithm for the directed case, and show that this is tight, unless P = NP.     

A Schauder and Riesz basis criterion for non-self-adjoint Schrödinger operators with periodic and antiperiodic boundary conditions

Under the assumption that $V\in L^2([0,\pi ];dx)$, we derive necessary and sufficient conditions in terms of spectral data for (non-self-adjoint) Schrödinger operators $?d^2/d{x}^2+V$ in $L^2([0,\pi ];dx)$ with periodic and antiperiodic boundary conditions to possess a Riesz basis of root vectors (i.e., eigenvectors and generalized eigenvectors spanning the range of the Riesz projection associated with the corresponding periodic and antiperiodic eigenvalues).We also discuss the case of a Schauder basis for periodic and antiperiodic Schrödinger operators $?d^2/d{x}^2+V$ in $L^p([0,\pi ];dx)$, $p\in (1,\infty )$.     

Weak version of restriction estimates for spheres and paraboloids in finite fields

We study $L^p-L^r$ restriction estimates for algebraic varieties in d-dimensional vector spaces over finite fields. Unlike the Euclidean case, if the dimension d is even, then it is conjectured that the $L^{(2d+2)/(d+3)}-L^2$ Stein–Tomas restriction result can be improved to the $L^{(2d+4)/(d+4)}-L^2$ estimate for both spheres and paraboloids in finite fields. In this paper we show that the conjectured $L^p-L^2$ restriction estimate holds in the specific case when test functions under consideration are restricted to d-coordinate functions or homogeneous functions of degree zero. To deduce our result, we use the connection between the restriction phenomena for our varieties in d dimensions and those for homogeneous varieties in $(d+1)$ dimensions.     

Critical space for the parabolic-parabolic Keller–Segel model in Rd

We study the Keller–Segel system in ${\mathbb{R}}^d$ when the chemoattractant concentration is described by a parabolic equation. We prove that the critical space, with some similarity to the elliptic case, is that the initial bacteria density satisfies $n_0\in L^a({\mathbb{R}}^d)$, $a>d/2$, and that the chemoattractant concentration satisfies $\mathrm{?}{c}_0\in L^d({\mathbb{R}}^d)$. In these spaces, we prove that small initial data give rise to global solutions that vanish as the heat equation for large times and that exhibit a regularizing effect of hypercontractivity type. To cite this article: L. Corrias, B. Perthame, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

Extremal trees with given degree sequence for the Randić index

The Randi? index of a graph G is the sum of $((d(u))(d(v)){)}^{\alpha }$ over all edges $\mathit{uv}$ of G, where $d(v)$ denotes the degree of $v$ in G, $\alpha \ne 0$. When $\alpha =1$, it is the weight of a graph. Delorme, Favaron, and Rautenbach characterized the trees with a given degree sequence with maximum weight, where the question of finding the tree that minimizes the weight is left open. In this note, we characterize the extremal trees with given degree sequence for the Randi? index, thus answering the same question for weight. We also provide an algorithm to construct such trees.     

Improved Cotlar's inequality in the context of local Tb theorems

In the context of local Tb theorems with $L^p$ testing conditions we prove an enhanced Cotlar's inequality. This is related to the problem of removing the so called buffer assumption of Hytönen–Nazarov, which is the final barrier for the full solution of S. Hofmann's problem. We also investigate the problem of extending the Hytönen–Nazarov result to non-homogeneous measures. We work not just with the Lebesgue measure but with measures μ in ${\mathbb{R}}^d$ satisfying $\mu (B(x,r))\le C{r}^n$, $n\in (0,d]$. The range of exponents in the Cotlar type inequality depend on n. Without assuming buffer we get the full range of exponents $p,q\in (1,2]$ for measures with $n\le 1$, and in general we get $p,q\in [2??(n),2]$, $?(n)>0$. Consequences for (non-homogeneous) local Tb theorems are discussed.     

On the semiclassical approximation to the eigenvalue gap of Schrödinger operators

We consider two types of Schrödinger operators $H(t)=?d^2/d{x}^2+q(x)+t\cos x$ and $H(t)=?d^2/d{x}^2+q(x)+A\cos (tx)$ defined on $L^2(\mathbb{R})$, where q is an even potential that is bounded from below, A is a constant, and $t>0$ is a parameter. We assume that $H(t)$ has at least two eigenvalues below its essential spectrum; and we denote by ${\lambda }_1(t)$ and ${\lambda }_2(t)$ the lowest eigenvalue and the second one, respectively. The purpose of this paper is to study the asymptotics of the gap $\Gamma (t)={\lambda }_2(t)?{\lambda }_1(t)$ in the limit as $t\to \infty$.     

Contracting an element from a cocircuit

We consider the situation that M and N are 3-connected matroids such that $|E(N)|⩾4$ and $C^1$ is a cocircuit of M with the property that $M/x_0$ has an N-minor for some $x_0\in C^1$. We show that either there is an element $x\in C^1$ such that $\mathrm{si}(M/x)$ or $\mathrm{co}(\mathrm{si}(M/x))$ is 3-connected with an N-minor, or there is a four-element fan of M that contains two elements of $C^1$ and an element x such that $\mathrm{si}(M/x)$ is 3-connected with an N-minor.