On the length of an external branch in the Beta-coalescent

In this paper, we consider Beta(2−α,α)$(2-\alpha ,\alpha )$ (with 1<α<2$1<\alpha <2$) and related Λ$\Lambda$-coalescents. If T⁽ⁿ⁾$T^{\left(n\right)}$ denotes the length of a randomly chosen external branch of the n$n$-coalescent, we prove the convergence of n^α−1T⁽ⁿ⁾$n^{\alpha -1}{T}^{\left(n\right)}$ when n$n$ tends to ∞$\infty$, and give the limit. To this aim, we give asymptotics for the number σ⁽ⁿ⁾${\sigma }^{\left(n\right)}$ of collisions which occur in the n$n$-coalescent until the end of the chosen external branch, and for the block counting process associated with the n$n$-coalescent.     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

Estimating the ground state energy of the Schrödinger equation for convex potentials

In 2011, the fundamental gap conjecture for Schrödinger operators was proven. This can be used to estimate the ground state energy of the time-independent Schrödinger equation with a convex potential and relative error ε$\epsilon$. Classical deterministic algorithms solving this problem have cost exponential in the number of its degrees of freedom d$d$. We show a quantum algorithm, that is based on a perturbation method, for estimating the ground state energy with relative error ε$\epsilon$. The cost of the algorithm is polynomial in d$d$ and ε⁻¹${\epsilon }^{-1}$, while the number of qubits is polynomial in d$d$ and logε⁻¹$log{\epsilon }^{-1}$. In addition, we present an algorithm for preparing a quantum state that overlaps within 1−δ,δ∈(0,1)$1-\delta ,\delta \in (0,1)$, with the ground state eigenvector of the discretized Hamiltonian. This algorithm also approximates the ground state with relative error ε$\epsilon$. The cost of the algorithm is polynomial in d$d$, ε⁻¹${\epsilon }^{-1}$ and δ⁻¹${\delta }^{-1}$, while the number of qubits is polynomial in d$d$, logε⁻¹$log{\epsilon }^{-1}$ and logδ⁻¹$log{\delta }^{-1}$.     

An upper bound for a valence of a face in a parallelohedral tiling

Consider a face-to-face parallelohedral tiling of R^d${\mathbb{R}}^d$ and a (d−k)$(d-k)$-dimensional face F$F$ of the tiling. We prove that the valence of F$F$ (i.e. the number of tiles containing F$F$ as a face) is not greater than 2^k$2^k$. If the tiling is affinely equivalent to a Voronoi tiling for some lattice (the so called Voronoi case), this gives a well-known upper bound for the number of vertices of a Delaunay k$k$-cell. Yet we emphasize that such an affine equivalence is not assumed in the proof.     

Stable extendibility of vector bundles over real projective spaces

Let F$\mathbb{F}$ be either the real number field R$\mathbb{R}$ or the complex number field C$\mathbb{C}$ and RPⁿ${\mathbb{RP}}^n$ the real projective space of dimension n. Theorems A and C in Hemmi and Kobayashi (2008) [2] give necessary and sufficient conditions for a given F$\mathbb{F}$-vector bundle over RPⁿ${\mathbb{RP}}^n$ to be stably extendible to RP^m${\mathbb{RP}}^m$ for every m?n$m?n$. In this paper, we simplify the theorems and apply them to the tangent bundle of RPⁿ${\mathbb{RP}}^n$, its complexification, the normal bundle associated to an immersion of RPⁿ${\mathbb{RP}}^n$ in R^n+r${\mathbb{R}}^{n+r}$(r>0)$(r>0)$, and its complexification. Our result for the normal bundle is a generalization of Theorem A in Kobayashi et al. (2000) [8] and that for its complexification is a generalization of Theorem 1 in Kobayashi and Yoshida (2003) [5].     

Constructing cubature formulae of degree 5 with few points

This paper is devoted to construct a family of fifth degree cubature formulae for n$n$-cube with symmetric measure and n$n$-dimensional spherically symmetrical region. The formula forn$n$-cube contains at most n²+5n+3$n^2+5n+3$ points and for n$n$-dimensional spherically symmetrical region contains only n²+3n+3$n^2+3n+3$ points. Moreover, the numbers can be reduced to n²+3n+1$n^2+3n+1$ and n²+n+1$n^2+n+1$ if n=7$n=7$ respectively, the latter of which is minimal.     

Estimation for stochastic differential equations with a small diffusion coefficient

We consider a multidimensional diffusion X$X$ with drift coefficient b(_Xt,α)$b(X_t,\alpha )$ and diffusion coefficient εa(_Xt,β)$\epsilon a(X_t,\beta )$ where α$\alpha$ and β$\beta$ are two unknown parameters, while ε$\epsilon$ is known. For a high frequency sample of observations of the diffusion at the time points k/n$k/n$, k=1,…,n$k=1,\dots ,n$, we propose a class of contrast functions and thus obtain estimators of (α,β)$(\alpha ,\beta )$. The estimators are shown to be consistent and asymptotically normal when n→∞$n\to \infty$ and ε→0$\epsilon \to 0$ in such a way that ε⁻¹n^−ρ${\epsilon }^{-1}{n}^{-\rho }$ remains bounded for some ρ>0$\rho >0$. The main focus is on the construction of explicit contrast functions, but it is noted that the theory covers quadratic martingale estimating functions as a special case. In a simulation study we consider the finite sample behaviour and the applicability to a financial model of an estimator obtained from a simple explicit contrast function.     

Asymptotic average shadowing property on compact metric spaces

We prove that if for a continuous map f$f$ on a compact metric space X$X$, the chain recurrent set, R(f)$R\left(f\right)$ has more than one chain component, then f$f$ does not satisfy the asymptotic average shadowing property. We also show that if a continuous map f$f$ on a compact metric space X$X$ has the asymptotic average shadowing property and if A$A$ is an attractor for f$f$, then A$A$ is the single attractor for f$f$ and we have A=R(f)$A=R\left(f\right)$. We also study diffeomorphisms with asymptotic average shadowing property and prove that if M$M$ is a compact manifold which is not finite with dimM=2$dimM=2$, then the C¹$C^1$ interior of the set of all C¹$C^1$ diffeomorphisms with the asymptotic average shadowing property is characterized by the set of Ω$\Omega$-stable diffeomorphisms.     

Growth order for the size of smallest hamiltonian chain saturated uniform hypergraphs

We say that a hypergraph H$H$ is hamiltonian chain saturated if H$H$ does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H$H$. In this paper, for each k≥3$k\ge 3$, we establish the right order of magnitude n^k−1$n^{k-1}$ for the size of the smallest k$k$-uniform hamiltonian chain saturated hypergraph. This solves an open problem of G.Y. Katona.     

Minimum size transversals in uniform hypergraphs

A set of vertices in a hypergraph which meets all the edges is called a transversal. The transversal number τ(H)$\tau \left(H\right)$ of a hypergraph H$H$ is the minimum cardinality of a transversal in H$H$. A classical greedy algorithm for constructing a transversal of small size selects in each step a vertex which has the largest degree in the hypergraph formed by the edges not met yet. The analysis of this algorithm (by Chvátal and McDiarmid (1992)  [3]) gave some upper bounds for τ(H)$\tau \left(H\right)$ in a uniform hypergraph H$H$ with a given number of vertices and edges. We discuss a variation of this greedy algorithm. Analyzing this new algorithm, we obtain upper bounds for τ(H)$\tau \left(H\right)$ which improve the bounds by Chvátal and McDiarmid.     

On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence

In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s$s$-dimensional sequence m$m$, whose elements are vectors obtained by concatenating d$d$-dimensional vectors from a low-discrepancy sequence q$q$ with (s−d)$(s-d)$-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0$\epsilon >0$ the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$ is bounded by ε$\epsilon$ with probability at least 1−2exp(−ε²N/2)$1-2exp(-{\epsilon }^{2}N/2)$ for N$N$ sufficiently large. The authors did not study how large N$N$ actually has to be and if and how this actually depends on the parameters s$s$ and ε$\epsilon$. In this note we derive a lower bound for N$N$, which significantly depends on s$s$ and ε$\epsilon$. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$, which holds without any restrictions on N$N$. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N$N$. We compare this bound to other known bounds.     

On the sum of two closed subspaces

If U,V$U,V$ are closed subspaces of a Fréchet space, then E$E$ is the direct sum of U$U$ and V$V$ if and only if E^′$E^{\prime }$ is the algebraic direct sum of the annihilators U^°$U^{°}$ and V^°$V^{°}$. We provide a simple proof of this (possibly well-known) result.     

Cone isomorphisms and almost surjective operators

Let E$E$ be a Banach lattice and F$F$ a Banach space. A bounded linear operator T:E→F$T:E\to F$ is an isomorphism on the positive cone of E$E$ if and only if T^∗$T^{\ast }$ is almost surjective. A dual version of this theorem holds also. A bounded linear operator T:F→E$T:F\to E$ is almost surjective if and only if T^∗$T^{\ast }$ is an isomorphism on the positive cone of F^∗$F^{\ast }$.     

Test ideals of non-principal ideals: Computations,jumping numbers,alterations and division theorems

Given an ideal a⊆R$\mathfrak{a}\subseteq R$ in a (log) Q$\mathbb{Q}$-Gorenstein F  -finite ring of characteristic p>0$p>0$, we study and provide a new perspective on the test ideal τ(R,a^t)$\tau (R,{\mathfrak{a}}^t)$ for a real number t>0$t>0$. Generalizing a number of known results from the principal case, we show how to effectively compute the test ideal and also describe τ(R,a^t)$\tau (R,{\mathfrak{a}}^t)$ using (regular) alterations with a formula analogous to that of multiplier ideals in characteristic zero. We further prove that the F  -jumping numbers of τ(R,a^t)$\tau (R,{\mathfrak{a}}^t)$ as t varies are rational and have no limit points, including the important case where R is a formal power series ring. Additionally, we obtain a global division theorem for test ideals related to results of Ein and Lazarsfeld from characteristic zero, and also recover a new proof of Skoda's theorem for test ideals which directly mimics the proof for multiplier ideals.     

Heat-kernel estimates for random walk among random conductances with heavy tail

We study models of discrete-time, symmetric, Z^d${\mathbb{Z}}^d$-valued random walks in random environments, driven by a field of i.i.d. random nearest-neighbor conductances _ωxy∈[0,1]${\omega }_{xy}\in [0,1]$, with polynomial tail near 0 with exponent γ>0$\gamma >0$. We first prove for all d≥5$d\ge 5$ that the return probability shows an anomalous decay (non-Gaussian) that approaches (up to sub-polynomial terms) a random constant times n⁻²$n^{-2}$ when we push the power γ$\gamma$ to zero. In contrast, we prove that the heat-kernel decay is as close as we want, in a logarithmic sense, to the standard decay n^−d/2$n^{-d/2}$ for large values of the parameter γ$\gamma$.     

Phase transition in equilibrium fluctuations of symmetric slowed exclusion

We analyze the equilibrium fluctuations of density, current and tagged particle in symmetric exclusion with a slow bond. The system evolves in the one-dimensional lattice and the jump rate is everywhere equal to one except at the slow bond where it is αn^−β$\alpha n^{-\beta }$, with α>0$\alpha >0$, β∈[0,+∞]$\beta \in [0,+\infty ]$ and n$n$ is the scaling parameter. Depending on the regime of β$\beta$, we find three different behaviors for the limiting fluctuations whose covariances are explicitly computed. In particular, for the critical value β=1$\beta =1$, starting a tagged particle near the slow bond, we obtain a family of Gaussian processes indexed in α$\alpha$, interpolating a fractional Brownian motion of Hurst exponent 1/4$1/4$ and the degenerate process equal to zero.     

Partial rigidity of degenerate CR embeddings into spheres

In this paper, we study degenerate CR embeddings f$f$ of a strictly pseudoconvex hypersurface M⊂Cⁿ⁺¹$M\subset {\mathbb{C}}^{n+1}$ into a sphere S$\mathbb{S}$ in a higher dimensional complex space C^N+1${\mathbb{C}}^{N+1}$. The degeneracy of the mapping f$f$ will be characterized in terms of the ranks of the CR second fundamental form and its covariant derivatives. In 2004, the author, together with X. Huang and D. Zaitsev, established a rigidity result for CR embeddings f$f$ into spheres in low codimensions. A key step in the proof of this result was to show that degenerate mappings are necessarily contained in a complex plane section of the target sphere (partial rigidity). In the 2004 paper, it was shown that if the total rank d$d$ of the second fundamental form and all of its covariant derivatives is <n$<n$ (here, n$n$ is the CR dimension of M$M$), then f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$. The converse of this statement is also true, as is easy to see. When the total rank d$d$ exceeds n$n$, it is no longer true, in general, that f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$, as can be seen by examples. In this paper, we carry out a systematic study of degenerate CR mappings into spheres. We show that when the ranks of the second fundamental form and its covariant derivatives exceed the CR dimension n$n$, then partial rigidity may still persist, but there is a “defect” k$k$ that arises from the ranks exceeding n$n$ such that f(M)$f\left(M\right)$ is only contained in a complex plane of dimension n+d+k+1$n+d+k+1$. Moreover, this defect occurs in general, as is illustrated by examples.     

Extension of positive definite functions

Let Ω⊂Rⁿ$\Omega \subset {\mathbb{R}}^n$ be an open, connected subset of Rⁿ${\mathbb{R}}^n$, and let F:Ω−Ω→C$F:\Omega -\Omega \to \mathbb{C}$, where Ω−Ω={x−y:x,y∈Ω}$\Omega -\Omega =\{x-y:x,y\in \Omega \}$, be a continuous positive definite function. We give necessary and sufficient conditions for F   to have an extension to a continuous positive definite function defined on the entire Euclidean space Rⁿ${\mathbb{R}}^n$. The conditions are formulated in terms of existence of a unitary representations of Rⁿ${\mathbb{R}}^n$ whose generators extend a certain system of unbounded Hermitian operators defined on a Hilbert space associated to F. Different positive definite extensions correspond to different unitary representations.     

Analysis of symmetric matrix valued functions I

For any symmetric function f:Rⁿ?Rⁿ$f:{\mathbb{R}}^n?{\mathbb{R}}^n$, one can define a corresponding function on the space of n×n$n\times n$ real symmetric matrices by applying f$f$ to the eigenvalues of the spectral decomposition. We show that this matrix valued function inherits from f$f$ the properties of continuity, Lipschitz continuity, strict continuity, directional differentiability, Frechet differentiability, continuous differentiability.