A lower bound for on-line ranking number of a path

A k-ranking of a graph G is a mapping $\varphi :V(G)\to \{1,\dots ,k\}$ such that any path with endvertices x and y satisfying $x\ne y$ and $\varphi (x)=\varphi (y)$ contains a vertex z with $\varphi (z)>\varphi (x)$. The ranking number ${\chi }_{\mathrm{r}}(G)$ of G is the minimum k admitting a k-ranking of G. The on-line ranking number ${\chi }_{\mathrm{r}}^{*}(G)$ of G is the corresponding on-line invariant; in that case vertices of G are coming one by one so that a partial ranking has to be chosen by considering only the structure of the subgraph of G induced by the present vertices. It is known that $\lfloor {\log }_{2}n\rfloor +1={\chi }_{\mathrm{r}}(P_n)⩽{\chi }_{\mathrm{r}}^{*}(P_n)⩽2\lfloor {\log }_{2}n\rfloor +1$. In this paper it is proved that ${\chi }_{\mathrm{r}}^{*}(P_n)>1.619{\log }_{2}n-1$.     

Large deviations of kernel density estimator in L1(Rd) for uniformly ergodic Markov processes

In this paper, we consider a uniformly ergodic Markov process $(X_n{)}_{n⩾0}$ valued in a measurable subset E of ${\mathbb{R}}^d$ with the unique invariant measure $\mu (\mathrm{d}x)=f(x)\mathrm{d}x$, where the density f is unknown. We establish the large deviation estimations for the nonparametric kernel density estimator $f_n^{*}$ in $L^1({\mathbb{R}}^d,\mathrm{d}x)$ and for $6f_n^{*}-f{6}_{L^1({\mathbb{R}}^d,\mathrm{d}x)}$, and the asymptotic optimality $f_n^{*}$ in the Bahadur sense. These generalize the known results in the i.i.d. case.     

Reconstruction and subgaussian processes

This Note presents a randomized method to approximate any vector v from some set $T\subset {\mathbb{R}}^n$. The data one is given is the set T, and k scalar products ${(〈X_i,v〉)}_{i=1}^k$, where ${(X_i)}_{i=1}^k$ are i.i.d. isotropic subgaussian random vectors in ${\mathbb{R}}^n$, and $k\ll n$. We show that with high probability any $y\in T$ for which ${(〈X_i,y〉)}_{i=1}^k$ is close to the data vector ${(〈X_i,v〉)}_{i=1}^k$ will be a good approximation of v, and that the degree of approximation is determined by a natural geometric parameter associated with the set T. This extends and improves recent results by Candes and Tao. To cite this article: S. Mendelson et al., C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

On parabolic Kazhdan–Lusztig R-polynomials for the symmetric group

Parabolic R-polynomials were introduced by Deodhar as parabolic analogues of ordinary R-polynomials defined by Kazhdan and Lusztig. In this paper, we are concerned with the computation of parabolic R-polynomials for the symmetric group. Let $S_n$ be the symmetric group on $\{1,2,\dots ,n\}$, and let $S=\{s_i|1\le i\le n?1\}$ be the generating set of $S_n$, where for $1\le i\le n?1$, $s_i$ is the adjacent transposition. For a subset $J?S$, let ${(S_n)}_J$ be the parabolic subgroup generated by J, and let ${(S_n)}^J$ be the set of minimal coset representatives for $S_n/{(S_n)}_J$. For $u\le v\in {(S_n)}^J$ in the Bruhat order and $x\in \{q,?1\}$, let $R_{u,v}^{J,x}(q)$ denote the parabolic R-polynomial indexed by u and v. Brenti found a formula for $R_{u,v}^{J,x}(q)$ when $J=S?\{s_i\}$, and obtained an expression for $R_{u,v}^{J,x}(q)$ when $J=S?\{s_{i?1},s_i\}$. In this paper, we provide a formula for $R_{u,v}^{J,x}(q)$, where $J=S?\{s_{i?2},s_{i?1},s_i\}$ and i appears after $i?1$ in v. It should be noted that the condition that i appears after $i?1$ in v is equivalent to that v is a permutation in ${(S_n)}^{S?\{s_{i?2},s_i\}}$. We also pose a conjecture for $R_{u,v}^{J,x}(q)$, where $J=S?\{s_k,s_{k+1},\dots ,s_i\}$ with $1\le k\le i\le n?1$ and v is a permutation in ${(S_n)}^{S?\{s_k,s_i\}}$.     

Toeplitz quantization on Fock space

For Toeplitz operators $T_f^{(t)}$ acting on the weighted Fock space $H_t^2$, we consider the semi-commutator $T_f^{(t)}{T}_g^{(t)}?T_{fg}^{(t)}$, where $t>0$ is a certain weight parameter that may be interpreted as Planck's constant ? in Rieffel's deformation quantization. In particular, we are interested in the semi-classical limit

($?$)$\underset{t\to 0}{\lim }?{6T_f^{(t)}{T}_g^{(t)}?T_{fg}^{(t)}6}_t.$

It is well-known that ${6T_f^{(t)}{T}_g^{(t)}?T_{fg}^{(t)}6}_t$ tends to 0 under certain smoothness assumptions imposed on f and g. This result was recently extended to $f,g\in \mathrm{BUC}({\mathbb{C}}^n)$ by Bauer and Coburn. We now further generalize (?) to (not necessarily bounded) uniformly continuous functions and symbols in the algebra $\mathrm{VMO}\cap L^{\infty }$ of bounded functions having vanishing mean oscillation on ${\mathbb{C}}^n$. Our approach is based on the algebraic identity $T_f^{(t)}{T}_g^{(t)}?T_{fg}^{(t)}=?{(H_{\overline{f}}^{(t)})}^{?}{H}_g^{(t)}$, where $H_g^{(t)}$ denotes the Hankel operator corresponding to the symbol g, and norm estimates in terms of the (weighted) heat transform. As a consequence, only f (or likewise only g) has to be contained in one of the above classes for (?) to vanish. For g we only have to impose ${\lim \sup }_{t\to 0}{6H_g^{(t)}6}_t<\infty$, e.g. $g\in L^{\infty }({\mathbb{C}}^n)$. We prove that the set of all symbols $f\in L^{\infty }({\mathbb{C}}^n)$ with the property that ${\lim }_{t\to 0}?{6T_f^{(t)}{T}_g^{(t)}?T_{fg}^{(t)}6}_t={\lim }_{t\to 0}?{6T_g^{(t)}{T}_f^{(t)}?T_{gf}^{(t)}6}_t=0$ for all $g\in L^{\infty }({\mathbb{C}}^n)$ coincides with $\mathrm{VMO}\cap L^{\infty }$. Additionally, we show that $\underset{t\to 0}{\lim }?{6T_f^{(t)}6}_t={6f6}_{\infty }$ holds for all $f\in L^{\infty }({\mathbb{C}}^n)$. Finally, we present new examples, including bounded smooth functions, where (?) does not vanish.     

On a conjecture of Faulhuber and Steinerberger on the logarithmic derivative of ϑ4

Faulhuber and Steinerberger conjectured that the logarithmic derivative of ${?}_4$ has the property that $y^2{?}_4^{\prime }(y)/{?}_4(y)$ is strictly decreasing and strictly convex. In this small note, we prove this conjecture.     

Sharp bounds for the spectral radius of digraphs

Let $G=(V\text{,}E)$ be a digraph with n vertices and m arcs without loops and multiarcs. The spectral radius $\rho (G)$ of G is the largest eigenvalue of its adjacency matrix. In this paper, the following sharp bounds on $\rho (G)$ have been obtained.$\min \{\sqrt{t_i^{+}{t}_j^{+}}:(v_i\text{,}{v}_j)\in E\}?\rho (G)?\max \{\sqrt{t_i^{+}{t}_j^{+}}:(v_i\text{,}{v}_j)\in E\}$where G is strongly connected and $t_i^{+}$ is the average 2-outdegree of vertex $v_i$. Moreover, each equality holds if and only if G is average 2-outdegree regular or average 2-outdegree semiregular.     

Existence and convexity of local solutions to degenerate Hessian equations

In this work, we prove the existence of convex solutions to the following k-Hessian equation

$S_k[u]=K(y)g(y,u,Du)$

in the neighborhood of a point $(y_0,u_0,p_0)\in {\mathbb{R}}^n\times \mathbb{R}\times {\mathbb{R}}^n$, where $g\in C^{\infty },g(y_0,u_0,p_0)>0$, $K\in C^{\infty }$ is nonnegative near $y_0$, $K(y_0)=0$ and $\text{Rank}(D_y^{2}K)(y_0)\ge n?k+1$.